stebalien / stash-rs Goto Github PK
View Code? Open in Web Editor NEWA fast map for when one doesn't care about choosing the keys.
Home Page: http://stebalien.com/projects/stash/
License: Other
A fast map for when one doesn't care about choosing the keys.
Home Page: http://stebalien.com/projects/stash/
License: Other
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.
stash-rs
!The checks are quite simple:
index
passed to methods such as get
, get_mut
and take
was generated by this instance of Stash
.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 put
s 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
instanceidx.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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.