4 ms·

It seems true to me that working with the Rust borrow checker is eventually fruitful, but this post shows a micro-case where working with lifetimes seems like a

It seems true to me that working with the Rust borrow checker is eventually fruitful, but this post shows a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. There is a part over there that compares: (cons word words) to: let mut partial_solution = words.clone(); partial_solution.push(word); In this particular case this isn't Rust being slow, this is an attempt to compare a O(1) cons operation to a O(n) process of copying a list. Doing this N times results in accidentally quadratic complexity for Rust - no doubt it's slow. I cannot say much more about Rust syntax since I am even more of a Rust newbie than the author - perhaps someone can have some further comments on the quality of the resultant Rust code. Still, the Lisp version can be pushed even further with regards to performance - it still lacks explicit type declarations and I am unsure if the author asked the Lisp compiler to optimize for speed and resolved any notes that the compiler might have produced.

Cu3PO42 5y ago
> It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. I fully agree. In the past year I have worked in Rust a lot and while quarrels with the borrow checker have definitely gotten more and more rare, they still happen occasionally. It's not that the borrow checker presents a reason which I think is incorrect or invalid, it's rather that it's sometimes difficult or just tedious to encode the proof that what you're doing is actually fine. That said, there have been situations in which I was absolutely confident my code would have been fine if it weren't for the meddling borrow checker, but it actually wasn't and it helped me catch bugs. Fortunately there is a bit of an escape hatch: if you want to, you can just start reference counting and get close to the experience you'd have with a proper GC. For example, there's nothing preventing you from implementing a reference counted linked list and writing LinkedList::Cons(word, words)
- nybble41 5y ago
  In this case the linked list is just tracking "breadcrumbs" which mirror the path back up the call chain, so you don't even need reference counting; a simple borrowed reference will do. I put together a version in Rust based on stack-allocated linked lists[0], and the results were promising: on 10 million inputs the Rust version completes in about 40 seconds on my machine, while the Java port (Main2.java in the code; "Java1" from the article IIUC) takes 82 seconds. This Rust version doesn't allocate anything from the heap, apart from loading the dictionary at startup; all the bookkeeping, including the cons cells, is kept on the stack. [0] https://github.com/nybble41/prechelt-phone-number-encoding https://github.com/nybble41/prechelt-phone-number-encoding
  - nybble41 5y ago
    > This Rust version doesn't allocate anything from the heap I lied—the BigUint values used as keys were still being allocated from the heap. Replacing these with Vec<u8> in the HashMap and &[u8] for the lookups brought the time down to about 31 seconds while also simplifying the code and eliminating a dependency. Bypassing the fmt library in the output code shaved off another second.
