Date: Mon, 22 Dec 1997 03:38:11 -0800 From: John-Mark Gurney <gurney_j@efn.org> To: A Joseph Koshy <koshy@india.hp.com> Cc: freebsd-hackers@freebsd.org Subject: Re: converting drivers to dynamic memory Message-ID: <19971222033811.27791@hydrogen.nike.efn.org> In-Reply-To: <199712190404.UAA03560@palrel1.hp.com>; from A Joseph Koshy on Fri, Dec 19, 1997 at 09:33:54AM %2B0530 References: <199712190404.UAA03560@palrel1.hp.com>
next in thread | previous in thread | raw e-mail | index | archive | help
A Joseph Koshy scribbled this message on Dec 19: > >>>>>> John-Mark Gurney <gurney_j@efn.org> said: > For example, concurrent B-trees are supposedly very complex to implement, > so typically people get by locking the root node and taking the serialization > hit. well... I was thinking about concurrent btrees... as B-tree can be completely implemented as a signle downward pass, all you need to do is lock your parent, and the current node, then when you set down, you only release your lock upon your parent AFTER you've locked your next node... as long as there aren't and processes that climb the tree, you won't have any deadlocks to avoid... this does mean you can't do concurrent operations and traversals of the tree though... you could lock the nodes read-only which would still allow current read operations to finish before you started modifing the tree.. > > quite small. The Fib heap code is under 3k, and the B-tree code is > > 4736 bytes, but this includes some debugkuing code (printing tree and > > Did you look at skiplists too? Typical skiplist implementations tend to be > small and can be coded to use the cache nicely. Further, combined with > non-blocking primitives like compare-and-swap (x86-post-P5), or > load-linked/store-conditional (Alpha) (we are going to have FreeBSD/Alpha > some day aren't we? :)) it can really shine. well.. I just implemented skiplists... they don't even come close to the performance of B-Trees (unless you use really small sets like 100 keys)... the data density is terible with skiplists... I ran it on freefall and it ran out of 64megs of ran for one million keys... but the B-Tree code (128bytes/node, 6-15keys/node) only used 16.5megs, four megs of that was for the table of keys that I had inserted into the tree)... the code for the skiplist is much smaller though.. 1632 bytes (sub 200 lines) for some debuging code, create, insert, delete... (4736 for B-tree, 500+ lines)... (and it did only take me about 6-8 hours to completely understand, write, and debug the code, compared to the 12-20 for the B-tree code)... I'm going to read a bit more, but I really don't think that skiplists are that useful for large sets of data... they also have the serious limitations that they are bounded by how much data you think you'll need (max height)... -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking P.O. Box 5693, 97405 Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19971222033811.27791>