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:Raymond Hettinger (pyt@rcn.com)
Date:Apr 13, 2004 10:17:18 pm
List:org.python.python-dev

[Jeff Epler]

With -O2 -mcpu=i686 or newer, gcc uses "imul" for both 100003 and 65599, rather than shifts and adds.

[Bob Ippolito]

It's not expected that GCC optimize an integer constant into shifts on its own.

Right, the actual diff is:

*** 1145,1151 **** p = (unsigned char *) a->ob_sval; x = *p << 7; while (--len >= 0) ! x = (1000003*x) ^ *p++; x ^= a->ob_size; if (x == -1) x = -2; --- 1152,1158 ---- p = (unsigned char *) a->ob_sval; x = *p << 7; while (--len >= 0) ! x = (x << 6) + (x << 16) - x + (long)*p++; x ^= a->ob_size; if (x == -1) x = -2;

I guess the real question for Raymond is, does it really make a measurable difference?

Yes, the loop runs 20% faster on my Pentium III. The speedup ought to be much more dramatic on the Pentium IV (where the integer ALU instructions speedup from 1 clock to 0.5 clocks while the latency on integer multiplication slows down from 4 clocks to 14-18 clocks).

And what effect does it have on pickled dicts (or other such hash-using data structures), if any?

The test suite runs fine. Dicts may display in a different order than in previous pythons. That may upset some doctests if the writer didn't take Tim's documented advice about making tests that do not depend on display order.

Raymond