myWindoonn 5y ago
We can actually go a little deeper. In a famous pair of papers, "CONS should not actually CONS its arguments", Henry Baker argued that (cons) is emblematic of a class of primitive/simple functions which vanish under continuation-passing style, and that LISPs should deliberately be structured around this fact. These papers directly inspired CHICKEN, the first modern fast LISP runtime. This is ignoring many Common Lisp specifics which are relevant to the blog post's original code, but I figured that on this example, the historical microscope is appropriate.
pjmlp 5y ago
Also regarding Lisp, the language might have been born just with List Processing capabilities during its early days, however since the 70's that any proper Lisp supports all common datastructures, including value types, stack allocation and deterministic resource management.
lijogdfljk 5y ago
> It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. Fwiw, my shop uses Rust in some basic web applications and lifetimes are not used in day to day programming. It heavily depends on what you're doing. Are there some applications/libraries/etc where we're using lifetimes? Definitely. But for us they're very niche. AND, perhaps most importantly, even in those you _still_ don't have to. If you're okay with the performance trade off, which we most certainly are (we have some Python usage for example), adding in basic reference counting can be a no-brainer tradeoff. I actually quite like lifetimes. I have some side projects where i use them extensively. But just like standard Generics they're a tool you can use, but that doesn't mean you always should. Just like accepting a `s: &str` instead of `s: S) where S: AsRef<str>` can make your life cleaner and simpler, using `Rc<Foo>` can equally simplify. Just my 2c :) [1]: because we like it, no other reason.. really, a team of ~30.
pizza234 5y ago
I'm confused at why the author is using static mutable variables, which, while sometimes required in Rust, they are at a high risk of design issues. In addition to the design issues, they are also implemented via mutexes, which have overhead - and I don't see threads in the file. EDIT: Even more skeptical. By replacing the ONE/TEN pseudo-static variables with standand/idiomatic local variables (and borrowing them), I get a 10% increase in performance.
- mst 5y ago
  Um, the article mentions that somebody explained to him that was wrong, and he replaced them with something better. This whole article is about "here's a bunch of things I got wrong because I'm not very good at rust and people were kind enough to help me fix them and I'm going to show you the fixes", I'm not sure what there is to be skeptical about here?
  - pizza234 5y ago
    I don't see much (if any) value in this article. The code was very unidiomatic to start with, and the issues are not just a matter of style - they're very substantial, and the code is still unidiomatic. At least one of the conclusions through the article is wrong - the author uses a vector of String references, concluding that the logic can't be easily simplified (because lifetimes are required). This data type is wrong, as owned String's should be used, which don't require any maintenance. This wrong conclusion has actually the side effect of describing a language complexity that doesn't exist (I'm certainly not arguing that Rust is complex, but credit should be due to cases where such complexity doesn't apply). Reconnecting to the beginning, I'm not sure what the value is supposed to be. Benchmark unidiomatically implemented updated to still unidiomatic implementation and flawed algorithm, with at least one improper conclusion, gives results that are not meaningful?
steveklabnik 5y ago
> seems like a lot mental overhead with little gain Now, I have bias, of course, and I do think this is the relationship at the start, but for me personally, it's the opposite. I never need to think about lifetimes. That's what the compiler is for. I don't think about it. If I make a mistake, the compiler tells me where I made a mistake. I fix it, and then I move on. Huuuuuge YMMV here, of course. But when I'm reading C code, the mental overhead of keeping track of all of this is massive. But it's generally nonexistent in Rust. That's why we pass this thinking off to the machine! Humans get tired, they get sloppy, they may even be intoxicated in some form. Compilers do not. (They do have bugs though...)
nestorD 5y ago
One thing I love about Rust is that, while the code is accidentaly quadratic, it is explicit when looking at the code and seing the call to `clone` which makes it much harder to produce those behaviour than in languages where copies can happen behind the scene (C++ is often guilty of that).
pizza234 5y ago
Posted in a sibling comment, but I repeat it because I think it's a very important point. > I cannot say much more about Rust syntax since I am even more of a Rust newbie than the author - perhaps someone can have some further comments on the quality of the resultant Rust code. The author is using an improper data type - a vector of borrowed strings (`Vec<&String>`), which forces the dev to use lifetimes. The owned version, `Vec<String>` doesn't suffer from this problem. More in general, this is a lack of experience problem - designing ownership is difficult at the beginning. And there's no problem with it! But don't publish a (micro)benchmark, please :) In particular, the author's conclusion on the necessity of lifetimes: > This means that, yes, writing efficient code in Rust requires a lot of forethought. In this case, our tiny modification to use a mutable Vec actually requires us to only deal with strings whose life times match or exceed that of our Vec. assigns a complexity to Rust that in this case doesn't exist. Rust is complex, but this is not one of those cases.
- brabel 5y ago
  You keep repeating your wrong argument, so please allow me to correct you. If you knew any Rust, you would immediately see that the owner of the words is the HashMap, which represents the dictionary of valid words to use. If the author had used a `Vec<String>` to represent the possible solutions, every single String would need to be either cloned or removed from the dictionary. A String cannot have two owners. This is basic Rust. If you disagree, please show me the magic code that can get around that.
  - pizza234 5y ago
    Here's the diff in Pastebin: https://pastebin.com/wT8gXtBJ https://pastebin.com/wT8gXtBJ One just clones the single word, rather than cloning the whole words vector. Something that can also be improved in the code above (I've done the most minimal change) is to move the Vector instantiation outside the for loop, since print_translations() guarantees that the vector has the same content before/after invocation.
    - brabel 5y ago

