Why is finding data in flatmap traversal?

Hi all
A problem arose when I was looking at ‘erl_maps.c’.
Why do you keep order when adding new elements to the flatmap, but still find the data by traversing instead of using a binary search, is it cache optimization?

2 Likes

We keep the keys sorted to optimize matching out multiple elements at once from a map. For example:

#{key1 := Value, key2 := Value2, key3 := Value} = Map

With sorted keys, a single linear traversal can match out all values. The code is found in beam_jit_map_elements() in beam_jit_common.c.

A similar optimization is possible when updating multiple elements at once. For example:

Map#{key1 := NewValue1, key2 := NewValue2} 

(The update code is found in beam_common.c)

The reason that we don’t do a binary search when looking up a single key is that testing two atoms for equality is faster than comparing whether an atom is smaller than another atom. It would probably be slower to do a binary search even for the largest possible small map (with 32 elements).

2 Likes