Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

Willy Tarreau
2003-05-31T08:43:14Z

On Sat, May 31, 2003 at 01:12:10AM -0700, David S. Miller wrote:
> From: Willy TARREAU <willy@w.ods.org>
> Date: Sat, 31 May 2003 10:02:05 +0200
>
> With this simple change, jhash_mix is *exactly* three times faster
> for me on athlon-xp, whatever gcc I use (2.95.3 or 3.2.3), on the
> following do_hash() function, and about 40% faster when used on
> local variables.
>
> Interesting :-)

Not that much finally, because I cannot reproduce the slowdown I initially
observed with the original function on local variables. I think I may have
had a wrong type somewhere or a particular operation which prevented gcc
from fully optimizing the macro :-/

So at the moment, both the original and my version are the same speed on
local variables on athlon-xp.

BTW, I don't understand why, but I've just noticed that the Alpha is 25%
slower on my version when used on local variables !

So my version is only interesting when working on indirect variables, which
is never the case in the kernel... Never mind, that was just a try.

For info, here's what I measure here on the original version :

- athlon-xp : 24 cycles, whatever -march/-mcpu
- alpha ev6 : -mcpu=ev5 : 22 cycles
-mcpu=ev6 : 24 cycles
- sparc64 : default : 26 cycles
-mcpu=v9 : 24 cycles
-mcpu=ultrasparc: 19 cycles (18 cycles for my version here)

Considering that the Alpha and the UltraSparc can issue up to 4 instruction
per cycle, I wonder whether it would be worse trying to implement such a hash
in assembler, optimized for each processor, with a default fall-back to the
C function for archs that have not been implemented.

Cheers,
Willy