Patricia said:
I would recommend comparing its performance to a linear search with the
data in descending order of historical access frequency.
Agreed. Besides the branch-prediction behavior, binary search can
suffer from locality-of-reference performance issues, though that's
not likely to be a problem with Roedy's small arrays. But in general,
on modern systems, binary search may perform much worse (relative to
linear) than algorithmic complexity suggests.
You could implement the latter constraint (data in descending order of
access) dynamically using a move-to-front list, though you'd want a
data structure that offers cheap insertion at the front. And if you
need multithreaded access to the list that would also complicate
performance. (At first glance I think you can do it locklessly with a
linked list, but I'd want to review that rather more carefully before
using it.)
On retrieval, a MTF list moves the retrieved element to the front of
the list. So over time frequently-accessed items end up clustered near
the front.
(MTF lists are sometimes used in predictive compression schemes;
Burroughs and Wheeler suggest using one to reorganize entropy in front
of the Burroughs-Wheeler Transform, for example, though they actually
turn it into an encoder, where the output isn't the retrieved item but
its index in the list before it's moved.)