Date: Mon, 22 Dec 1997 11:44:29 -0500 (EST) From: Chuck Robey <chuckr@glue.umd.edu> To: John-Mark Gurney <gurney_j@resnet.uoregon.edu> Cc: A Joseph Koshy <koshy@india.hp.com>, freebsd-hackers@FreeBSD.ORG Subject: Re: converting drivers to dynamic memory Message-ID: <Pine.BSF.3.96.971222114303.4983Y-100000@picnic.mat.net> In-Reply-To: <19971222033811.27791@hydrogen.nike.efn.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, 22 Dec 1997, John-Mark Gurney wrote: > 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 I didn't know that ... I wonder how ... do you keep a count of keys stored inside a node hierarchy or something like that? How is splitting handled? , 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 > > ----------------------------+----------------------------------------------- Chuck Robey | Interests include any kind of voice or data chuckr@glue.umd.edu | communications topic, C programming, and Unix. 213 Lakeside Drive Apt T-1 | Greenbelt, MD 20770 | I run Journey2 and picnic, both FreeBSD (301) 220-2114 | version 3.0 current -- and great FUN! ----------------------------+-----------------------------------------------
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.3.96.971222114303.4983Y-100000>