Right... this result is one of those examples of why you don't guess, you benchmark, because my intuition is that binary search should be "really fast." Clearly though the cache misses hurt a lot more than my intuitions capture.
Oh, the sorted array-backed "map" isn't using B-trees because I wanted it as a comparison point (to see how the LLVM containers fare against the old "just use a vector" advice). So the ArrayMap isn't production-ready or anything... it's intended to give a baseline against which to compare what would happen if you wrote your own dead-simple map replacement with the hope of improving perf.