Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.datemas.de!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.050
X-Spam-Evidence: '*H*': 0.90; '*S*': 0.00; 'bits': 0.09; 'python': 0.11; '2.7': 0.14; 'bucket': 0.16; 'once.': 0.16; 'shifts': 0.16; 'stumbled': 0.16; 'unequal': 0.16; 'unexpected': 0.16; 'url:file': 0.16; 'wrote:': 0.18; 'code,': 0.22; 'adds': 0.24; 'header:In- Reply-To:1': 0.27; 'am,': 0.29; 'compared': 0.30; 'message- id:@mail.gmail.com': 0.30; 'comments': 0.31; "d'aprano": 0.31; 'keys': 0.31; 'steven': 0.31; 'checked': 0.32; 'url:python': 0.33; 'received:google.com': 0.35; 'url:org': 0.36; 'starting': 0.37; 'sometimes': 0.38; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'most': 0.60; 'guarantee': 0.63; 'reached': 0.63; 'within': 0.65; 'mar': 0.68; 'upper': 0.74; 'dict,': 0.84; 'url:cpython': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=KYREHO4WFel8n57mHWeWEhpXiEdCABslwFz7k7uAbuE=; b=lz7ekWnwwe+aPGPZoGphwiX2A9tKvN6gkvq1+rf+sypeuBEzO5iwg0AntpAt0reXuJ m4uX64gO/06EputtO0GGTCsddN8ca2oTv+d98rXKcHZe9m5jOW2IbNCvY3ZBpD5qVSOh e0cNrfcP7gds3m/kVpI94R7rEeDX3hU6sjcOumTRzjn56hFmKlTV1WiOfcpSi1wz6nxo 4z4ApOAmzU5NyY9IOOzEhRVGus5TK/NUUn2QuSr/83511jpRFP8PvCj9RnEn8mLAhZij 2bCH+qeEpgASvX/4P4973IQy+He0VwDDzpuE+GClybiol5PqhlzxN46qGztl/++KP6dg rh6w==
X-Received: by 10.68.134.198 with SMTP id pm6mr35461386pbb.9.1395173771428; Tue, 18 Mar 2014 13:16:11 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <53285617$0$29994$c3e8da3$5496439d@news.astraweb.com>
References: <53285617$0$29994$c3e8da3$5496439d@news.astraweb.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 18 Mar 2014 14:15:31 -0600
Subject: Re: Unexpected comparisons in dict lookup
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.8258.1395173776.18130.python-list@python.org>
Lines: 15
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1395173776 news.xs4all.nl 2834 [2001:888:2000:d::a6]:59028
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:68514

On Tue, Mar 18, 2014 at 8:20 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> I stumbled across this unexpected behaviour with Python 2.7 and 3.3. When
> you look up a key in a dict, the key is sometimes compared against other
> keys twice instead of just once.

>From what I can see in the code, it adds a perturbation based on the
upper bits of the hash value to the probing scheme, to reduce
collisions for keys with unequal hashes.  On the downside, this
cancels the guarantee that each bucket can only be checked at most
once.  The perturbation gradually shifts to 0 after a few iterations,
so every bucket can still be reached within O(n) iterations.

See the comments starting at "Major subtleties ahead":
http://hg.python.org/cpython/file/f8b40d33e45d/Objects/dictobject.c#l106