atom feed30 messages in org.python.python-dev[Python-Dev] String hash function mul...
FromSent OnAttachments
Raymond HettingerApr 13, 2004 8:00 pm 
Jeff EplerApr 13, 2004 9:10 pm 
Bob IppolitoApr 13, 2004 9:26 pm 
Jeff EplerApr 13, 2004 10:04 pm 
Raymond HettingerApr 13, 2004 10:17 pm 
Jeff EplerApr 13, 2004 11:10 pm 
Guido van RossumApr 13, 2004 11:26 pm 
Tim PetersApr 13, 2004 11:56 pm 
Jeff EplerApr 14, 2004 9:08 am 
Raymond HettingerApr 14, 2004 12:06 pm 
Andrew MacIntyreApr 14, 2004 3:23 pm 
Jeff EplerApr 14, 2004 3:35 pm 
Mike PallApr 14, 2004 5:50 pm 
Tim PetersApr 14, 2004 11:14 pm 
Michael HudsonApr 15, 2004 7:05 am 
Mike PallApr 15, 2004 9:36 am 
Guido van RossumApr 15, 2004 10:27 am 
Jeremy HyltonApr 15, 2004 10:38 am 
Guido van RossumApr 15, 2004 10:42 am 
Mike PallApr 15, 2004 11:56 am 
Mike PallApr 15, 2004 11:56 am 
Skip MontanaroApr 15, 2004 11:59 am 
Michael HudsonApr 15, 2004 1:27 pm 
Raymond HettingerApr 15, 2004 2:22 pm 
Thomas HellerApr 15, 2004 2:31 pm 
"Martin v. Löwis"Apr 15, 2004 3:07 pm 
Jeremy HyltonApr 15, 2004 11:26 pm 
Tim PetersApr 16, 2004 12:18 am 
"Martin v. Löwis"Apr 16, 2004 2:00 am 
Andrew MacIntyreApr 16, 2004 9:14 pm 
Subject:[Python-Dev] String hash function multiplier
From:Jeff Epler (jep@unpythonic.net)
Date:Apr 13, 2004 10:04:49 pm
List:org.python.python-dev

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