3 ms·

> 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

> 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.

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.