stebalien / stash-rs

A fast map for when one doesn't care about choosing the keys.

Stash

Stash is a library for storing items where you need (amortized) O(1) insertion, deletion, and lookups but don't care about the order of the items and don't need to be able to choose the keys.

Please see the API documentation for a more detailed description.

Authors

• Steven Allen [email protected]
• Robbepop [email protected]
• Shane Pearman [email protected]
• Simon Persson [email protected]

stash-rs's Issues

Round trip through serialization breaks determinacy

I think this behavior is acceptable, but it took me a little while to debug what was going on. Maybe a note should be added to the documentation.

Here is a gist that reproduces the behavior: https://gist.github.com/spearman/adfc6d84251169fe6075c89eef73043e

I am using Stash in the game state of a multiplayer game. When a player joins, the server sends the serialization of a an existing Stash, but since this breaks determinism they will no longer update in lock step given the same operations.

Add debug checks for misusage of Stash indices

In insaneinside's crate symtern (https://github.com/insaneinside/symtern) the system checks for misusage of indices into the string interner during debug builds and runs. For release builds these checks are disabled for performance reasons. Yet, this feature enables a very rich debugging experience when using his string interner.

The same techniques could be applied to stash-rs !

The checks are quite simple:

• check if an index passed to methods such as get, get_mut and take was generated by this instance of Stash.
• check if an index passed to methods such as get, get_mut and take was generated before this instance of Stash removed it or was cleared: accesses an "old" entry that is no longer present or has been updated meanwhile.

Both checks could be implemented with tags and timestamps.
For example in debug builds, every instance of Stash receives and stores a unique identifier (which I will call tag: should be u64 for stability purposes). This tag must also be stored for every outgoing index generated by put. This enforces a generic implementation of indices: other people have already suggested this for Stash.
Also every full entry within an instance of a Stash requires a unique timestamp which is again just a number that is incremented for an instance of Stash whenever the user puts a new item into it. This also has to be stored in debug-mode indices generated by put.

With this structure it is then very easy to debug programs for invalid accesses to instances of Stash:

When calling a method such as get, get_mut or take with an index idx the following checks are made:

• idx.tag == self.tag: This ensures that the index was generated by this Stash instance
• idx.timestamp == self[idx].timestamp: This ensures that the entry that is associated with the timestamp of idx has not been updated (e.g. taken and put in again) during the lifetime of idx.

Possible timestamp storage design

To store the lifetimes for every bucket it should be possible to create a separate array which stores a lifetime for every bucket. Whenever a bucket is assigned a new Entry::Full or whenver it is cleared we simply increase the timestamp for that bucket in the Stash. This design makes it easy to adjust the code for debug builds.

Behaviour on clear

After clear has been called on an instance s of Stash all extern indices idx should be invalidated. This can be achived by setting s.tag to a new global unique identifier. No other changes are required besides that.

How are failures handled?

The assertions should be handled with debug_assert! macro. This way the assertions are only enabled for debug builds and the API doesn't need to change to Result<_> types.

Feature gate or not?

This feature could also be provided behind a feature gate instead of being active by default for debug builds.