Date: Thu, 18 Dec 1997 20:43:34 -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: <19971218204334.41263@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: > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19971218204334.41263>