>the work I do. Anyone who knows me well will tell you that I'll
>completely rearchitect the trap handling on UltraSparc from scratch
>just to save 2 processor cycles in the trap entry/exit code for that
>platform.
;)).
>The computational cost in real life means:
>
>1) Some _constant_ number of processor cycles
>2) Some _constant_ set of instruction cache lines to hold to hash
> computation code
>
>Compare this (in real life) to the cost of:
>
>1) _Non-constant_ extra traversals through the main hash chain loop
>2) _Non-constant_ memory references assosciated with touching
> significantly more than (nr_buffer_heads / nr_hash_chains) buffer
> heads.
Of course I agree it's more important to reduce the complexity (even more
on fast CPU where the in core calculation are faster than memory
accesses).
OTOH lots of hashfn are implemented worrying about the speed of the hash
(just have a look at the trick used in the pagecache hash to let the
compiler optimize away the divl with a right shift).
Only for curiosity I did a little bench (maybe you'll find interesting,
otherwise ignore it and sorry for the wasted bandwith).
#define __KERNEL__
#define CONFIG_X86_TSC
#include <asm/timex.h>
#include <linux/kdev_t.h>
#include <sched.h>
#define _hashfn_13(dev,block) (((unsigned)(HASHDEV(dev)^block)) & bh_hash_mask)
#define __hashfn_14pre(dev,block) \
((((dev)<<(bh_hash_shift - 6)) ^ ((dev)<<(bh_hash_shift - 9))) ^ \
(((block)<<(bh_hash_shift - 6)) ^ ((block) >> 13) ^ ((block) << (bh_hash_shift - 12))))
#define _hashfn_14pre(dev,block) (__hashfn_14pre(dev,block) & bh_hash_mask)
unsigned long bh_hash_mask = 0x7ffff, bh_hash_shift = 19;
unsigned long hashfn_13(kdev_t dev, int block)
{
return _hashfn_13(dev, block);
}
unsigned long hashfn_14pre(kdev_t dev, int block)
{
return _hashfn_14pre(dev, block);
}
main()
{
int i;
cycles_t start, stop;
kdev_t dev = 0x0801;
int block = 28976, size = 1024;
struct sched_param par;
par.sched_priority = sched_get_priority_max(SCHED_FIFO);
if (sched_setscheduler(0, SCHED_FIFO, &par) < 0)
perror("sched_setscheduler SCHED_FIFO");
start = get_cycles();
hashfn_13(dev, block);
stop = get_cycles();
printf("2.2.13 cycles: %5u\n", stop - start);
start = get_cycles();
hashfn_14pre(dev, block);
stop = get_cycles();
printf("2.2.14pre2 cycles: %5u\n", stop - start);
}
On PII (compiled with `gcc -O2 -mcpu=i686 bufferhashfn.c`):
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 144
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 125
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 131
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 131
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 130
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 130
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 122
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 130
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 133
root@laser:/home/andrea > ./a.out
2.2.13 cycles: 51
2.2.14pre2 cycles: 130
On Alpha (compiled with `gcc bufferhashfn.c -O2 -mcpu=ev6`):
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 108
2.2.14pre2 cycles: 148
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 98
2.2.14pre2 cycles: 148
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 71
2.2.14pre2 cycles: 148
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 98
2.2.14pre2 cycles: 148
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 102
2.2.14pre2 cycles: 148
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 108
2.2.14pre2 cycles: 161
root@alpha:/home/andrea > ./a.out
2.2.13 cycles: 98
2.2.14pre2 cycles: 212
Here the i686 assembler of the 2.2.13 hashfn:
hashfn_13:
pushl %ebp
movl %esp,%ebp
movzwl 8(%ebp),%eax
xorl 12(%ebp),%eax
andl bh_hash_mask,%eax
movl %ebp,%esp
popl %ebp
ret
Here the i686 assembler of the 2.2.14pre2 hashfn:
hashfn_14pre:
pushl %ebp
movl %esp,%ebp
pushl %edi
pushl %esi
pushl %ebx
movzwl 8(%ebp),%eax
movl bh_hash_shift,%ebx
leal -6(%ebx),%edi
movl %eax,%esi
movl %edi,%ecx
sall %cl,%esi
leal -9(%ebx),%edx
movl %edx,%ecx
sall %cl,%eax
xorl %eax,%esi
movl 12(%ebp),%edx
movl %edi,%ecx
sall %cl,%edx
movl 12(%ebp),%eax
sarl $13,%eax
xorl %eax,%edx
leal -12(%ebx),%eax
movl %eax,%ecx
sall %cl,12(%ebp)
xorl 12(%ebp),%edx
xorl %edx,%esi
andl bh_hash_mask,%esi
leal -12(%ebp),%esp
movl %esi,%eax
popl %ebx
popl %esi
popl %edi
movl %ebp,%esp
popl %ebp
ret
Andrea
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/