From: "Alexander van Heukelum" <heukelum@fastmail.fm>
To: "dean gaudet" <dean@arctic.org>
Cc: "Alexander van Heukelum" <heukelum@mailshack.com>,
"Ingo Molnar" <mingo@elte.hu>, "Andi Kleen" <andi@firstfloor.org>,
"LKML" <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH] x86: generic versions of find_first_(zero_)bit, convert i386
Date: Mon, 07 Apr 2008 12:25:50 +0200 [thread overview]
Message-ID: <1207563950.7880.1246457209@webmail.messagingengine.com> (raw)
In-Reply-To: <alpine.DEB.1.10.0804061320470.7751@twinlark.arctic.org>
On Sun, 6 Apr 2008 13:22:58 -0700 (PDT), "dean gaudet" <dean@arctic.org>
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
next prev parent reply other threads:[~2008-04-07 10:25 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-03-31 17:15 [PATCH] x86: generic versions of find_first_(zero_)bit, convert i386 Alexander van Heukelum
2008-03-31 17:22 ` Stephen Hemminger
2008-03-31 19:38 ` Alexander van Heukelum
2008-03-31 21:58 ` Andi Kleen
2008-04-01 8:47 ` Ingo Molnar
2008-04-01 9:46 ` Alexander van Heukelum
2008-04-01 15:41 ` [PATCH] x86: switch x86_64 to generic find_first_bit Alexander van Heukelum
2008-04-01 15:42 ` [PATCH] x86: optimize find_first_bit for small bitmaps Alexander van Heukelum
2008-04-01 15:47 ` [PATCH] x86: remove x86-specific implementations of find_first_bit Alexander van Heukelum
2008-04-03 9:34 ` Alexander van Heukelum
2008-04-04 8:47 ` Ingo Molnar
2008-04-06 17:03 ` [PATCH] x86: generic versions of find_first_(zero_)bit, convert i386 dean gaudet
2008-04-06 18:51 ` Alexander van Heukelum
2008-04-06 20:22 ` dean gaudet
2008-04-07 8:43 ` Ingo Molnar
2008-04-07 10:25 ` Alexander van Heukelum [this message]
2008-04-18 20:18 ` Alternative implementation of the generic __ffs Alexander van Heukelum
2008-04-18 23:46 ` dean gaudet
2008-04-19 0:09 ` Harvey Harrison
2008-04-19 0:20 ` dean gaudet
2008-04-19 0:58 ` Joe Perches
2008-04-19 1:04 ` Harvey Harrison
2008-04-19 1:11 ` dean gaudet
2008-04-19 2:55 ` Joe Perches
2008-04-19 4:13 ` dean gaudet
2008-04-19 10:05 ` Mikael Pettersson
2008-04-19 12:10 ` Alexander van Heukelum
2008-04-19 18:17 ` Joe Perches
2008-04-19 20:26 ` Alexander van Heukelum
2008-04-19 22:29 ` Matti Aarnio
2008-04-20 3:06 ` Joe Perches
2008-04-20 8:42 ` Alexander van Heukelum
2008-04-20 12:31 ` Matti Aarnio
2008-04-21 11:43 ` Alexander van Heukelum
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1207563950.7880.1246457209@webmail.messagingengine.com \
--to=heukelum@fastmail.fm \
--cc=andi@firstfloor.org \
--cc=dean@arctic.org \
--cc=heukelum@mailshack.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).