homepage

In the discussion of issue14621 it was noted that much more complex hash algorithms can overtake the current one due to the fact that they process more data at a time. Here is a patch that implements this idea for the current algorithm. Also code duplication removed.
Microbenchmarks:
$ ./python -m timeit -n 1 -s "t = b'a' * 10**8" "hash(t)"
$ ./python -m timeit -n 1 -s "t = 'a' * 10**8" "hash(t)"
$ ./python -m timeit -n 1 -s "t = '\u0100' * 10**8" "hash(t)"
$ ./python -m timeit -n 1 -s "t = '\U00010000' * 10**8" "hash(t)"
Results on 32-bit Linux on AMD Athlon 64 X2 4600+:
 original patched speedup
bytes 181 msec 45.7 msec 4x
UCS1 429 msec 45.7 msec 9.4x
UCS2 179 msec 92 msec 1.9x
UCS4 183 msec 183 msec 1x
If the idea is acceptable, I will create benchmarks for short strings.

yes please!
Any reason you're using an unsigned int in your loop instead of a Py_uhash_t?

> Any reason you're using an unsigned int in your loop instead of a Py_uhash_t?
In fact, there is no serious reason. This should be the type aligned as minimal alignment of void*, size_t and Py_hash_t. Since de facto Py_uhash_t is size_t, then we can use size_t.

The patch is too optimistic, it gives different results depending on the alignment of the memory buffer:
>>> b = b"abcd"*100
>>> hash(b[1:])
7264687738704559842
>>> hash(memoryview(b)[1:])
9054791208347464792
>>> memoryview(b)[1:] == b[1:]
True

Here is a test case for the hash/alignment issue.

> The patch is too optimistic, it gives different results depending on the alignment of the memory buffer:
So this method is not applicable for a byte. Here is a patch only for strings.
If a fast hash for bytes/memoryview is desirable, I can write a fast robust implementation for nonaligned data. But this will be more cumbersome and a bit slower.

> Here is a test case for the hash/alignment issue.
I think here should be a test for a shifted data. Something like hash(b'abcd...') == hash(memoryview(b'xabcd...')[1:]).

Oh, I see, it's already here.

> If a fast hash for bytes/memoryview is desirable, I can write a fast
> robust implementation for nonaligned data. But this will be more
> cumbersome and a bit slower.
Unaligned accesses are not a problem on x86(-64), but they will segfault
(bus error, IIRC) on other architectures such as SPARC, unfortunately.
(blame RISC for being really too "simplified")

FWIW, on x86/x64 gcc often generates identical code for x = y and
memcpy(x, y, 8). See e.g. the PACK_SINGLE and UNPACK_SINGLE macros in
Objects/memoryobject.c.
I didn't look at the patch yet, just an idea.

> Unaligned accesses are not a problem on x86(-64), but they will segfault
(bus error, IIRC) on other architectures such as SPARC, unfortunately.
On x86(-64) this kills performance and makes the optimization be senseless.
> FWIW, on x86/x64 gcc often generates identical code for x = y and
memcpy(x, y, 8).
The code can be identical, but the time will differ significantly for aligned and non-aligned data.

> The code can be identical, but the time will differ significantly for
> aligned and non-aligned data.
Of course, but in most cases the data *is* aligned, so only code that does
something quite special pays the performance penalty.

Stefan, thank you for the suggestion. The test showed that, in fact, at least under some x86 there is no performance decrease when using memcpy on nonaligned data. This is good news. The code can left simple and even some doubtful potential undefined behavior was removed.
Additional microbenchmarks:
$ ./python -m timeit -n 1 -s "t = memview(b'a' * 10**8)" "hash(t)"
$ ./python -m timeit -n 1 -s "t = memview(b'a' * 10**8)[1:]" "hash(t)"
$ ./python -m timeit -n 1 -s "t = memview(b'a' * 10**8)[8:]" "hash(t)"
 original patched speedup
bytes 181 msec 46 msec 3.9x
UCS1 429 msec 46.2 msec 9.3x
UCS2 179 msec 91.9 msec 1.9x
UCS4 183 msec 184 msec 1x
memview() 362 msec 91.7 msec 3.9x
memview()[1:] 362 msec 93.2 msec 3.9x
memview()[8:] 362 msec 92.4 msec 3.9x
I don't know how it will be on other platforms.

