From owner-freebsd-hackers Mon Dec 22 03:39:40 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id DAA17840 for hackers-outgoing; Mon, 22 Dec 1997 03:39:40 -0800 (PST) (envelope-from owner-freebsd-hackers) Received: from hydrogen.nike.efn.org (resnet.uoregon.edu [128.223.170.28]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id DAA17834 for ; Mon, 22 Dec 1997 03:39:34 -0800 (PST) (envelope-from gurney_j@efn.org) Received: (from jmg@localhost) by hydrogen.nike.efn.org (8.8.7/8.8.7) id DAA02414; Mon, 22 Dec 1997 03:38:11 -0800 (PST) Message-ID: <19971222033811.27791@hydrogen.nike.efn.org> Date: Mon, 22 Dec 1997 03:38:11 -0800 From: John-Mark Gurney To: A Joseph Koshy Cc: freebsd-hackers@freebsd.org Subject: Re: converting drivers to dynamic memory References: <199712190404.UAA03560@palrel1.hp.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.69 In-Reply-To: <199712190404.UAA03560@palrel1.hp.com>; from A Joseph Koshy on Fri, Dec 19, 1997 at 09:33:54AM +0530 Reply-To: John-Mark Gurney Organization: Cu Networking X-Operating-System: FreeBSD 2.2.1-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ Sender: owner-freebsd-hackers@freebsd.org X-Loop: FreeBSD.org Precedence: bulk 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, 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