Cu3PO42 5y ago

> It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. I fully agree. In the past year I have worked in Rust a lot and while quarrels with the borrow checker have definitely gotten more and more rare, they still happen occasionally. It's not that the borrow checker presents a reason which I think is incorrect or invalid, it's rather that it's sometimes difficult or just tedious to encode the proof that what you're doing is actually fine. That said, there have been situations in which I was absolutely confident my code would have been fine if it weren't for the meddling borrow checker, but it actually wasn't and it helped me catch bugs. Fortunately there is a bit of an escape hatch: if you want to, you can just start reference counting and get close to the experience you'd have with a proper GC. For example, there's nothing preventing you from implementing a reference counted linked list and writing LinkedList::Cons(word, words)

nybble41 5y ago
In this case the linked list is just tracking "breadcrumbs" which mirror the path back up the call chain, so you don't even need reference counting; a simple borrowed reference will do. I put together a version in Rust based on stack-allocated linked lists[0], and the results were promising: on 10 million inputs the Rust version completes in about 40 seconds on my machine, while the Java port (Main2.java in the code; "Java1" from the article IIUC) takes 82 seconds. This Rust version doesn't allocate anything from the heap, apart from loading the dictionary at startup; all the bookkeeping, including the cons cells, is kept on the stack. [0] https://github.com/nybble41/prechelt-phone-number-encoding https://github.com/nybble41/prechelt-phone-number-encoding
- nybble41 5y ago
  > This Rust version doesn't allocate anything from the heap I lied—the BigUint values used as keys were still being allocated from the heap. Replacing these with Vec<u8> in the HashMap and &[u8] for the lookups brought the time down to about 31 seconds while also simplifying the code and eliminating a dependency. Bypassing the fmt library in the output code shaved off another second.

myWindoonn 5y ago

We can actually go a little deeper. In a famous pair of papers, "CONS should not actually CONS its arguments", Henry Baker argued that (cons) is emblematic of a class of primitive/simple functions which vanish under continuation-passing style, and that LISPs should deliberately be structured around this fact. These papers directly inspired CHICKEN, the first modern fast LISP runtime. This is ignoring many Common Lisp specifics which are relevant to the blog post's original code, but I figured that on this example, the historical microscope is appropriate.

pjmlp 5y ago

Also regarding Lisp, the language might have been born just with List Processing capabilities during its early days, however since the 70's that any proper Lisp supports all common datastructures, including value types, stack allocation and deterministic resource management.

lijogdfljk 5y ago

> It seems true to me that working with the Rust borrow checker is eventually fruitful, but there is a micro-case where working with lifetimes seems like a lot mental overhead with little gain, compared to a built-in garbage collector available in Lisp. Fwiw, my shop uses Rust in some basic web applications and lifetimes are not used in day to day programming. It heavily depends on what you're doing. Are there some applications/libraries/etc where we're using lifetimes? Definitely. But for us they're very niche. AND, perhaps most importantly, even in those you _still_ don't have to. If you're okay with the performance trade off, which we most certainly are (we have some Python usage for example), adding in basic reference counting can be a no-brainer tradeoff. I actually quite like lifetimes. I have some side projects where i use them extensively. But just like standard Generics they're a tool you can use, but that doesn't mean you always should. Just like accepting a `s: &str` instead of `s: S) where S: AsRef<str>` can make your life cleaner and simpler, using `Rc<Foo>` can equally simplify. Just my 2c :) [1]: because we like it, no other reason.. really, a team of ~30.

pizza234 5y ago

