From owner-freebsd-hackers  Thu Dec 18 20:04:40 1997
Return-Path: <owner-freebsd-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id UAA18766
          for hackers-outgoing; Thu, 18 Dec 1997 20:04:40 -0800 (PST)
          (envelope-from owner-freebsd-hackers)
Received: from palrel1.hp.com (palrel1.hp.com [156.153.255.235])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id UAA18742
          for <freebsd-hackers@freebsd.org>; Thu, 18 Dec 1997 20:04:27 -0800 (PST)
          (envelope-from koshy@india.hp.com)
Received: from postbox.india.hp.com (postbox.india.hp.com [15.10.45.1])
	by palrel1.hp.com (8.8.6/8.8.5tis) with ESMTP id UAA03560;
	Thu, 18 Dec 1997 20:04:10 -0800 (PST)
Message-Id: <199712190404.UAA03560@palrel1.hp.com>
Received: from localhost by postbox.india.hp.com with ESMTP
	(1.39.111.2/16.2) id AA141794235; Fri, 19 Dec 1997 09:33:55 +0530
To: freebsd-hackers@freebsd.org
Cc: gurney_j@efn.org
Subject: Re: converting drivers to dynamic memory
Date: Fri, 19 Dec 1997 09:33:54 +0530
From: A Joseph Koshy <koshy@india.hp.com>
Sender: owner-freebsd-hackers@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk


>>>>>> 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