Date: Fri, 19 Dec 1997 09:33:54 +0530 From: A Joseph Koshy <koshy@india.hp.com> To: freebsd-hackers@freebsd.org Cc: gurney_j@efn.org Subject: Re: converting drivers to dynamic memory Message-ID: <199712190404.UAA03560@palrel1.hp.com>
next in thread | raw e-mail | index | archive | help
>>>>>> John-Mark Gurney <gurney_j@efn.org> said: Hi John-Mark, 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. > 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. Koshy #include STD_DISCLAIMER
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199712190404.UAA03560>