3 ms·

> I would expect an idiomatic implementation to drastically go down in lines of code Can you give an example of where something in the project could be, say, 2

> I would expect an idiomatic implementation to drastically go down in lines of code Can you give an example of where something in the project could be, say, 20 lines of code instead of 30? https://github.com/quick-lint/cpp-vs-rust/tree/master/rust https://github.com/quick-lint/cpp-vs-rust/tree/master/rust

orlp 4y ago
Well, for example the libs/container/src/linked_vector.rs is very overcomplicated and fragile using unsafe code. Ultimately what you want is for references to remain stable on push/pop, which can be achieved simply with a Vec<Vec<T>>. It's also idiomatic for push to return nothing and for pop to return the item (if any - and not crash if not empty!). Similarly back should return an Option instead of crashing on empty (and is called last in Rust). for_each is also unidiomatic - it's much more useful to provide an iterator over the collection. Here's an example implementation in ~60LOC instead of ~200: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=602a22d1de3e7a0487bac522a161f253 https://play.rust-lang.org/?version=nightly&mode=debug&editi...
- vegerot 4y ago
  Thank you for actually suggesting something! Many people say “this is unidiomatic/slow/unoptimal” but nobody is giving specifics. Thanks :) btw the author is looking to improve the Rust version and is accepting contributions in that repo if you wanna improve the experiment
- magicalhippo 4y ago
  For those of us less versed in Rust, from what I can gather the reason the provided Vec<Vec<T>> implementation works is that the Vec implementation guarantees[1] no reallocation happens when created with a sufficient capacity, and that the elements live on the heap. This means it's safe for the outer Vec to be reallocated. That said, the pop implementation seems faulty in that it does not appear to deallocate empty chunks. Does Rust have any non-obvious magic here? [1]: https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees
  - orlp 4y ago
    > That said, the pop implementation seems faulty in that it does not appear to deallocate empty chunks. Does Rust have any non-obvious magic here? No, the only magic here is my utter lack of testing for throwaway HN code :) A corrected implementation would be: pub fn pop(&mut self) -> Option<T> { let last = self.chunks.last_mut()?; let ret = last.pop()?; if last.is_empty() { self.chunks.pop(); } Some(ret) } This is only correct if we maintain the invariant that we do not keep any empty chunks around, but the rest of the implementation does not violate this.

orlp 4y ago

Well, for example the libs/container/src/linked_vector.rs is very overcomplicated and fragile using unsafe code. Ultimately what you want is for references to remain stable on push/pop, which can be achieved simply with a Vec<Vec<T>>. It's also idiomatic for push to return nothing and for pop to return the item (if any - and not crash if not empty!). Similarly back should return an Option instead of crashing on empty (and is called last in Rust). for_each is also unidiomatic - it's much more useful to provide an iterator over the collection. Here's an example implementation in ~60LOC instead of ~200: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=602a22d1de3e7a0487bac522a161f253 https://play.rust-lang.org/?version=nightly&mode=debug&editi...

vegerot 4y ago
Thank you for actually suggesting something! Many people say “this is unidiomatic/slow/unoptimal” but nobody is giving specifics. Thanks :) btw the author is looking to improve the Rust version and is accepting contributions in that repo if you wanna improve the experiment
magicalhippo 4y ago
For those of us less versed in Rust, from what I can gather the reason the provided Vec<Vec<T>> implementation works is that the Vec implementation guarantees[1] no reallocation happens when created with a sufficient capacity, and that the elements live on the heap. This means it's safe for the outer Vec to be reallocated. That said, the pop implementation seems faulty in that it does not appear to deallocate empty chunks. Does Rust have any non-obvious magic here? [1]: https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees
- orlp 4y ago
  > That said, the pop implementation seems faulty in that it does not appear to deallocate empty chunks. Does Rust have any non-obvious magic here? No, the only magic here is my utter lack of testing for throwaway HN code :) A corrected implementation would be: pub fn pop(&mut self) -> Option<T> { let last = self.chunks.last_mut()?; let ret = last.pop()?; if last.is_empty() { self.chunks.pop(); } Some(ret) } This is only correct if we maintain the invariant that we do not keep any empty chunks around, but the rest of the implementation does not violate this.