Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use hash maps exclusively in storage. #66

Closed
olson-sean-k opened this issue Nov 17, 2020 · 1 comment
Closed

Use hash maps exclusively in storage. #66

olson-sean-k opened this issue Nov 17, 2020 · 1 comment

Comments

@olson-sean-k
Copy link
Owner

olson-sean-k commented Nov 17, 2020

This issue completely contradicts #16 and the title just about says it all. 😛

Effective slot map implementations like those found in the slotmap crate have some limitations that are difficult (expensive) to work around. Mainly, keys are entirely opaque and their generation is intrusive, meaning that it relies on embedded structures in the slot map that must be mutated. Shrinking the allocation used to store items invalidates keys and requires rekeying (as seen in #19).

In #16, I presumed that slot maps would have better performance than hash maps, but I never tested this. I've recently done some preliminary testing using variations on this benchmark and hash maps using the AHash function seem to consistently beat slot maps by a 25% margin. I've tested this against various slot map variants, different iteration sizes, and different subdivision depths.

One benchmark is certainly not enough to definitively claim that hash maps will yield better general performance! However, these results are still promising and suggest that hash maps may not be trounced by slot maps in this application. Importantly, hash maps have additional useful properties that slot maps lack.

  1. Hash maps can be resized trivially (though they generally require memory overhead).
  2. Hash maps have stable keys.
  3. Keys are generated separately from hash maps.
  4. HashMap supports non-Copy items on stable Rust.

The journaling described in #19 becomes trivial to implement using exclusively hash maps. Providing a shrink_to_fit API for MeshGraph would become much simpler and more efficient, as it would not require rekeying. Cloning becomes trivial to implement, but rekeying may still be a good idea to avoid identical keys between independent graphs.

I plan to continue some testing.

@olson-sean-k
Copy link
Owner Author

c483dcb removes slot maps and parameterizes HashStorage to support both dependent and independent storage. Crucially, the storage module remains reasonably flexible, so if this turns out to be the wrong call, then it should be possible to introduce additional storage types.

d33539c and 3f55673 are quick wins as a result of this change. This (possibly meaningless) benchmark improved substantially.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant