Re: Algoritmic Complexity Attacks and 2.4.20 the dcache code

[Willy Tarreau (willy@w.ods.org)]

On Sat, May 31, 2003 at 01:12:10AM -0700, David S. Miller wrote:
>    From: Willy TARREAU <willy@xxxxxxxxx>
>    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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/