[issue28201] dict: perturb shift should be done when first conflict

[Donald Stufft]

Changes by Donald Stufft :


--
pull_requests: +1110

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


--
resolution:  -> fixed
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

INADA Naoki added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Roundup Robot]

Roundup Robot added the comment:

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

--
nosy: +python-dev

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

LGTM. But why you moved the declaration of perturb?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


Added file: http://bugs.python.org/file44981/dict-perturb-shift4.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


Added file: http://bugs.python.org/file44980/dict-perturb-shift3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Added comments on Rietveld.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Tim Peters]

Tim Peters added the comment:

LGTM!  Ship it :-)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

INADA Naoki added the comment:

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

INADA Naoki added the comment:

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

--
Added file: http://bugs.python.org/file44966/dict-perturb-shift2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


--
stage:  -> patch review
type:  -> performance

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

INADA Naoki added the comment:

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

--
assignee:  -> inada.naoki

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


Added file: http://bugs.python.org/file44774/dict-perturb-shift.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

INADA Naoki added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Josh Rosenberg]

Josh Rosenberg added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Josh Rosenberg]

Josh Rosenberg added the comment:

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.

--
nosy: +josh.r

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

Changes by INADA Naoki :


--
keywords: +patch
Added file: http://bugs.python.org/file44759/dict-perturb-shift.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Raymond Hettinger]

Raymond Hettinger added the comment:

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

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Tim Peters]

Tim Peters added the comment:

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

--
nosy: +tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
nosy: +rhettinger, serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28201] dict: perturb shift should be done when first conflict

[INADA Naoki]

New submission from INADA Naoki:

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.

--
components: Interpreter Core
messages: 276936
nosy: methane
priority: normal
severity: normal
status: open
title: dict: perturb shift should be done when first conflict
versions: Python 3.6

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com