From owner-freebsd-current@FreeBSD.ORG Mon Oct 4 10:22:55 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 3A8A31065675 for ; Mon, 4 Oct 2010 10:22:55 +0000 (UTC) (envelope-from mayur.shardul@gmail.com) Received: from mail-qy0-f175.google.com (mail-qy0-f175.google.com [209.85.216.175]) by mx1.freebsd.org (Postfix) with ESMTP id E5C578FC1A for ; Mon, 4 Oct 2010 10:22:54 +0000 (UTC) Received: by qyk8 with SMTP id 8so2965095qyk.13 for ; Mon, 04 Oct 2010 03:22:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:content-type; bh=MVqLoRNkD2wl+YckhEtiIL1tWVlWGlP5AmrUkWTmUDI=; b=MrEsVRVs2FekUkVqlwp6mqYm+Q8oZwzOoU/ViKZ3yQE0sVyJzC2krTWieZAm2+7F5h QGWEpONedxCXctZZkqx5nVUyox7SzQq9CN14nO919K/uOSuTjJ4F3PobBkn35XXOKhvj 9HWLKJIEoIQjnPqU8g21obUjOXbDSm1xUvCHI= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=WNZpOCHQZpi3bpfGb5DTbogGp0na7stC8pY5dQWVPnRTKwmBCGPkvn+ShLLuw7Lnpl LKxecJuWPQBe3mnh1J0sIDJ/ORS6A8Trp5IQa3t9KYfHABUNFeGDz8Ki+67InbC113sW Xb6repEYOqyyXg7/CAAPGhVXgpYV4rvMIQJfA= MIME-Version: 1.0 Received: by 10.224.19.200 with SMTP id c8mr6754698qab.129.1286186116672; Mon, 04 Oct 2010 02:55:16 -0700 (PDT) Received: by 10.229.11.25 with HTTP; Mon, 4 Oct 2010 02:55:16 -0700 (PDT) In-Reply-To: References: Date: Mon, 4 Oct 2010 15:25:16 +0530 Message-ID: From: Mayur To: freebsd-current@freebsd.org Content-Type: text/plain; charset=ISO-8859-1 X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Subject: Fwd: 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: Mon, 04 Oct 2010 10:22:55 -0000 By mistake last mail went to hackers.... sending it to freebsd-current -- Hi, Sorry for pitching in late on the discussion.... Looks like I have missed many mails, Will start from this point in the discussion I just took a look (not in-depth though) at the patch and can't follow your conclusion. It is not ready to go into svn in its current state. Even though it is called a radix trie it doesn't look like one. On first impression it looks much more like an AA tree. A radix trie, which we already have in our network routing table code, is a variable length (mask) tree that does path compression. See net/radix.[ch] and <> The data-structure is just like a page table where the index is chopped in to sub-indices. i th sub-index is offset into corresponding node node on (i+1)th level. The difference between then wikipedia description of radixtree and our implementation is that nodes with single child are not merged with parent (level compression). Also, we started with variable size slots (sub-indices) but Jeff thought its little too flexible. Current implementation works with fixed sized sub-indices (size is multiple of sizeof original index) About the benchmark: It works on uniform random numbers. Objective was to optimize random accesses on large objects (~4G-2T) Take a look at radix_tree_shrink() this function reduces the depth of the tree (if possible). Special case of path compression. <> http://en.wikipedia.org/wiki/Radix_tree Extrapolating in a complete guesstimating way from the lookup function I'd say it may perform only slightly better in an ideal case than a RB tree but with the added overall expense of requiring external memory to store the index and branch nodes. This is probably a nasty disadvantage. <> I don't get you, please elaborate. The way tree is structured we do not need space to store index (nor does radix-trie), it is implicit from the position of the "value" corresponding the index. <> Thanks, Mayur