From owner-freebsd-current@FreeBSD.ORG Fri Oct 1 05:53:54 2010 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 934EE106564A for ; Fri, 1 Oct 2010 05:53:54 +0000 (UTC) (envelope-from adrian.chadd@gmail.com) Received: from mail-iw0-f182.google.com (mail-iw0-f182.google.com [209.85.214.182]) by mx1.freebsd.org (Postfix) with ESMTP id 52EB08FC0A for ; Fri, 1 Oct 2010 05:53:54 +0000 (UTC) Received: by iwn34 with SMTP id 34so4180310iwn.13 for ; Thu, 30 Sep 2010 22:53:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:sender:received :in-reply-to:references:date:x-google-sender-auth:message-id:subject :from:to:cc:content-type:content-transfer-encoding; bh=ijmxDKamgLMNXxHSwD+ep7q9PJ0DRVtD+g5PJfv5bmE=; b=h9uAau2vBBwR8Unnm3glcmruPUrk4ss5OSprzaKyKZ/Y+spQR5smG5DoQG2AF/UIEz rgflrWifIIbZAnSMpZ7Ip76IFr8Bn5hlPAL7uUsw12HLXnF92GgupghFVZqe4993orMQ xf5sl2QTmGClBMOC5BAcF8pAW8bd9D+njToC8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=gweMJpBI5hoNHqe4cT3Qg5TbY9ty2knbfrkvozyy/eTl9gM5Texxk8IYL46egCycC1 x7FXRPi8wZcNloUKYBz7+xAjjBNBlFhx8O1DoI7HqizjA0OIHIkAVxazQOy0vKB9jNPP jLzbAHmZBPfcOThq1Ik1ZAK7JeTVt/GpVVmfM= MIME-Version: 1.0 Received: by 10.231.118.28 with SMTP id t28mr3682214ibq.131.1285912433463; Thu, 30 Sep 2010 22:53:53 -0700 (PDT) Sender: adrian.chadd@gmail.com Received: by 10.231.171.203 with HTTP; Thu, 30 Sep 2010 22:53:53 -0700 (PDT) In-Reply-To: <201010010449.o914nmVt024965@apollo.backplane.com> References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org> <4CA504AD.8000102@freebsd.org> <4CA509FE.30303@freebsd.org> <201010010449.o914nmVt024965@apollo.backplane.com> Date: Fri, 1 Oct 2010 13:53:53 +0800 X-Google-Sender-Auth: Espu7z_Yj4aG2XQIyN0XjET1lsw Message-ID: From: Adrian Chadd To: Matthew Dillon Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Oct 2010 05:53:54 -0000 On 1 October 2010 12:49, Matthew Dillon wrote= : > =A0 =A0What turned out to be the best indexing mechanism was a chained > =A0 =A0hash table whos hoppers were small linear arrays instead of single > =A0 =A0elements. =A0So instead of pointer-chaining each element you have = a small > =A0 =A0for() loop for 4-8 elements before you chain. =A0The structure bei= ng > =A0 =A0indexed would NOT be integrated into the index directly, the index > =A0 =A0would point at the final structure from the hopper. > > =A0 =A0For our purposes such linear arrays would contain a pointer and > =A0 =A0an indexing value in as small an element as possible (8-16 bytes), > =A0 =A0the idea being that you make the absolute best use of your cache l= ine > =A0 =A0and L1 cache / memory burst. =A0One random access (initial hash in= dex), > =A0 =A0then linear accesses using a small indexing element, then one fina= l > =A0 =A0random access to get to the result structure and validate that > =A0 =A0it's the one desired (at that point we'd be 99.9% sure that we hav= e > =A0 =A0the right structure because we have already compared the index val= ue > =A0 =A0stored in the hopper). =A0As a plus the initial hash index also ma= kes > =A0 =A0MP locking the base of the chains easier. Sounds like B+tree style stuff. Minimise the "seek" operations, as random lookup times are orders of magnitude slower than sequential access times. (Memory is hierarchial, who would've thunk. :-) Adrian