Hashing (u)int8

[Ondrej]

Hey,

I had int as a key in my map and later realised I only used 100 or so values, so swapped it for a uint8, expecting a minor speed increase, but saw a major slowdown instead. To recreate this, I tried this simple microbenchmark and was surprised by the difference between (u)int8/16 and int/int32/int64.

https://play.golang.org/p/RxmtASRiS4

In my actual code I have the key in a slice, so I expected []uint8 to be more cache friendly than []int, but I guess any potential cache friendliness was outweighed by this hashing performance difference.

Thanks for any info on this.

[Ayan George]

It looks like any type that isn't the size of a word is slower.
Probably due to all sort of masking and maybe shifting it has to do.

-ayan

[Damian Gryski]

The runtime has optimized map implementations for strings, int32 and int64-sized thing

There is no optimized implementation for int8-sized things -- just use an array.

Damian

[Daniel Skinner]

It's surprising but it's not. Who would have guessed 8bits would be more expensive on a 64bit platform.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Ondrej]

Oh yeah, preallocating 256 elements is fine. It's a bit expensive to allocate 2**16 for the int16 case, so I'll have to do with the slow hashing there - or are there any plans for speeding up that one?

Cheers, this is helpful.

O.

[Damian Gryski]

This ends up being only half a megabyte of memory (65536 x 8 byte pointers) for the array-based solution.

You can always write your own hash table, or convert your uint16 key to a uint32 for lookup purposes. (I've done the same thing with floats to speed up a float64-keyed hash table.)

Damian

[Ondřej Kokeš]

Good points! I'll keep this in mind!

Thanks again

--

You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.

To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/1iSmPQ6vrl0/unsubscribe.

To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.