Of course. I saw that. However the do/while approach is a O(N) algorithm
while the ffs() using algorithm can be O(1) if the CPU allows it.
I wrote a quick benchmark program + script (appended at bottom of this
mail) and did 50 million iterations of either the do/while function or the
ffs() equivalent (including the BUG() check for power of 2) and it turns
out that on all CPUs tested (Pentium 133S, Pentium III 800, Alpha EV56
533(or so), Athlon 1.33GHz 266FSB) the do/while loop is marginally faster
for sizes of 256 and 512 (except P3/800 where the ffs is faster even for
these smaller sizes) but is increasingly slower for increasing sizes. For
large sizes the do/while loop becomes significantly slower than the ffs()
approach, which of course is irrelevant at the moment with the block size
limitation...
The values in below tables are in seconds (user field from time output)
needed to complete 50 million cycles.
For those who prefer graphs rather than tables, I have created line charts
comparing the two methods for each CPU which you can view at URL (note the
charts contain data points for higher sizes, too, not shown in below tables
and also note that each point shown is from a single benchmark run simply
because I couldn't be bothered to do the stats on more than one go, but the
values shown are representative of several runs, if you don't believe me,
the program and script are at the bottom of this mail...):
http://www-stu.christs.cam.ac.uk/~aia21/ffs_test.gif
do/while based function
=======================
| Size
CPU | 256 512 1024 2048 4096 8192 16384
---------------+----------------------------------------------------
P1/133 | 2.26 2.38 4.62 5.29 6.04 6.78 7.56
P3/800 | 0.30 0.30 0.42 0.56 0.70 1.40 1.65
Alpha/533 | 0.48 0.48 1.93 2.22 2.52 2.31 2.61
Athlon/1333 | 0.13 0.14 0.27 0.34 0.41 0.49 0.57
ffs based function
==================
| Size
CPU | 256 512 1024 2048 4096 8192 16384
---------------+----------------------------------------------------
P1/133 | 3.73 3.73 3.78 3.77 3.77 3.78 3.84
P3/800 | 0.27 0.26 0.25 0.26 0.26 0.25 0.27
Alpha/533 | 0.58 0.58 0.58 0.58 0.58 0.58 0.58
Athlon/1333 | 0.15 0.15 0.15 0.15 0.15 0.15 0.15
And just for fun the comparison for the completely irrelevant and insane
size of 2^30 (1073741824), again 50 million iterations:
CPU | do/while | ffs
---------------+----------+--------
P1/133 | 19.62 | 3.76
P3/800 | 3.70 | 0.25
Alpha/533 | 7.25 | 0.58
Athlon/1333 | 2.18 | 0.15
Yeah, I know, benchmarks are to be taken with a pinch of salt, are
meaningless most of the time, etc, but it was fun doing this just to see
how different CPUs perform (on this specific piece of code). And it was a
good way to relax my brain after 11 hours of work at the lab today... (-:
>More importantly, I think the whole code will go away, because the bits
>(and the size) should be in the bdev structure in the first place (or,
>even better, the inode, at which point all the special-case functions go
>away and just become calls to the generic ones)
Yes, that would be a very good thing indeed and yes it renders the
discussion pointless. But a lot of code in the kernel does the same
calculation all the time, in particular in file systems and block devices
(which will probably go away once we have the value in the inode) and
almost none I have seen use ffs() but use variations of unoptimized
for/while/do loops and I think the above benchmark results show that using
ffs() would benefit all those cases unless they expect the normal case to
be a size of less or equal 512.
Best regards,
Anton
--- test_ffs.sh ---
#!/bin/bash
iters=50000000
if [ ! -f ./test_ffs ]; then
gcc -O2 -m486 -o test_ffs test_ffs.c
fi
echo
echo Performing $iters iterations with each blocksize.
for l in 256 512 1024 2048 4096 8192 16384 32768 65536 131072 1073741824; do
time ./test_ffs 1 $iters $l
time ./test_ffs 2 $iters $l
done
exit 0
--- test_ffs.c ---
static inline unsigned int blksize_bits(unsigned int size)
{
unsigned int bits = 8;
do {
bits++;
size >>= 1;
} while (size > 256);
return bits;
}
/*
* Replace this with ffs() from linux/include/asm/bitops.h
* for your arch on non ia32.
*/
static __inline__ int kernel_ia32_ffs(int x)
{
int r;
__asm__("bsfl %1,%0\n\t"
"jnz 1f\n\t"
"movl $-1,%0\n"
"1:" : "=r" (r) : "g" (x));
return r+1;
}
static inline unsigned int blksize_bits_ffs(unsigned int size)
{
if (!(size & size - 1))
return kernel_ia32_ffs(size) - 1;
puts("size not power of 2!");
exit(1);
}
int main(int argc, char *argv[])
{
long i, j, iters, testval;
char test;
if (argc != 4) {
parm_err:
printf("Syntax: test_ffs test iterations testvalue\n"
"test = 1 -> use do/while blksize_bits\n"
"test = 2 -> use ffs blksize_bits\n"
"iterations = number of iterations of "
"blksize_bits call\n"
"testvalue = value to pass to
blksize_bits\n");
exit(1);
}
test = *argv[1];
if (test != '1' && test != '2')
goto parm_err;
iters = atol(argv[2]);
testval = atol(argv[3]);
if (iters <= 0 || testval <= 0)
goto parm_err;
printf("\n\nPerforming %li million iterations of %s test with test "
"value %li.\n", iters/1000000, test == '1' ?
"do/while" : "ffs", testval);
switch (test) {
case '1':
for (i = 0; i < iters; i++)
j = blksize_bits(testval);
break;
case '2':
for (i = 0; i < iters; i++)
j = blksize_bits_ffs(testval);
break;
}
return 0;
}
-- "Nothing succeeds like success." - Alexandre Dumas-- Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @) Linux NTFS Maintainer / WWW: http://linux-ntfs.sf.net/ ICQ: 8561279 / WWW: http://www-stu.christs.cam.ac.uk/~aia21/- 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/
