From: David Howells <dhowells@redhat.com>
In-Reply-To: <20040614040417.29e7497b.akpm@osdl.org>
References: <20040614040417.29e7497b.akpm@osdl.org>  <20040611150110.73fadefb.akpm@osdl.org> <567.1086950642@redhat.com> <6567.1086963705@redhat.com> <18241.1087210067@redhat.com>
To: Andrew Morton <akpm@osdl.org>
Cc: torvalds@osdl.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH] Permit inode & dentry hash tables to be allocated > MAX_ORDER size [try #3]
User-Agent: EMH/1.14.1 SEMI/1.14.5 (Awara-Onsen) FLIM/1.14.5 (Demachiyanagi) APEL/10.6 Emacs/21.3 (i386-redhat-linux-gnu) MULE/5.0 (SAKAKI)
MIME-Version: 1.0 (generated by SEMI 1.14.5 - "Awara-Onsen")
Content-Type: text/plain; charset=US-ASCII
Date: Mon, 14 Jun 2004 12:41:01 +0100
Message-ID: <19095.1087213261@redhat.com>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1959
Lines: 65

> > > What's the attribute((pure)) for?
> >
> > It tells gcc that the function's result only depends on its arguments... it
> > makes no references at all to external data. It's like __attribute__((const))
> > but stronger. This means that gcc can generate code that caches the result.

Actually... I'm wrong about that. I've got "pure" and "const" the wrong way
around... Perhaps I need to go and read the gcc manual too:-)

> Of course, but we could use it in zillions of places and we don't.  Does it
> actually help?

Well... it could. It certainly doesn't hurt. Actually, it's probably
irrelevant on inline functions as the compiler can look inside of those.

> > > The other four or five implementations of log2() use ffx(~n).
> >

I presume this should be ffz() not ffx().

> > Yes... but ffs() and ffz() take int args, not long args. I suspect that
> > shouldn't matter (that would require the hash table to be calculated at 4Gig
> > buckets in size or greater to be a problem), but why take the chance when we
> > can avoid it easily?
>
> No, ffz() takes an unsigned long argument.

So it does. However, ffz(~n) is not equivalent to log2(n). This can be
demonstrated by this little test program:

	#include <stdio.h>
	#include <stdlib.h>

	static __inline__ unsigned long ffz(unsigned long word)
	{
		__asm__("bsfl %1,%0"
			:"=r" (word)
			:"r" (~word));
		return word;
	}

	int main(int argc, char *argv[])
	{
		for (argv++; *argv; argv++)
			printf("%lu\n", ffz(~strtoul(*argv, NULL, 0)));

		return 0;
	}

	dhowells>/tmp/ffz 0x10
	4
	dhowells>/tmp/ffz 0x8
	3
	dhowells>/tmp/ffz 0x1f
	0

This is not entirely correct; the third answer should be 4 too. The bit scan
occurs in the wrong direction.

David
-
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/