Reimplement axmap_next_free() to prevent distribution skew
authorMichael Kelley <mikelley@microsoft.com>
Fri, 17 Aug 2018 19:02:58 +0000 (12:02 -0700)
committerMichael Kelley <mikelley@microsoft.com>
Fri, 17 Aug 2018 19:02:58 +0000 (12:02 -0700)
commitb9304c5be4efabebdc4d8bf649d7239bf8af986e
treeb7f7eb963bd52785b4e324c5135c68061623f97e
parent9ee669faa39003c2317e5df892314bcfcee069e3
Reimplement axmap_next_free() to prevent distribution skew

New algorithm starts the search at the specified bit, and only
looks forward (higher index) for a free bit, wrapping around the
end of the map if necessary.  This avoids a distribution skew in
the current algorithm where the low order 5 or 6 bits of the
replacement address tend toward zero.

The first_free cached value is not updated or used. But performance
of the new algorithm is marginally faster than the old algorithm
when measured on a 200 million entry map that is half full,
averaged across searches starting with each of the 200 million
entries.

A separate commit adds new tests to t/axmap.c to confirm the
correct behavior in a variety of situations and edge cases.
lib/axmap.c