It appears that by removing some conditionals in the reiser4 key comparison functions key comparison performance improves by at least 2x. Using a purpose-built znode_contains_key_strict and the new comparison code, cache scanning could be almost three times as fast -- even faster with a single unsigned char 'hint' member added to the znode structure.
A writeup, including the timings and the code, is available at http://dabbs.net/reiser4 I'd be interested in your feedback. David Dabbs