Splay tree patch
Red-black tree patch
Tests have been run with a ben.c program. A benchmark was a:
# sysctl kern.maxproc=8000 # ./ben -f -n7000 >resultsas was suggested by Markus Friedl. Then results file was split to fork/kill parts and plotted.
Here are plots:
fork test #1 -
original implementation (tailq) and a splay tree one. No actual changes
here.
fork test #2 - splay tree vs. r/b tree.
Splay tree occurs to be slighter faster this time...
kill test #1 - original implementatio (tailq)
and a splay tree. Great changes here... (Note: the plot is logarithmic!)
kill test #3 - another splay tree vs. r/b tree
test. IMO, the same results.
Benchmarks were performed on an AMD Athlon 850Mhz machine with 512Mb RAM,
full dmesg and a kernel config.
OpenBSD 3.9-beta (the latests sources from anoncvs.ca.openbsd.org).