The Berkeley DB change to the application-specified comparison function API may be interesting. The change was to add a reference to a size_t as an additional 4th argument to the comparison function, but oddly enough, the applications aren't supposed to touch that new argument.

What's happening is BDB has the same code we have to skip over common prefixes when doing a binary search through page keys, which requires the comparison function return the longest matching prefix on each comparison, and that's the reason for the additional argument. Rather than add a test/branch into the btree search inner loop, BDB changed the application-specified comparison function signature to take the additional argument just like the internal comparison function.

We're doing it with a test:

#define WT_LEX_CMP_SKIP(s, collator, k1, k2, cmp, matchp)
        ((collator) == NULL ?
        (((cmp) = __wt_lex_compare_skip((k1), (k2), matchp)), 0) :
        (collator)->compare(collator, &(s)->iface, (k1), (k2), &(cmp)))

Further, the only reason for error handling on this call is because application-specified collators can fail, our collator cannot fail.

I replaced the search loop calls to WT_ERR(WT_LEX_CMP_SKIP()) with a call to __wt_lex_compare_skip(), removing the error handling, and it improves my test by over 6% with gcc 4.7 on my FreeBSD 9.1 box. In an in-cache, 5M row table, search for every row in order, I go from .5788 usecs per search to .5416 usecs per search.

I don't see a simple way to make this change for real, but 6% seems like it's worth having on searches.

Thoughts?