Current perturb shift code is like following:

    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = mask & ((i << 2) + i + perturb + 1);

This loop is start after first conflict. It means perturb == hash for first conflict.

The purpose of perturb shift is avoid long conflict chain when keys more
than two have hashes their lower-bit is same. So first perturb should be hash >> PERTURB_SHIFT.

example: Consider about ma_keys == 16 and keys are [1, 17, 33, 49, 65].
Current perturb
1. hash(1) & (16-1) == 1; 1 uses ix==1 slot.
2. hash(17) & (16-1) == 1; ix==1 conflicts; Next ix is mask & (3 + 17 + 1) == 5; use ix==5 slot.
3. hash(33) & (16-1) == 1; ix==1 conflicts; Next ix is mask & (3 + 33 + 1) == 5; ix==5 conflicts; ...

When first perturb = hash >> PERTURB_SHIFT:
1. hash(1) & (16-1) == 1; 1 uses ix==1 slot.
2. hash(17) & (16-1) == 1; ix==1 conflicts; Next ix is mask & (3 + (17>>5) + 1) == 4; use ix==4 slot.
3. hash(33) & (16-1) == 1; ix==1 conflicts; Next ix is mask & (3 + (33>>5) + 1) == 5; use ix==5 slot.


While it's difficult to see performance difference from benchmark, this should be decrease possibility of 2nd conflict.

Good catch!  I agree - and I wrote this code to begin with, so my opinion should count ;-)

I agree and my opinion counts even more because I long ago made this change for setobjects ;-)

General comment on the patch: I believe per PEP7, we're still sticking to ANSI C (aka C89), and specifically, "all declarations must be at the top of a block (not necessarily at the top of function".

The patch assumes lax standards compliance (or C99+ compliance), declaring variables in the for loop initializer section and midway through blocks. This should be changed to declare all variables at the top of blocks, and not in for loop initializer sections.

Removing those unrelated changes looks like it would dramatically reduce the churn too, making review easier.

josh.r:

>  I believe per PEP7, we're still sticking to ANSI C (aka C89), and specifically, "all declarations must be at the top of a block (not necessarily at the top of function".

Python 3.6 branch allows some C99 features.
https://www.python.org/dev/peps/pep-0007/#c-dialect

> Removing those unrelated changes looks like it would dramatically reduce the churn too, making review easier.

While I think refactoring around changes is practical [1], I agree that I made too much change.  I'll reduce diff size.

[1] Changing without refactoring is hard sometimes. Whole file refactoring
    without actual change may cause many conflicts against other patches.

Could anyone review the patch?
I'm starting to #28199.  But it must conflict with this patch.

Fixed conflict with current 3.6 branch, and added NEWS entry.

While I think this patch is safe, I need LGTM from another committer
because I'm new committer.

Could Tim or Raymond review the patch before 3.6beta2?

LGTM!  Ship it :-)

Added comments on Rietveld.

LGTM. But why you moved the declaration of perturb?

New changeset cf2778fd7acb by INADA Naoki in branch '3.6':
Issue #28201: Dict reduces possibility of 2nd conflict in hash table.
https://hg.python.org/cpython/rev/cf2778fd7acb

New changeset 80b01cd94a63 by INADA Naoki in branch 'default':
Issue #28201: Dict reduces possibility of 2nd conflict in hash table.
https://hg.python.org/cpython/rev/80b01cd94a63

Thank you, Tim and Serhiy.  My first commit has been pushed now!

Serhiy:
Since I prefer putting variable declaration near it's usage, and
PEP 7 permits it since Python 3.6.