Reply to thread

Message: [QUOTE="Michael Wojcik, post: 4197343"] 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.) [/QUOTE]