Improvement idea

[MCJOHN974]

I didn't implement and benchmark this, but it potentially could be interesting:

Let's have two arrays instead of one:

    pairs0: [MaybeUninit<(K, V)>; N],    // for keys whose first bit is 0
    pairs1: [MaybeUninit<(K, V)>; N],    // for keys whose first bit is 1

The idea under them is pretty simple -- in the first array we will store pairs, where first (or any other fixed) bit is 0, the rest -- in the other.

My intuition why it would work:

• extracting first bit sounds as relatively cheap operations, something like just one BITAND and one CMP native instructions, while it can save as much as N / 2 iterations in some cases.
• even if it don't help, and all data unfortunately went to same bucket, it generates much smaller overhead, comparing to profit it makes in positive scenarios.
• probably taking first bit of structure is not so bad "hash function" and it will be relatively a lot of positive scenarios (for example if key is an integer, which is relatively often used as a key, it should pretty good).

Some thoughts about good implementation:

• Don't keep two arrays in reality, just assume that numbers with first bit 0 are in first half of the array
• Maybe it will worth to use this logic only for big micromaps (size 128, 64, probably 32)
• Maybe it will worth to use this logic only for Sized structs, and even for structs which have small size (not bigger than 8 bytes???)

Did someone tested such approach? Maybe any analogues you benchmarking against?