From owner-freebsd-arch@FreeBSD.ORG  Tue Nov 14 17:23:23 2006
Return-Path: <owner-freebsd-arch@FreeBSD.ORG>
X-Original-To: arch@freebsd.org
Delivered-To: freebsd-arch@FreeBSD.ORG
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 3E64016A40F;
	Tue, 14 Nov 2006 17:23:23 +0000 (UTC) (envelope-from jdp@polstra.com)
Received: from blake.polstra.com (blake.polstra.com [64.81.189.66])
	by mx1.FreeBSD.org (Postfix) with ESMTP id 1E7C443D49;
	Tue, 14 Nov 2006 17:23:20 +0000 (GMT) (envelope-from jdp@polstra.com)
Received: from strings.polstra.com (strings.polstra.com [64.81.189.67])
	by blake.polstra.com (8.13.6/8.13.6) with ESMTP id kAEHN8C8071836;
	Tue, 14 Nov 2006 09:23:08 -0800 (PST) (envelope-from jdp@polstra.com)
Message-ID: <XFMail.20061114092308.jdp@polstra.com>
X-Mailer: XFMail 1.5.5 on FreeBSD
X-Priority: 3 (Normal)
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
In-Reply-To: <11832.1163519171@critter.freebsd.dk>
Date: Tue, 14 Nov 2006 09:23:08 -0800 (PST)
From: John Polstra <jdp@polstra.com>
To: Andre Oppermann <andre@freebsd.org>
Cc: arch@freebsd.org
Subject: Re: a proposed callout API
X-BeenThere: freebsd-arch@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussion related to FreeBSD architecture <freebsd-arch.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-arch>
List-Post: <mailto:freebsd-arch@freebsd.org>
List-Help: <mailto:freebsd-arch-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-arch>,
	<mailto:freebsd-arch-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Nov 2006 17:23:23 -0000

In message <4559E301.2030607@freebsd.org>, Andre Oppermann writes:
>Luigi Rizzo wrote:
>> On Tue, Nov 14, 2006 at 04:11:20PM +0100, Andre Oppermann wrote:
>> ...
>>> It's important to know that any random memory accesses on modern
>>> CPUs are really expensive because of cache misses.  That's why
>>> Judy tries beat RB tries by an order of a magnitude these days.
>> 
>> you mean this stuff ?
>> 
>> http://docs.hp.com/en/B6841-90001/ch02s01.html
>> http://judy.sourceforge.net/
>
>We've used it a number of other projects and it beats everything
>else hands down in speed and memory consumption.

Very cool.  Unfortunately, Appendix A of the H-P document says,
"Hewlett-Packard has patents pending on the Judy Technology," so the
data structure might not be useful to us in practice.

John