Add benchmarks for checking CHAMP memory usage

[arximboldi]

The exection of these is not automated yet. We suggest running them with:

  valgrind --tool=massif --detailed-freq=1 --max-snapshots=1000 <BENCHMARK>

The output file can then be studied with a tool like massif-visualizer (you may install it with nix-shell -p massif-visualizer).

These are some sample outputs:

set-memory-lin-string-long

This one shows the massive effects of structural sharing, when we are interested in taking multiple copies of a data-structure (snapshots). We produce a map of N 2^18 (~250K) strings and then we produce 128 updates, taking a "snapshot" on every step.

We see that for std::map and std::unordered_map (the two first "peaks"), after the initial container is built, memory usage (and time!) grows in proportion to N for every new item added.

With Immer at verious configurations (all the other "peaks"), a neglible memory or time cost is produced for these 128 snapshot-based updates.

set-memory-basic-unsigned

In this graph we simply produce a very big set of integers (N = 2^24 or ~16 M elements). This can help how much memory is wasted by the data-structure itself.

We see that std::map and std::unordered_map (the two first peaks) waste more memory than Immer (except with B=2, third peak).

We also see that B=5 (before last peak) which is the default in Immer, is optimal memory usage.

---

FYI @omer-s @harryhk

[codecov-commenter]

Codecov Report

Merging #243 (ffef271) into master (58036b4) will not change coverage. The diff coverage is n/a.

@@           Coverage Diff           @@
##           master     #243   +/-   ##
=======================================
  Coverage   90.50%   90.50%           
=======================================
  Files         119      119           
  Lines       12109    12109           
=======================================
  Hits        10959    10959           
  Misses       1150     1150           

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.