[erlang-questions] Maps

[Björn-Egil Dahlberg]

On 2013-05-10 05:03, Richard A. O'Keefe wrote:
> On 9/05/2013, at 8:10 PM, Max Lapshin wrote:
>
>> Richard. Would you, kindly, tell: where is the difference between maps
>> and frames?
>>
>> As far as I understand, it is not about syntax, it is about internal
>> way of storing data?
> I thought I already had, but here goes.
>
> There is one central semantic difference, which leads to two
> others.
>
> (U) What do you want to optimise the design for?
>
>      Frames are optimised (pared to the bone, in fact) for use in
>      record-like ways.  They are somewhere between pathetic and
>      hopeless as general purpose dictionaries.
>
>      Maps optimised for service as general-purpose dictionaries.
>      They are somewhere between almost usable and pathetic for
>      record-like uses.
>
>      I do not believe that it is possible to design a data structure
>      which is *good* at both tasks.  I suspect that it is possible to
>      prove this, but I must admit I haven't tried.
>
>      THIS is the reason that Björn-Egil Dahlberg was able to sneer at
>      frames as "just a replacement".  I don't try to build perpetual
>      motion machines.  I don't try to square the circle with ruler and
>      compass.  I don't try to design bottle-openers that make good
>      chisels.  And given two sets of conflicting requirements (even if
>      the sets overlap substantially), I don't try to satisfy them both
>      with a single data structure.  (Using a Java ArrayList as a queue
>      is *possible*, but stupid.)

Richard, I'm sorry that you feel that way. It was not my intention to 
"sneer" at Frames. I merely stated that Frames is intended as a record 
replacement whereas Maps is not.

I also said: "The one suggestion that stands out is of course the Frames 
proposal from Richard O'Keefe. It is the most complete proposal I've 
seen and is very well thought out." .. but I wanted something else, 
hence the EEP.

> As for implementation, Björn-Egil Dahlberg wrote:
>
>> Current prototypes stems from using sparse tuples in a
>> HAMT-like data structure and tuple-like data structures.
>> The HAMT-like data structure is discontinued and will be
>> replaced by some ordered tree.
> The HAMT-like data structure for OCAML that I've looked at
> takes *at least* four words for every key/value association.
> (I have been able to find plenty of numbers for the *speed*
> of HAMTs but nothing for the *space* they need other than a
> claim of "small".)  That's not necessarily the same thing,
> and the "tuple-like" part makes me wonder if something much
> cleverer is being done.
I don't know how OCAML does it but that word count seems excessive.

Now, the HAMT impl. is discontinued because it was decided an ordered 
structured was going to be used. But,
here is what I had i mind:

First things first. HAMT is a functional structure, meaning no 
destructive updates.

In my implementation I used the structure of an radix tree. In the tree 
we have three types of nodes,
leaf nodes, tuple nodes and "sparse-tuple" nodes.

Tuple nodes are a saturated "sparse-tuple". It is a plain tuple of fixed 
size. Each element in the tuple is a leaf node, tuple node or 
"sparse-tuple".

Leaf nodes are conses with key values [K|V]. Leaf nodes not are not 
really necessary since we can save KVs directly in the other nodes but 
it simplifies implementation and was used in the prototype. Storing KVs 
directly in tuple and "sparse-tuple" nodes saves one word per KV but it 
also doubles the number of words that needs copying in each update. This 
boils down to a trade-off between speed and memory.

"Sparse-tuple" nodes is an internal construct, but a real type, only 
used in this data structure. Elements may be indexed 1 - N but it would 
*not* take N + 1 words in memory. Instead a mapping function is used to 
index elements. We also need the information of which elements in the 
sparse tuple are set. This information takes about one word. The number 
of words required depends on the node size (which is fixed), but can be 
placed in the header of this type. So the memory size of a sparse tuple, 
indexable 1 - N with only two elements, takes 3 - 4 words (3 if the 
mapping is in the header). N is typically 16 or 32.

What this means is that we can take a hashing approach to this but still 
keep the tree compact. I believe this is meant to be the "small" memory 
footprint.

The key to be used to traverse tree is hashed (using the same algorithm 
as phash2) which produces an 32 bit integer. We index the tree by using 
a set of bits from this hash at each level. The number of bits used is 
dependent on the fixed size of the nodes. In my prototype i used nodes 
of size 32. For each level in the tree we use 5 bits of the hash to 
index down in the tree. When the hash is exhausted we produce an new 
hash but add the level as well, ex. phash([Lvl|Key]).

When we update a value in the tree only the nodes in the path are 
updated. "sparse-tuples" reduces the amount of copying.

The space this tree requires depends on the hashing algorithm (and the 
keys that are hashed). Some "management size" is required ofc. The root 
of this structure may be implemented in several ways. For instance we 
can consider a variant of the "sparse-tuple" as the root. The management 
size requirement would be 2 words, a header defining the type and 
keeping the mapping, and a Eterm for the number of entries in the tree. 
If we optimize for space we would require one word header per node in 
the tree, the rest of the elements are key/values. I have no exact value 
for words/pair but I think you get it.

It also worth noting that,
   * the tree would be shallow,
   * only one key comparison is done while traversing the tree (leaf node).

It is also worth noting that the mapping function in "sparse-tuples" is 
an expensive one. We need hamming weight of a bitfield. This can be done 
in newer hardware using a popcount instruction. Doing popcount in Erlang 
code is doable but not very efficient unless compiler/runtime aided.

This whole explanation serves as one big parenthesis since HAMT will not 
be used. Space conservation, key-sharing and ordering requirements were 
added.

>    However, we're told that's going "and
> will be replaced by some ordered tree".  Suppose you have a
> 2-3-4 tree.  We can play SML/Mercury-style games to move the
> size of a node into the pointer to it, so we
>
> 2-node: C1 K1 V1 C2                    4   words/pair
> 3-node: C1 K1 V1 C2 K2 V2 C3           3.5 words/pair
> 4-node: C1 K1 V1 C2 K2 V2 C3 K3 V3 C4  3.3+words/pair
>
> So it's fair to say that this would take *roughly* 3.5 words
> per field.
>
> Playing similar move-the-balance-info-into-the-pointers games
> would let us do red-black trees or AVL trees in 4 words/pair.
>
> There are other games one can play, at the price of more
> complicated code, where we take advantage of the leaves of
> a 2-3-4 tree being at the same depth, so that leaf nodes
> are K1 V1
>   or K1 V1 K2 V2
>   or K1 V1 K2 V2 K3 V3
>   or K1 V1 K2 V2 K3 V3 K4 V4
> and the tree as a whole is roughly 2.3 words per pair.
>
> I don't know what exactly Björn-Egil Dahlberg has in mind,
> but if we charge 3 words per key/value association, it's
> not likely that we're overestimating the space cost.

Maps would have a two tier approach.
Tier 1 would have an approach much like your frames { {K1, ..., Kn}, V1, 
..., Vn }, essentially two tuples where keys are ordered in term order.

When the number of entries reaches a certain point the cost of doing 
business becomes too great. Searching and the garbage generated by 
updates costs more than space saving earns us. Typically 30 - 50 
entries. At this point the structure is converted to some ordered tree, 
Tier 2. I say "some" ordered tree because it is still undecided what is 
suitable here. I think it is fair to say that space cost here would be 3 
- 4 words per pair. I would view Tier 1 as an optimization of Tier 2 for 
few entries.

I would also like to point out that when this point is reached, space is 
not our primary concern.

Regards,
Björn-Egil