parameter selection

[whyrusleeping]

There are several parameters in the hamt that we can tweak depending on what our desired outcomes are. Let's start by brainstorming the metrics, then we can build benchmarks to check the metrics for any given set of parameters.

First, the parameters we have:

• Tree width.
  • The size of the fanout at each layer
  • Currently 256, is 32 in the original HAMT designs. Must be a power of 2.
• arrayWidth
  • the number of elements that get bundled together when a collision happens within a layer.
  • currently 3
  • higher numbers result in denser trees

Next, metrics we would like to see:

• Average tree density (values per node)
• Space overhead of the structure (total serialized size of all nodes / size of keys+values)
• average storage delta size for {a single write, 100 writes, n writes}
  • If i do a single 'Set' on a large tree, how much data do we have to rewrite to bubble up the changes?
• Write performance
  • time to put N nodes into an empty tree
  • time to put N nodes into a tree of size M
  • time to update a single value in a tree of size M
• Read performance
  • Read of a random value
  • iterate through all values