Skip to contentSkip to conversation

linux kernel hash table vs rbtree

DISCUSSION Hiro Yoshioka 1 participant 1 message Apr 2, 2002 Memory management

lore
Share & tools
lore
#0 lore raw

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:[email protected]
http://www.miraclelinux.com
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/