permafrost

Permafrost is a collection of thread-safe, persistent, immutable data structures for Crystal.

An unordered map Pf::Map
An unordered set Pf::Set
An unordered bidirectional map (bimap) Pf::BidiMap.
An unsigned 32-bit integer set Pf::USet32.

Most of the data structures in Permafrost come from my main project, Wirewright. Wirewright is also the main user of Permafrost.

Installation

Add the dependency to your shard.yml:

dependencies:
  permafrost:
    github: homonoidian/permafrost

Run shards install

Usage

See the docs.

Performance

You can run the benchmark file, bench.cr, for a (very dumb and useless) benchmark of the map vs. what we consider the speed-of-light implementation, Hash, and what seems to be our only competitor, Immutable::Map from the wonderful shard Immutable. The latter you'd have to install somehow, maybe by cloning this repo and modifying shard.yml directly.

Note that each benchmark run you'd get (somewhat) different results depending on how good the hash seed was, which is picked by Crystal randomly. I haven't found a way to reliably disable that. If you know how let me know, maybe make a PR or something.

                   add speed of light 228.59  (  4.37ms) (±14.11%)  4.75MB/op    26.60× slower
          add + delete speed of light 152.26  (  6.57ms) (±12.12%)  4.75MB/op    39.93× slower
                  each speed of light   6.08k (164.48µs) (± 0.18%)    0.0B/op          fastest
                          pf::map add   8.54  (117.13ms) (± 8.92%)    98MB/op   712.10× slower
                 pf::map add + delete   4.33  (231.07ms) (± 3.70%)   189MB/op  1404.84× slower
                       pf::map add tx  57.24  ( 17.47ms) (±18.02%)  7.78MB/op   106.22× slower
              pf::map add + delete tx  38.76  ( 25.80ms) (±20.76%)  7.78MB/op   156.84× slower
                         pf::map each 280.95  (  3.56ms) (± 0.70%)    0.0B/op    21.64× slower
                   immutable::map add   3.52  (284.13ms) (±10.84%)   219MB/op  1727.44× slower
          immutable::map add + delete   1.74  (574.02ms) (± 2.66%)   373MB/op  3489.90× slower
         immutable::map add transient   6.26  (159.64ms) (±11.90%)   101MB/op   970.58× slower
immutable::map add + delete transient   3.33  (300.57ms) (± 1.33%)   134MB/op  1827.38× slower
                  immutable::map each   6.40  (156.36ms) (± 2.67%)  87.4MB/op   950.61× slower

The ± numbers being so big smells weird, but the results clearly show the winner!

Again, I picked this run among others because it is the fastest. With a different hash seed, you'll get different results, faster or slower than those presented here.

Development

If you find any errors please let me know or (even better!) fix them yourself and submit a PR.
New methods or quality improvements are welcome, especially if they already exist in Crystal's stdlib.
Optimizations are especially welcome. E.g. Wirewright currently uses Permafrost in extremely hot places. A dozen nanoseconds shaved off of something hot in Permafrost itself would be very nice.

References

Contributing

Fork it (https://github.com/homonoidian/permafrost/fork)
Create your feature branch (git checkout -b my-new-feature)
Commit your changes (git commit -am 'Add some feature')
Push to the branch (git push origin my-new-feature)
Create a new Pull Request

Contributors

Alexey Yurchenko - creator and maintainer