[New-bugs-announce] [issue23259] Remove dummy reuse optimization from sets

[Raymond Hettinger]

New submission from Raymond Hettinger:

The lookkey routines in Object/setobject.c have logic to track the first open "freeslot" in a search.  

The benefit is that new keys can reuse previously deleted slots.  The benefit only occurs in cases where keys are added, then some removed, and then more added with no intervening resizes (which clear all dummy entries) and only when the newly added keys happen to land on previously deleted entries.

The cost of the optimization is the extra logic in the inner search loop, an extra freeslot stackframe field that needs to be saved and restored, and extra logic on the loop exit.  It also causes dummies to "leak" out of the lookkey routines so that the code in contains(), discard(), and insert() all have to check for the dummy case.

This patch removes the freeslot tracking.  It saves one field on the stackframe, simplifies the lookkey inner-loop logic, simplifies the lookkey "found_null" logic, it confines knowledge of dummies to just the lookkey functions, and it simplifies the code in the insert(), contains(), and discard() functions.

In short, it looks like the freeslot idea was a net negative -- it optimized an uncommon case at the cost of slowing and complicating the common cases.

----------
assignee: rhettinger
components: Interpreter Core
files: late8.diff
keywords: patch
messages: 234198
nosy: rhettinger
priority: low
severity: normal
stage: patch review
status: open
title: Remove dummy reuse optimization from sets
type: performance
versions: Python 3.5
Added file: http://bugs.python.org/file37750/late8.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue23259>
_______________________________________