In erl_map.c, https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_map.c#L207C4-L216C3, it is using linear search to find the specific key. Since these keys are sorted, why not use binary search here? Similar in https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_map.c#L2074-L2083
2 Likes
On modern hardware, binary search is nearly always slower for small collections like these (and what constitutes “small” keeps on rising). There might be a point for complex keys where the cost of comparison dominates everything else, but for immediates I’d actually be surprised if binary search was faster in the average case.
A little duplication is fine. The loops are doing different things, and we wouldn’t gain anything from trying to make an abstraction that fits both uses.
7 Likes
Thanks for the reply. That makes sense.
1 Like