Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755060Ab0FCN4H (ORCPT ); Thu, 3 Jun 2010 09:56:07 -0400 Received: from ist.d-labs.de ([213.239.218.44]:44108 "EHLO mx01.d-labs.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752955Ab0FCN4F convert rfc822-to-8bit (ORCPT ); Thu, 3 Jun 2010 09:56:05 -0400 Date: Thu, 3 Jun 2010 15:55:52 +0200 From: Florian Mickler To: Arve =?ISO-8859-15?Q?Hj=F8nnev=E5g?= Cc: markgross@thegnar.org, Brian Swetland , 640e9920@gmail.com, "Rafael J. Wysocki" , Alan Stern , Peter Zijlstra , Linux PM , Alan Cox , Matthew Garrett , Thomas Gleixner , LKML , Ingo Molnar Subject: Re: [linux-pm] [PATCH 0/8] Suspend block api (version 8) Message-ID: <20100603155552.24c38afc@schatten.dmk.lab> In-Reply-To: References: <201005312338.55109.rjw@sisk.pl> <20100531232617.GF31155@gvim.org> <20100601090737.4bc243d9@schatten.dmk.lab> <20100601140519.GC1281@gvim.org> <20100602133910.GA9106@gvim.org> <20100603031842.GB11311@gvim.org> <20100603054018.GE11311@gvim.org> X-Mailer: Claws Mail 3.7.5 (GTK+ 2.18.9; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8BIT Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1594 Lines: 42 On Thu, 3 Jun 2010 00:10:03 -0700 Arve Hj?nnev?g wrote: > On Wed, Jun 2, 2010 at 10:40 PM, mark gross <640e9920@gmail.com> wrote: > > well I think for a pm_qos class that has boolean dynamic range we can > > get away with not walking the list on every request update. ?we can use > > a counter, and the list will be for mostly for stats. > > > > Did you give any thought to my suggestion to only use one entry per > unique value on the first level list and then use secondary lists of > identical values. That way if you only have two constraints values the > list you have to walk when updating a request will never have more > than two entries regardless of how many total request you have. > > A request update then becomes something like this: > if on primary list { > unlink from primary list > if secondary list is not empty > get next secondary entry and add in same spot on primary list > } > unlink from secondary list > find new spot on primary list > if already there > add to secondary list > else > add to primary list > Yes. I think that would be good. If we keep the primary list sorted, then this becomes a nice priority queue implementation which does GetMax in constant time and Insert and Delete in logarithmic complexity to the number of different values. Cheers, Flo -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/