runtime: memhash: use simple loop for short strings

[adonovan]

I noticed in the course of developing starlark-go that maphash.String, which wraps runtime.memhash and thus runtime.aeshashbody, is slower than a trivial loop-based hash such as FNV for short strings (len <= 12). You might want to see whether there are gains to be made by changing runtime.memhash.

In the M1 benchmark below, "hard" is the AES 128-bit hash, soft is the FNV byte-at-a-time hash.

BenchmarkStringHash/hard-1-8         	425380128	         2.724 ns/op // slower
BenchmarkStringHash/soft-1-8         	968800584	         1.253 ns/op
BenchmarkStringHash/hard-2-8         	285782469	         4.155 ns/op // slower
BenchmarkStringHash/soft-2-8         	482670777	         2.543 ns/op
BenchmarkStringHash/hard-4-8         	238793694	         5.426 ns/op // slower
BenchmarkStringHash/soft-4-8         	359522328	         3.318 ns/op
BenchmarkStringHash/hard-8-8         	180634999	         6.658 ns/op // slower
BenchmarkStringHash/soft-8-8         	241373414	         4.995 ns/op
BenchmarkStringHash/hard-16-8        	205045033	         5.823 ns/op
BenchmarkStringHash/soft-16-8        	144273086	         8.322 ns/op
BenchmarkStringHash/hard-32-8        	206178392	         5.844 ns/op
BenchmarkStringHash/soft-32-8        	80871846	        14.96 ns/op
BenchmarkStringHash/hard-64-8        	175336156	         6.891 ns/op
BenchmarkStringHash/soft-64-8        	42610798	        28.30 ns/op
BenchmarkStringHash/hard-128-8       	125781333	         9.542 ns/op
BenchmarkStringHash/soft-128-8       	18739946	        64.47 ns/op
BenchmarkStringHash/hard-256-8       	59081041	        20.63 ns/op
BenchmarkStringHash/soft-256-8       	10185776	       118.5 ns/op
BenchmarkStringHash/hard-512-8       	23744743	        51.08 ns/op
BenchmarkStringHash/soft-512-8       	 5342551	       224.6 ns/op
BenchmarkStringHash/hard-1024-8      	10823535	       111.2 ns/op
BenchmarkStringHash/soft-1024-8      	 2731977	       438.0 ns/op

[cagedmantis]

cc @golang/runtime

[randall77]

What does the benchmark code look like?

BenchmarkStringHash/hard-1-8         	425380128	         2.724 ns/op // slower
BenchmarkStringHash/hard-2-8         	285782469	         4.155 ns/op // slower
BenchmarkStringHash/hard-4-8         	238793694	         5.426 ns/op // slower
BenchmarkStringHash/hard-8-8         	180634999	         6.658 ns/op // slower

This variance surprises me, because the hash for 1-15 bytes uses exactly the same hash operations. It only varies a bit in how it initializes the vector register with 1-15 bytes of string contents.

[adonovan]

The benchmark is here, and the soft and hard algorithms are here, but note that I deleted the if len < 12 { soft } fallback logic in the numbers I posted above.

[randall77]

One of the things to consider here is that the current hash is designed to make it hard for an adversary to engineer collisions. We'd want a similar property for any replacement. As far as I know it is easy to engineer collisions with FNV hashing. (But maybe it would be harder if we picked the prime randomly somehow?)
Maybe for 1 and possibly 2 byte hashes collisions aren't that big a deal.

[ericlagergren]

Naively, the variance makes sense for the arm64 aeshash.

Presumably some of the overhead for 12-byte strings is just because aeshash is implemented in assembly and is opaque to the compiler.

Perhaps it makes sense to use memhashFallback for short strings?