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

Replace hash maps with slot maps in storage. #16

Closed
olson-sean-k opened this issue Aug 13, 2018 · 3 comments
Closed

Replace hash maps with slot maps in storage. #16

olson-sean-k opened this issue Aug 13, 2018 · 3 comments

Comments

@olson-sean-k
Copy link
Owner

olson-sean-k commented Aug 13, 2018

Consider replacing the use of HashMap with a slot map in Storage. This could improve performance (benchmarks?). This crate looks promising.

However, edges currently use keys built from their corresponding vertex keys, which is incompatible with slot maps (because it requires being able to specify the key). Examine this pattern to see if it can be removed or modified or if continuing to use HashMap for edges is a better approach.

@olson-sean-k
Copy link
Owner Author

It may be difficult to use both kinds of collections (slot maps and hash maps) together, because abstracting over iterators is not currently possible in Rust. If traits are used to abstract storage, then it is no longer possible to expose iterators without resorting to trait objects, boxing, and dynamic dispatch. I made some good progress on this, but I'd really like to avoid boxing iterators, as they are very commonly used and could present a real performance penalty (no benchmarks though, so I can't be too sure).

This also affects issue #17 for which I have been using the same branch. It's probably worth mentioning that associated type constructors could really help with this, as they would allow storage to be abstracted behind a trait with iterators and all.

@olson-sean-k
Copy link
Owner Author

There is currently a working example of this on the storage branch. Unfortunately, it requires that storage iterators are boxed, so direct iteration over a MeshGraph requires a heap allocation. As already noted, once GATs land (presumably later this year), boxing will no longer be necessary.

Abstracting containers is used here to allow HashMap and SlotMap (or HopSlotMap) to be used to power Storage without needing specialized code. This allows for independent O(1) arc queries, which is a core assumption in MeshGraph's design.

@olson-sean-k
Copy link
Owner Author

This work has landed in ba64094. This better abstracts storage and introduces slot maps. There are two points to keep in mind though:

  • Due to a limitation of the slotmap crate, graph geometry types must now implement Copy. I don't expect this to be an issue, but ideally Clone would be enough. See this issue.
  • Until GATs land in stable Rust, this change requires boxing iterators to put them behind StorageProxy. This requires an allocation whenever iterating over some topology in a graph.

I'll close this for now and may open additional issues for followup work.

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