From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757373AbYDGKZ7 (ORCPT ); Mon, 7 Apr 2008 06:25:59 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1756076AbYDGKZw (ORCPT ); Mon, 7 Apr 2008 06:25:52 -0400 Received: from out4.smtp.messagingengine.com ([66.111.4.28]:50217 "EHLO out4.smtp.messagingengine.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755428AbYDGKZv (ORCPT ); Mon, 7 Apr 2008 06:25:51 -0400 Message-Id: <1207563950.7880.1246457209@webmail.messagingengine.com> X-Sasl-Enc: w6P3LeprDVbjjCuAivnWNEGHl1Yy3AYytF38kPxdWKQZ 1207563950 From: "Alexander van Heukelum" To: "dean gaudet" Cc: "Alexander van Heukelum" , "Ingo Molnar" , "Andi Kleen" , "LKML" Content-Disposition: inline Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="ISO-8859-1" MIME-Version: 1.0 X-Mailer: MessagingEngine.com Webmail Interface References: <20080331171506.GA24017@mailshack.com> <20080401084710.GB4787@elte.hu> <20080401094618.GA24862@mailshack.com> <1207507897.18129.1246358115@webmail.messagingengine.com> Subject: Re: [PATCH] x86: generic versions of find_first_(zero_)bit, convert i386 In-Reply-To: Date: Mon, 07 Apr 2008 12:25:50 +0200 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sun, 6 Apr 2008 13:22:58 -0700 (PDT), "dean gaudet" said: > On Sun, 6 Apr 2008, Alexander van Heukelum wrote: > > > The current generic implementation of ffz is O(lg(n)) already > > it's O(lg(n)) time... the operations all depend on each other. > > the implementation i pointed to is O(lg(n)) code space... and the time > depends on how parallel the machine is, they're not dependent on each > other. Indeed. The worst dependencies are in the sum of all the partial results in this implementation. And addition is associative, so partial results can be written as ((a+b)+(c+d))+(e+f). Assuming perfect parallel execution this would lead to O(ln(ln(n))). Good. Care to implement ffs and __ffs like this? Greetings, Alexander > -dean -- Alexander van Heukelum heukelum@fastmail.fm -- http://www.fastmail.fm - The professional email service