On Tue, 3 Apr 2012, Stephen R. van den Berg wrote:
Arne Goedeke wrote:
have been developing. This one uses a different algorithm than the one we briefly mentioned on the conference. The new one uses a hashtable for page lookup instead of radix trees.
The benchmarks are impressive. However, using a hashtable always pops up the question, what is the worst case for this implementation, and when does it happen?
The worst case will be roughly the same as the lookup happening for the current one. Pointers to the pages are stored in the hashtable. So if you are very unlucky and all page pointers end up in the same bucket, you will be doing the same linear search of a linked list thats currently the lookup algorithm in the pike block_alloc.h. I never got around to trying to somehow include the radix tree lookup again, there of cause worst case would be much nicer.
-- Stephen.
"Sleep: A completely inadequate substitute for caffeine."