[Python-Dev] String hash function multiplier (original) (raw)

Jeff Epler jepler at unpythonic.net
Tue Apr 13 22:04:10 EDT 2004

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

More information about the Python-Dev mailing list