New changeset 797de1864fd9 by Antoine Pitrou in branch '3.3':
Add a test for hashing of unaligned memory buffers (from issue #16427).
http://hg.python.org/cpython/rev/797de1864fd9
New changeset 9cb1366b251b by Antoine Pitrou in branch 'default':
Add a test for hashing of unaligned memory buffers (from issue #16427).
http://hg.python.org/cpython/rev/9cb1366b251b 

fast_hash_3.patch is a litte bit (6%) slower for Unicode string shorter than 10 characters, but much faster for string equal or longer than 100 characters (up to 10x faster).
I used the str type and disabled its cache ("_PyUnicode_HASH(self) = x;" in unicode_hash()) to run my benchmark.
Summary    |  original |    patched
---------------+------------+---------------
Length 1    | 231 ns (*) |  244 ns (+6%)
Length 3    | 238 ns (*) |  253 ns (+6%)
Length 10   | 254 ns (*) |     251 ns
Length 20   | 280 ns (*) |  256 ns (-8%)
Length 100   | 528 ns (*) | 321 ns (-39%)
Length 10 ** 4 | 32 us (*) | 9.49 us (-70%)
Length 10 ** 8 | 329 ms (*) | 104 ms (-68%)
---------------+------------+---------------
Total     | 329 ms (*) | 104 ms (-68%)

Does anyone know if fast_hash_3.patch may reduce the quality of the hash function? (May the patched hash function produce more collisions? The "Avalanche effect" thing.)

Well, the quality of the hash function is clearly reduced:
>>> hash("abcdefgh") & 0xff
206
>>> hash("abcdefgi") & 0xff
206
>>> hash("abcdefgj") & 0xff
206
>>> hash("abxxxxxx") & 0xff
206
>>> hash("aaaaaa11") & 0xff
206
>>> hash("aaaaaa12") & 0xff
206
Now to know if that may produce slowdowns in some situations... (dicts and sets have a sophisticated probing algorithm which takes into account the whole hash value, not the masked one).

> (dicts and sets have a sophisticated probing algorithm which takes into account the whole hash value, not the masked one).
Correct, so your specific example should not be a problem since the
whole hash value is different for the 6 hash values.
> Now to know if that may produce slowdowns in some situations...
pybench and perf.py can be used to measure performances of the patch.
The speedup may not be detected, but a slowdown would be detected at
least.
2013年4月9日 Antoine Pitrou <report@bugs.python.org>:
>
> Antoine Pitrou added the comment:
>
> Well, the quality of the hash function is clearly reduced:
>
>>>> hash("abcdefgh") & 0xff
> 206
>>>> hash("abcdefgi") & 0xff
> 206
>>>> hash("abcdefgj") & 0xff
> 206
>>>> hash("abxxxxxx") & 0xff
> 206
>>>> hash("aaaaaa11") & 0xff
> 206
>>>> hash("aaaaaa12") & 0xff
> 206
>
>
> Now to know if that may produce slowdowns in some situations... (dicts and sets have a sophisticated probing algorithm which takes into account the whole hash value, not the masked one).
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <http://bugs.python.org/issue16427>
> _______________________________________

Note that the patch uses type punning through a union: while GCC allows this, it's not allowed by ANSI (although since we're using a char [], it's somewhat a grey area). An aggresive compiler could optimiza the read/write away.

> Note that the patch uses type punning through a union
What is the standard and portable way to cast an array of bytes to size_t?
2013年4月9日 Charles-François Natali <report@bugs.python.org>:
>
> Charles-François Natali added the comment:
>
> Note that the patch uses type punning through a union: while GCC allows this, it's not allowed by ANSI (although since we're using a char [], it's somewhat a grey area). An aggresive compiler could optimiza the read/write away.
>
> ----------
> nosy: +neologix
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <http://bugs.python.org/issue16427>
> _______________________________________

> > Note that the patch uses type punning through a union
>
> What is the standard and portable way to cast an array of bytes to size_t?
I'd expect just casting the pointer type before dereferencing:
unsigned char *p;
...
hash = (multiplier * hash) ^ *((Py_uhash_t *)p);
(don't use size_t, use Py_uhash_t)

> pybench and perf.py can be used to measure performances of the patch.
> The speedup may not be detected, but a slowdown would be detected at
> least.
The slowdown would only occur for specific, well-chosen patterns. Also it may make DoS attacks easier.
(remember the reason we randomized hashes is so that it's hard for attackers to find collisions)

> I'd expect just casting the pointer type before dereferencing:
>
> unsigned char *p;
> ...
> hash = (multiplier * hash) ^ *((Py_uhash_t *)p);
>
> (don't use size_t, use Py_uhash_t)
Is p guaranteed to be size_t aligned?
If not, unaligned access can segfault (e.g. on Sparc IIRC).
> Also it may make DoS attacks easier.
Indeed.
And the increase in collision you demonstrated in your previous
message worries me (both security and performance wise).

> Is p guaranteed to be size_t aligned?
> If not, unaligned access can segfault (e.g. on Sparc IIRC).
Apparently yes.

> Note that the patch uses type punning through a union: while GCC allows > this, it's not allowed by ANSI.
I believe it's legal under C99 + TC3.

I was investigating a callgrind dump of my code, showing how badly unicode_hash() was affecting my performance. Using google's cityhash instead of the builtin algorithm to hash unicode objects improves overall performance by about 15 to 20 percent for my case - that is quite a thing.
Valgrind shows that the number of instructions spent by unicode_hash() drops from ~20% to ~11%. Amdahl crunches the two-fold performance increase to the mentioned 15 percent.
Cityhash was chosen because of it's MIT license and advertisement for performance on short strings.
I've now found this bug and attached a log for haypo's benchmark which compares native vs. cityhash. Caching was disabled during the test. Cityhash was compiled using -O3 -msse4.2 (cityhash uses cpu-native crc instructions). CPython's unittests fail due to known_hash and gdb output; besides that, everything else seems to work fine.
Cityhash is advertised for it's performance with short strings, which does not seem to show in the benchmark. However, longer strings perform *much* better.
If people are insterested, i can repeat the test on a armv7l

> I was investigating a callgrind dump of my code, showing how badly
> unicode_hash() was affecting my performance.
Can you tell us about your use case?
There are several CityHash variants, which one did you use? CityHash64?

It's a cache sitting between an informix db and and an internal web service. Stuff comes out of db, processed, json'ifed, cached and put on the wire. 10**6s of strings pass this process per request if uncached...
I use CityHash64WithSeed, the seed being cpython's hash prefix (which I don't care about but found reassuring to put in anyway)

Here are some benchmarks for a arm7l on a rk30-board. CityHash was compiled with -mcpu=native -O3.
CityHash is around half as fast as the native algorithm for small strings and way, way slower on larger ones. My guess would be that the complex arithmetic in cityhash outweights the gains of better scheduling.
The results are somewhat inconclusive, as the performance increases again for very long strings.

> Here are some benchmarks for a arm7l on a rk30-board. CityHash was
> compiled with -mcpu=native -O3.
The results look unbelievable. If you take "Length 10 ** 4", it means
arm7l is able to hash 20 GB/s using the default unicode hash function.
(did you disable caching?)

The 10**4-case is an error (see insane %), I've never been able to reproduce. Having done more tests with fixed cpu frequency and other daemons' process priority reduced, cityhash always comes out much slower on arm7l.

Here are more benchmarks of vanilla 3.4 vs. cityhash vs. fast_hash_3 on both arm7l and x86-64. The patch was applied varbatim, only caching disabled. On arm7l, the cpu was fixed to maximum freq (it seems to take ages to switch frequencies, at least there is a lot of jitter with ondemand). The cityhash implementation was compiled with -O3 on both platforms and -msse4.2 on x86-64.
CityHash and fh3 come out much better than vanilla on x86-64 with cityhash being slightly faster (which is surprising). On ARM7 CityHash performs much worse than vanilla and fh3 significantly better.

I'm not sure that micro-benchmarks are revelant for this issue. Hash collisions may have an higher cost than the gain of a faster hash function. Some people feel also concerned by the dict denial of service issue.
It would be interesting to compare performances using the benchmark suite:
http://hg.python.org/benchmarks/ 

Antoine, I have addressed your concern "Well, the quality of the hash function is clearly reduced" in patch http://hg.python.org/features/pep-456/rev/765930d944a5
>>> s = set()
>>> for i in range(256):
... s.add(hash("abcdfeg" + chr(i)) & 0xff)
... 
>>> len(s)
256
>>> s = set()
>>> for i in range(256):
... s.add(hash("abcdfeghabcdefg" + chr(i)) & 0xff)
... 
>>> len(s)
256

Shouldn't this issue be obsoleted?

Since issue19183 supersedes it, yes.