3 ms·

Implementing a Lisp cons algorithm as-is using a Vec is so far from being apples-to-apples that it makes me question the results of the entire article, despite

Implementing a Lisp cons algorithm as-is using a Vec is so far from being apples-to-apples that it makes me question the results of the entire article, despite the fact that things were eventually "optimized" to not do this. Gathering a list by calling cons over and over is only remotely advisable when you're working with a linked-list (which you are, in Lisp). Blindly replacing it with a Vec demonstrates either a total ignorance of CS fundamentals, or a willingness for the benchmarks to come out a certain way. A real "apples-to-apples" comparison would at least have Rust using an actual linked-list for this algorithm. A mutable Vec is more idiomatic and probably more efficient, but cloning an immutable Vec at every step turns O(N) into O(N^2). Note that this isn't Rust apologism: the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. Most languages' go-to structures for holding a sequence have roughly the performance characteristics of a vector. I guess the article at least fulfills its title: "How to write slow Rust code"

phoe-krk 5y ago
> the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. ...or, to be fully honest, a Common Lisp VECTOR that is then CONCATENATE'd with a new element at its beginning. As I said in another comment, this isn't the problem of using a given language - it's the problem of using a wrong data structure for the job.
- brundolf 5y ago
  Exactly. And the fact that it's framed as "well I just wanted a straight comparison, I didn't want to wade too far into idioms and Rust-isms in the first pass" feels disingenuous.
lalaithion 5y ago
The more general view to take from this is that when you program a lot in one language, you get so used to certain performance patterns that you simply write your code in a way that takes advantage of them first try[1]. Peter Norvig's Lisp solution is an optimized solution for Lisp in a lot of little ways. Directly translating an optimized-for-Lisp program into any other language is silly, because you miss out on the optimizations available in that language to an experienced programmer and you lose out doing pointless things which were essential in Lisp.
- brundolf 5y ago
  I'm arguing that this case stands above that. This isn't some nuance of either language; it's CS 101
  - tux3 5y ago
    I was going to argue the same: This isn't Java vs Rust, it's the author's familiarity with Lisps not translating very well to less purely functional languages. Writing an O(N^2) algorithm should give you pause in any imperative language, if you can spot the copy. The author is clearly not a beginner dev, but the mistake here isn't really Rust specific, it's "vaguely imperative systems language" programming patterns
    - brundolf 5y ago
      That's not quite it; it's not really about functional vs imperative (though there's some loose correlation) Common Lisp isn't purely functional (it's arguably the least-functional of the major Lisps), and in fact it has a vector data structure of its own, so you could make the same mistake there if you went out of your way to. Similarly, Rust has a LinkedList in its standard library. This algorithm is simply O(N) if you do it with a linked-list, and O(N^2) if you do it with a naive vector, regardless of language or programming style.
      - tux3 5y ago
        Fair enough, though I would argue Rust's Vec being the 'default' data structure plays a big role in non-beginners avoiding that mistake, versus Lisp where you more rarely see people reaching for vectors (though they exist). I have, in fact, never seen Rust code using a linked-list in the wild, though obviously there are many valid uses cases where linked lists beat vectors (and I probably don't need to tell you =]), and surely there are many examples. And the same goes for C++, you don't reach for std::list without a specific reason. Those de-facto 'defaults' in traditional 'vaguely imperative/systems' languages steer people towards different code styles. Of course both have access to all mainstream data structure, but I'd like to think the author does know about the complexity of linked-lists versus vectors, they only made that mistake because they probably don't reach for vectors as often in Common Lisp as someone in Rust would — or presumably they would have quickly gained an innate eye for expensive copies in recursive functions

phoe-krk 5y ago

> the same would be true if the author did this with a C++ std::vector, or a Java ArrayList, or a Python list, or a JavaScript array. ...or, to be fully honest, a Common Lisp VECTOR that is then CONCATENATE'd with a new element at its beginning. As I said in another comment, this isn't the problem of using a given language - it's the problem of using a wrong data structure for the job.

brundolf 5y ago
Exactly. And the fact that it's framed as "well I just wanted a straight comparison, I didn't want to wade too far into idioms and Rust-isms in the first pass" feels disingenuous.

lalaithion 5y ago

The more general view to take from this is that when you program a lot in one language, you get so used to certain performance patterns that you simply write your code in a way that takes advantage of them first try[1]. Peter Norvig's Lisp solution is an optimized solution for Lisp in a lot of little ways. Directly translating an optimized-for-Lisp program into any other language is silly, because you miss out on the optimizations available in that language to an experienced programmer and you lose out doing pointless things which were essential in Lisp.

brundolf 5y ago
I'm arguing that this case stands above that. This isn't some nuance of either language; it's CS 101
- tux3 5y ago
  I was going to argue the same: This isn't Java vs Rust, it's the author's familiarity with Lisps not translating very well to less purely functional languages. Writing an O(N^2) algorithm should give you pause in any imperative language, if you can spot the copy. The author is clearly not a beginner dev, but the mistake here isn't really Rust specific, it's "vaguely imperative systems language" programming patterns
  - brundolf 5y ago
    That's not quite it; it's not really about functional vs imperative (though there's some loose correlation) Common Lisp isn't purely functional (it's arguably the least-functional of the major Lisps), and in fact it has a vector data structure of its own, so you could make the same mistake there if you went out of your way to. Similarly, Rust has a LinkedList in its standard library. This algorithm is simply O(N) if you do it with a linked-list, and O(N^2) if you do it with a naive vector, regardless of language or programming style.
    - tux3 5y ago
      Fair enough, though I would argue Rust's Vec being the 'default' data structure plays a big role in non-beginners avoiding that mistake, versus Lisp where you more rarely see people reaching for vectors (though they exist). I have, in fact, never seen Rust code using a linked-list in the wild, though obviously there are many valid uses cases where linked lists beat vectors (and I probably don't need to tell you =]), and surely there are many examples. And the same goes for C++, you don't reach for std::list without a specific reason. Those de-facto 'defaults' in traditional 'vaguely imperative/systems' languages steer people towards different code styles. Of course both have access to all mainstream data structure, but I'd like to think the author does know about the complexity of linked-lists versus vectors, they only made that mistake because they probably don't reach for vectors as often in Common Lisp as someone in Rust would — or presumably they would have quickly gained an innate eye for expensive copies in recursive functions