a possible explanation for the mmap benchmarks

["Igor Shmukler"]

First of all I do not want to start any kind of war here.
I studied results of Felix's benchmark some time ago and now I think I have a 
possible explanation for what happens. I do not mean to invalidate results. I 
just want to offer a cause, in case someone is unaware.

What does mmapbench do? It does mmap of every other page on 200MB file (by
default). Since it does mmap sequentialy, free space linear search vs hint
works very well, so we get almost constant time free space allocation (I
have tested Linux kernel 2.4 - it spends more and more time on each
subsequent mmap as the number of mapped regions growth. 2.6 should be OK,
since they are start using search hint :-) ) During sequential mmaping,
splay tree [used in vm_map_lookup_entry()] degenerates to a list. Later,
when mmapbench sequentialy touches mmaped regions, entry search using
degenerated splay tree gives almost the same results as linear entry
search vs hint. So again - no improvements on such test conditions.
RB-tree (NetBSD), as I understand, rebalances itself after each insert.
Splay tree only does rebalancing during sort.

The questions is whether altered benchmark, where things are done randomly
will produce similar results. I do not know the answer, yet. However, I believe 
it very well might.

I would be glad to know whether it seems reasonable to anyone? I contacted the 
author, but he has not had a chance to reply yet.