Use perfect hashing, instead of binary search, for keyword lookup
Binary search is a pretty bad algorithm.  Sure, it runs in O(log n) time and it's more or less the best you can do to solve the general problem of finding something in a sorted list, but that does <i>not</i> mean it's a good way to create an immutable list of things that can be searched using comparisons.<p>In particular, binary search has awful cache locality.  Until you get very close to your target, you are essentially hitting a random cache line (and maybe even a random <i>page</i> for large lists) for every comparison.  This is bad.  A B-tree-like structure that is never modified is very easy to make, and it will be much faster.<p>This came up with the ORC unwinder in Linux.  We got something like a 4x speedup by changing from binary search to something a bit more clever to find unwind entries in the table.