cvs commit: src/sys/vm vm_map.c vm_map.h
dillon 2005/01/20 10:00:38 PST
DragonFly src repository
Modified files:
sys/vm vm_map.c vm_map.h
Log:
Replace the cache-point linear search algorithm for VM map entries with
a red-black tree. This makes VM map lookups O(log N) in all cases.
Note that FreeBSD seems to have gone the splay-tree route, but I really
dislike the fact that splay trees are constantly writing to memory even
for simple lookups. This would also limit our ability to implement a
separate hinting/caching mechanism. A red-black tree is basically a
binary tree with internal nodes containing real data in addition to the leafs,
simlar to a B+Tree. A red-black tree is very similar to a splay tree but it
does not attempt to modify the data structure for pure lookups.
Caveat: we tried to revive the map->hint mechanism but there is currently
a serious crash/lockup bug related to it so it is disabled in this commit.
Submitted-by: Eirik Nygaard <eirikn@kerneled.com>
Using-Red-Black-Macros-From: NetBSD (sys/tree.h)
Revision Changes Path
1.37 +82 -69 src/sys/vm/vm_map.c
1.15 +6 -0 src/sys/vm/vm_map.h
http://www.dragonflybsd.org/cvsweb/src/sys/vm/vm_map.c.diff?r1=1.36&r2=1.37&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vm/vm_map.h.diff?r1=1.14&r2=1.15&f=u