GeezerVison

I like this in general.

I'm not convinced by (1) as it may lead to more collisions. I'd be happy to be proved wrong, if you have data.
(2) and (3) are definitely improvements.

Can you try to write a micro-benchmark to show the speedup?

cc @pablogsal @methane @serhiy-storchaka

Can you try to write a micro-benchmark to show the speedup?

I'll make an attempt at it and report back, but I think it'll be hard to get enough signal even w/ a microbenchmark. When I originally measured this against re-played Instagram traffic we saw a reduction in _PyType_Lookup from 1.7% of CPU usage to 1.6% of CPU usage. So it is a pretty small win overall, and may be dwarfed by all the other interpreter overhead in a benchmark.

This is great work.

I agree with @markshannon, I think that I am sold with (2) and (3) but I am quite not convinced by (1), but I think it should be fine because I expect quite a small amount of cache misses.

This is great work.

I agree with @markshannon, I think that I am sold with (2) and (3) but I am quite not convinced by (1), but I think it should be fine because I expect quite a small amount of cache misses.

One additional tweak here could be to do >> 2 on 32-bit platforms, although I'm not sure how much that'll really matter either.

One additional tweak here could be to do >> 2 on 32-bit platforms, although I'm not sure how much that'll really matter either.

Objects are aligned by 16byte on 64bit and 8byte on 32bit platforms. So >>4 on 64bit and >>3 on 32bit would be better.

Objects are aligned by 16byte on 64bit and 8byte on 32bit platforms. So >>4 on 64bit and >>3 on 32bit would be better.

Since unicode objects is larger than minimum alignment, more than 4bits are not random.

>>> sys.getsizeof("a")
50
>>> (50+15)//16
4

But lower bits of tp_version_tag are more random than higher bits. So I think no need to throw away all non-random lower bits in unicode pointer.

But lower bits of tp_version_tag are more random than higher bits. So I think no need to throw away all non-random lower bits in unicode pointer.

I forgot about we use only 12bits for hash. All bits are important. I posted benchmark result of >>3 in bpo. I will benchmark >>4 and >>5 too.

About >>4 shift, see also the _Py_HashPointer() function:

    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
       excessive hash collisions for dicts and sets */
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4));

Objects are aligned by 16byte on 64bit and 8byte on 32bit platforms. So >>4 on 64bit and >>3 on 32bit would be better.

Should we update _Py_HashPointer()?

I forgot about we use only 12bits for hash. All bits are important. I posted benchmark result of >>3 in bpo. I will benchmark >>4 and >>5 too.

Performance difference between >>3, >>4, and >>5 are not significant.
All of them are faster than status quo (result).

I think this change is significant enough to have a news entry.

Can you try to write a micro-benchmark to show the speedup?

@vstinner I've added a small C micro-benchmark in https://bugs.python.org/issue43452

obj hash: 0m6.222s
str hash: 0m6.327s
baseline: 0m6.784s

Thanks for proving that the optimization actually makes the code faster :-)

Thanks a lot @DinoV for the fantastic work!