linux kernel hash table vs rbtree

[Hiro Yoshioka <hyoshiok@miraclelinux.com>]

Hi,

I have read papers: 'Linux Kernel Hash Table Behavior:
analysis and improvements'

http://www.citi.umich.edu/projects/linux-scalability/reports/hash.html
http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
http://www.usenix.org/publications/library/proceedings/als2000/lever.html

It is very interesting though it is based on the kernel 2.2.

I also found the kernel 2.4.10 has been introducing a rbtree
instead of AVL tree.

Your paper has suggested rbtree performs better than the
original but not better than other algorithm.

Do you know any performance data (quantitative data)
which supports rbtree has good performance?

I'm CCing linux-mm mailing list since there are maintainers.

Regards,
  Hiro
--
Hiro Yoshioka/CTO, Miracle Linux
mailto:hyoshiok@miraclelinux.com
http://www.miraclelinux.com
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/