Byte & String collection hash performance; a modest proposal for change.

    the hash algorithm used for ByteString in Squeak and Pharo is good for "small" strings and overkill for large strings.  It is important in many applications to get well distributed string hashes, especially over the range of strings that constitute things like method names, URLs, etc.  Consequently, the current algorithm includes every character in a string.  This works very well for "small" strings and results in very slow hashes (and hence long latencies, because the hash is an uninterruptible primitive) for large strings, where large may be several megabytes.

Let's look at the basic hash algorithm.  The following method is translated my compiler machinery in VMMaker from Smalltalk to C.  It creates a primitive function called primitiveStringHash, and so when invoked in normal Smalltalk code the method below invokes its C translation; neat.

This function is invokes by a rather convoluted chain:

String>>hash

"#hash is implemented, because #= is implemented"

"ar 4/10/2005: I had to change this to use ByteString hash as initial 

hash in order to avoid having to rehash everything and yet compute

the same hash for ByteString and WideString.

md 16/10/2006: use identityHash as initialHash, as behavior hash will 

use String hash (name) to have a better hash soon.

eem 4/17/2017 it's not possible to use String hash (name) for the

initial hash because that would be recursive."

^self class stringHash: self initialHash: ByteString identityHash

and the generic string implementation is

String class>>stringHash: aString initialHash: speciesHash

"Answer the hash of a byte-indexed string, using speciesHash as the initial value.

 See SmallInteger>>hashMultiply."

| hash |

hash := speciesHash bitAnd: 16rFFFFFFF.

1 to: aString size do:

[:pos |

hash := (hash + (aString basicAt: pos)) hashMultiply].

^hash

(it simply omits the primitive declaration).

As of yesterday the inner loop was written differently by Andres Valoud to avoid overflow:

hash := hash + (aByteArray basicAt: pos).

The problem here is that the Smalltalk-to-C translation machinery is naive and entirely incapable of transforming 

low := hash bitAnd: 16383.

hash := (16r260D * low + ((16r260D * (hash bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384)) bitAnd: 16r0FFFFFFF.

into

hash := hash * 1664525 bitAnd: 16r0FFFFFFF

The reformulation makes the primitive a little quicker, gaining for larger strings, but still suffers the high invocation overhead as described in the Cog Primitive Performance thread.

In looking at this I've added a primitive for hashMultiply; primitive #159 implements precisely self * 1664525 bitAnd: 16r0FFFFFFF for SmallInteger and LargePositiveInteger receivers, as fast as possible in the Cog JIT.  With this machinery in place it's instructive to compare the cost of the primitive against the non-primitive Smalltalk code.

First let me introduce a set of replacement hash functions, newHashN.  These hash all characters in strings up to a certain size, and then no more than that number for larger strings.  Here are newHash64 and newHash2048, which use pure Smalltalk, including an inlined hashMultiply written to avoid SmallInteger overflow.  Also measured are the obvious variants newHash128, newHash256, newHash512 & mewHash1024.