Why is flatmap not using binary search to find the key?

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


Also, DRY

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.


Thanks for the reply. That makes sense.

1 Like