From mboxrd@z Thu Jan 1 00:00:00 1970 From: Werner Almesberger Subject: Re: barriers vs. reads Date: Thu, 24 Jun 2004 14:02:29 -0300 Sender: linux-fsdevel-owner@vger.kernel.org Message-ID: <20040624140228.T1325@almesberger.net> References: <20040623214845.A21586@almesberger.net> <20040624003944.B21586@almesberger.net> <20040624133639.GA8440@mail.shareable.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: linux-fsdevel@vger.kernel.org Return-path: Received: from almesberger.net ([63.105.73.238]:14853 "EHLO host.almesberger.net") by vger.kernel.org with ESMTP id S266195AbUFXRCx (ORCPT ); Thu, 24 Jun 2004 13:02:53 -0400 To: Jamie Lokier Content-Disposition: inline In-Reply-To: <20040624133639.GA8440@mail.shareable.org>; from jamie@shareable.org on Thu, Jun 24, 2004 at 02:36:39PM +0100 List-Id: linux-fsdevel.vger.kernel.org Jamie Lokier wrote: > Is the prio_tree data structure, the one being used by recent VM work, > which keeps track of ranges, any use? Hmm, they deliver exactly the data we need. That's great. Unlike rb-trees, they also aren't balanced, and thus have a worst-case O(log n) term with "log n" = sizeof(sector_t)*8 for simple lookups. Furthermore, they have a scary worst-case insertion time of O((log n)^2). With rb-trees, we get a mere O(log nr_requests) for lookups. So that's A*32 vs. B*7 using all-default 2.6.7 on ia32. Insertion has the same typical cost, and A*1024 vs. B*7 worst-case. A and B are implementation-specific per-operation cost factors. But yes, they look very interesting ... Thanks, - Werner -- _________________________________________________________________________ / Werner Almesberger, Buenos Aires, Argentina wa@almesberger.net / /_http://www.almesberger.net/____________________________________________/