From owner-freebsd-hackers Thu Dec 18 21:11:20 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id VAA22696 for hackers-outgoing; Thu, 18 Dec 1997 21:11:20 -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 VAA22675 for ; Thu, 18 Dec 1997 21:10:35 -0800 (PST) (envelope-from gurney_j@efn.org) Received: (from jmg@localhost) by hydrogen.nike.efn.org (8.8.7/8.8.7) id UAA11721; Thu, 18 Dec 1997 20:43:34 -0800 (PST) Message-ID: <19971218204334.41263@hydrogen.nike.efn.org> Date: Thu, 18 Dec 1997 20:43:34 -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: > If you are proposing new in-kernel structures, it may be convenient to > choose those that can be later be easily parallelized. This can then avoid > unnecessary serialization on the data structure if/when the degree of > processor parallelism supported by FreeBSD increases in the future. hmm... good point... I'll have to talk with a professor of mine that knows data structures a bit better than I for suggestions... this isn't something that they normally cover in a 300 or 400 level classes... :( > > Timings: > > Fibonacci heap (amortized): > > Make-Heap theta(1) > > Insert theta(1) > > Minimum theta(1) > > Extract-min O(lg n) > > Union theta(1) > > Decrease-key theta(1) > > Delete O(lg n) > > B-Tree (each node has between t - 1 and 2t -1 keys) > > Create O(1) > > Search O(t logt n) soon to be O(lg t * logt n) > > Insert " > > Delete " > > (I'll have to read up on Fibonacci heaps). > > 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. > > > 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. hmm... can you point me to a book that has 'em? talking about cache's.. using a btree with a node size of 128 bytes is a significant performance boost... even on an old Intel 486DX2/66 processor... -- 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