[Python-Dev] String hash function multiplier

[Jeff Epler]

On Tue, Apr 13, 2004 at 09:30:28PM -0400, Bob Ippolito wrote:
> It's not expected that GCC optimize an integer constant into shifts on  
> its own.

But gcc does! -- with -mcpu=i386, 65599 is optimized into some shifts,
and 100003 is optimized into some very painful use of "lea" (x is in
edx):
   lea    (%edx,%edx,4),%eax  //  eax = 5 * edx
   lea    (%eax,%eax,4),%eax  //  eax = 25 * edx
   lea    (%eax,%eax,4),%eax  //  eax = 125 * edx
   lea    (%eax,%eax,4),%eax  //  eax = 625 * edx
   lea    (%eax,%eax,4),%eax  //  eax = 3125 * edx
   lea    (%eax,%eax,4),%eax  //  eax = 15625 * edx
   shl    $0x5,%eax           //  eax = 50000 * edx
   add    %edx,%eax           //  eax = 50001 * edx
   lea    (%edx,%eax,2),%edx  //  edx = 100003 * edx
On the newer x86 CPUs (starting at i686 / k6) imul is preferred by the
optimizer.

Here's what 65599 gives, with -mcpu=i386 (x is in edx again):
   mov    %edx,%eax           //  eax = edx
   shl    $0xa,%eax           //  eax = edx * 1024
   add    %edx,%eax           //  eax = edx * 1025
   shl    $0x6,%eax           //  eax = edx * 65600
   sub    %edx,%eax           //  eax = edx * 65599
   mov    %eax,%edx           //  edx = eax

If gcc can emit these tortured instruction sequences, but chooses not
to, I have to suspect it knows the properties of the CPU better than me.

Jeff