3 ms·
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 bo
by 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.