George V. Reilly

LKRhash: Scalable Hash Tables

LKRhash is a hashtable that scales to multiple processors and to millions of items. LKRhash was invented at Microsoft in 1997 by Per-Åke (Paul) Larson of Microsoft Research and Murali Krishnan and George Reilly of Internet In­for­ma­tion Services. LKRhash has been used in many Microsoft products. The techniques that give LKRhash its per­for­mance include linear hashing, cache-friendly data structures, and fine-grained locking.

If Microsoft had had 20% time, LKRhash would have been my main project. I put a lot of effort into making it a polished, well-tuned library that was used in multiple products across the company. I even ported the C++ code to kernel mode, though it never ended up in a production driver, as far as I know. Several years ago, after I left Microsoft, I attempted to get it open-sourced. However, despite some help on the inside, we were never able to surmount the legal barriers.

blog comments powered by Disqus
Review: Watch Your Back! » « Diff a Transformed File