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."
