search

rust-scraper / ego-tree

Vec-backed ID-tree
https://docs.rs/ego-tree
ISC License
45 stars 16 forks source link

Use NonZeroUsize inside NodeId #16

Closed SimonSapin closed 5 years ago

SimonSapin commented 5 years ago

This allows Option<NodeId> to be no larger than usize, and saves 32 bytes of memory per node.

SimonSapin commented 5 years ago

This library looks really nice! This PR is a memory use improvement that you might be interested in.

It adds some CPU instructions for those + 1 and - 1, but hopefully that cost is small enough. A way to avoid that could be to have a dummy unused node at index zero. But then we’d have to come up with a dummy T value for it (requiring T: Default just for this seems unfortunate), or unsafely leave it uninitialized.

In the same spirit, it looks like NodeRef could also be made smaller by replacing its node field by a node() method similar to that of NodeMut. Since indexing is unchecked, I think the only cost would be the extra pointer indirection (NodeRef.tree → Tree.vec.ptr → Node v.s. NodeRef.node → Node). NodeRef may seem small already (relatively to, say, Node<T>) but in code that passes it around a lot, those copies/moves can add up.

SimonSapin commented 5 years ago

But then we’d have to […] unsafely leave it uninitialized.

On further thought this isn’t so bad, with Vec::with_capacity + set_len. Let me do that instead :)

causal-agent commented 5 years ago

It's been ages but I'd like to merge this one since it's much less code and more convincingly correct. The branch is gone however so I can't reopen this PR, but I'm guessing I can grab the commits from GitHub some way.