I'm confused at why the author is using static mutable variables, which, while sometimes required in Rust, they are at a high risk of design issues. In addition to the design issues, they are also implemented via mutexes, which have overhead - and I don't see threads in the file. EDIT: Even more skeptical. By replacing the ONE/TEN pseudo-static variables with standand/idiomatic local variables (and borrowing them), I get a 10% increase in performance.

mst 5y ago
Um, the article mentions that somebody explained to him that was wrong, and he replaced them with something better. This whole article is about "here's a bunch of things I got wrong because I'm not very good at rust and people were kind enough to help me fix them and I'm going to show you the fixes", I'm not sure what there is to be skeptical about here?
- pizza234 5y ago
  I don't see much (if any) value in this article. The code was very unidiomatic to start with, and the issues are not just a matter of style - they're very substantial, and the code is still unidiomatic. At least one of the conclusions through the article is wrong - the author uses a vector of String references, concluding that the logic can't be easily simplified (because lifetimes are required). This data type is wrong, as owned String's should be used, which don't require any maintenance. This wrong conclusion has actually the side effect of describing a language complexity that doesn't exist (I'm certainly not arguing that Rust is complex, but credit should be due to cases where such complexity doesn't apply). Reconnecting to the beginning, I'm not sure what the value is supposed to be. Benchmark unidiomatically implemented updated to still unidiomatic implementation and flawed algorithm, with at least one improper conclusion, gives results that are not meaningful?

steveklabnik 5y ago

> seems like a lot mental overhead with little gain Now, I have bias, of course, and I do think this is the relationship at the start, but for me personally, it's the opposite. I never need to think about lifetimes. That's what the compiler is for. I don't think about it. If I make a mistake, the compiler tells me where I made a mistake. I fix it, and then I move on. Huuuuuge YMMV here, of course. But when I'm reading C code, the mental overhead of keeping track of all of this is massive. But it's generally nonexistent in Rust. That's why we pass this thinking off to the machine! Humans get tired, they get sloppy, they may even be intoxicated in some form. Compilers do not. (They do have bugs though...)

nestorD 5y ago

One thing I love about Rust is that, while the code is accidentaly quadratic, it is explicit when looking at the code and seing the call to `clone` which makes it much harder to produce those behaviour than in languages where copies can happen behind the scene (C++ is often guilty of that).

pizza234 5y ago

Posted in a sibling comment, but I repeat it because I think it's a very important point. > I cannot say much more about Rust syntax since I am even more of a Rust newbie than the author - perhaps someone can have some further comments on the quality of the resultant Rust code. The author is using an improper data type - a vector of borrowed strings (`Vec<&String>`), which forces the dev to use lifetimes. The owned version, `Vec<String>` doesn't suffer from this problem. More in general, this is a lack of experience problem - designing ownership is difficult at the beginning. And there's no problem with it! But don't publish a (micro)benchmark, please :) In particular, the author's conclusion on the necessity of lifetimes: > This means that, yes, writing efficient code in Rust requires a lot of forethought. In this case, our tiny modification to use a mutable Vec actually requires us to only deal with strings whose life times match or exceed that of our Vec. assigns a complexity to Rust that in this case doesn't exist. Rust is complex, but this is not one of those cases.

brabel 5y ago
You keep repeating your wrong argument, so please allow me to correct you. If you knew any Rust, you would immediately see that the owner of the words is the HashMap, which represents the dictionary of valid words to use. If the author had used a `Vec<String>` to represent the possible solutions, every single String would need to be either cloned or removed from the dictionary. A String cannot have two owners. This is basic Rust. If you disagree, please show me the magic code that can get around that.
- pizza234 5y ago
  Here's the diff in Pastebin: https://pastebin.com/wT8gXtBJ https://pastebin.com/wT8gXtBJ One just clones the single word, rather than cloning the whole words vector. Something that can also be improved in the code above (I've done the most minimal change) is to move the Vector instantiation outside the for loop, since print_translations() guarantees that the vector has the same content before/after invocation.
  - brabel 5y ago