From owner-freebsd-current@FreeBSD.ORG Thu Sep 30 17:52:03 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 627051065674 for ; Thu, 30 Sep 2010 17:52:03 +0000 (UTC) (envelope-from freebsd-current@m.gmane.org) Received: from lo.gmane.org (lo.gmane.org [80.91.229.12]) by mx1.freebsd.org (Postfix) with ESMTP id 1BD088FC15 for ; Thu, 30 Sep 2010 17:52:02 +0000 (UTC) Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1P1NIW-0001h0-Sw for freebsd-current@freebsd.org; Thu, 30 Sep 2010 19:52:00 +0200 Received: from 93-138-123-63.adsl.net.t-com.hr ([93.138.123.63]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 30 Sep 2010 19:52:00 +0200 Received: from ivoras by 93-138-123-63.adsl.net.t-com.hr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 30 Sep 2010 19:52:00 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: freebsd-current@freebsd.org From: Ivan Voras Date: Thu, 30 Sep 2010 19:51:49 +0200 Lines: 19 Message-ID: References: <4CA4BCD2.4070303@freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 93-138-123-63.adsl.net.t-com.hr User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.9.1.9) Gecko/20100620 Thunderbird/3.0.4 In-Reply-To: <4CA4BCD2.4070303@freebsd.org> Cc: freebsd-hackers@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: Thu, 30 Sep 2010 17:52:03 -0000 On 09/30/10 18:37, Andre Oppermann wrote: > Both the vmmap and page table make use of splay trees to manage the > entries and to speed up lookups compared to long to traverse linked > lists or more memory expensive hash tables. Some structures though > do have an additional linked list to simplify ordered traversals. The property of splay tree requiring *writes* for nearly every read really is a thorn in the eye for SMP. It seems to me that even if the immediate benefits from converting to something else are not directly observable, it will still be worth doing it. It's a shame that RCU is still a patent minefield :/ http://mirror.leaseweb.com/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf Slightly off-topic: a scare-mongering topic on Slashdot: http://hardware.slashdot.org/story/10/09/30/1528229/Linux-May-Need-a-Rewrite-Beyond-48-Cores