[Python-Dev] Algoritmic Complexity Attack on Python

[Jeff Epler]

On Fri, May 30, 2003 at 11:18:14AM -0500, Scott A Crosby wrote:
> On 
> 
>    http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/LengthEffects.png
> 
> UHASH exceeds the performance of perl's hash function, which is
> simpler than your own.

I notice that you say "with strings longer than around 44-bytes,
UHASH dominates all the other hash functions, due in no small part to its
extensive performance tuning and *hand-coded assembly routines.*"
[emphasis mine]  It's all well and good for people who can run your
hand-coded VAX assembly, but when Intel's 80960* comes out and people
start running Unix on it, won't they be forced to code your hash function
all over again?  Since everybody has hopes for Python beyond the VAX
(heck, in 20 years VAX might have as little as 5% of the market --
anything could happen) there has been a consious decision not to hand-code
anything in assembly in Python.

Jeff
* The Intel 80960, in case you haven't heard of it, is a superscalar
  processor that will require highly-tuned compilers and will run like
  a bat out of hell when the code is tuned right.  I think it's capable
  of one floating-point and two integer instructions per cycle!