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

2 Likes

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.

7 Likes

Thanks for the reply. That makes sense.

1 Like