From owner-freebsd-hackers Mon Dec 22 08:47:01 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id IAA04552 for hackers-outgoing; Mon, 22 Dec 1997 08:47:01 -0800 (PST) (envelope-from owner-freebsd-hackers) Received: from picnic.mat.net (picnic.mat.net [206.246.122.117]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id IAA04538 for ; Mon, 22 Dec 1997 08:46:49 -0800 (PST) (envelope-from chuckr@glue.umd.edu) Received: from localhost (chuckr@localhost) by picnic.mat.net (8.8.8/8.8.5) with SMTP id LAA01670; Mon, 22 Dec 1997 11:44:29 -0500 (EST) Date: Mon, 22 Dec 1997 11:44:29 -0500 (EST) From: Chuck Robey X-Sender: chuckr@picnic.mat.net To: John-Mark Gurney cc: A Joseph Koshy , freebsd-hackers@FreeBSD.ORG Subject: Re: converting drivers to dynamic memory In-Reply-To: <19971222033811.27791@hydrogen.nike.efn.org> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk On Mon, 22 Dec 1997, John-Mark Gurney wrote: > A Joseph Koshy scribbled this message on Dec 19: > > >>>>>> John-Mark Gurney 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! ----------------------------+-----------------------------------------------