Skip to content
A faster Map, augmented with Merkle Trees.
Elixir
Branch: master
Clone or download
Latest commit efd9de7 Jun 20, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.circleci Run CI on circleci Jun 14, 2019
bench Fix compiler warning in test Jun 13, 2019
config Initial commit Apr 10, 2019
lib Update README.md Jun 20, 2019
test Recursion is faster than Enum.map Jun 20, 2019
.formatter.exs Initial commit Apr 10, 2019
.gitignore Initial commit Apr 10, 2019
README.md Update readme Jun 20, 2019
mix.exs Bump version to 0.2.0 Jun 14, 2019
mix.lock Prefer `:erlang.phash2`. Solves #1. May 20, 2019

README.md

MerkleMap

MerkleMap is an augmented "plain" Map. Certain operations are faster, and others are slower. MerkleMap also requires more memory, so be aware of this.

MerkleMap is almost a drop-in replacement for Map. It has the same functions, with the following additions:

  • MerkleMap.diff_keys/2 returns the keys that differ between two merkle maps.
  • MerkleMap.prepare_partial_diff/2 prepares a partial diff.
  • MerkleMap.continue_partial_diff/3 continues the partial diff.
  • MerkleMap.update_hashes/1 updates the hashes in the merkle map.

When mutating the merkle map, hashes are not automatically updated. Hashes must be updated manually. This is both for performance, but also to keep function signatures from getting too silly. Functions that accept two merkle maps (eg, merge/2) will require that you have run update_hashes/1 on both input maps, or an ArgumentError will be raised.

prepare_partial_diff/2 and continue_partial_diff/3 are built for use when comparing two maps that are not present in the same process or perhaps not even on the same node. By sending and comparing only a part of the merkle tree in each step, it is possible to send much less traffic back and forth. This is especially a concern for large maps.

Benchmarks

##### With input 100_000 #####                                                              
Name                             ips        average  deviation         median         99th %
merkle_map_not_equal_2       35.27 M     0.00003 ms±100268.45%           0 ms           0 ms
merkle_map_equal_2           26.76 M     0.00004 ms ±98106.44%           0 ms           0 ms
map_put_3                    13.87 M     0.00007 ms  ±8711.21%           0 ms     0.00133 ms
merkle_map_put_3            0.0798 M      0.0125 ms  ±3058.31%     0.00723 ms      0.0130 ms
merkle_map_merge_2          0.0370 M      0.0270 ms  ±2246.31%      0.0162 ms      0.0338 ms
map_not_equal_2            0.00099 M        1.01 ms     ±7.78%        1.00 ms        1.37 ms
map_equal_2                0.00094 M        1.06 ms    ±12.97%        1.02 ms        1.68 ms
map_merge_2                0.00059 M        1.71 ms    ±34.77%        1.62 ms        2.59 ms

Installation

This package can be installed by adding merkle_map to your list of dependencies in mix.exs:

def deps do
  [
    {:merkle_map, "~> 0.2.0"},
  ]
end

The docs can be found at https://hexdocs.pm/merkle_map.

You can’t perform that action at this time.