classification
Title: Remove dummy reuse optimization from sets
Type: performance Stage: patch review
Components: Interpreter Core Versions: Python 3.5
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: pitrou, rhettinger, serhiy.storchaka, tim.peters
Priority: low Keywords: patch

Created on 2015-01-17 20:46 by rhettinger, last changed 2015-01-18 20:58 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
late8.diff rhettinger, 2015-01-17 20:46 Remove freeslot tracking review
Messages (8)
msg234198 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-17 20:46
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.
msg234200 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-17 21:44
This can be a common case in following algorithm (mesh optimization):

while elems:
    elem = elems.pop()
    changed = optimize(elem)
    if changed:
        elems.update(neighbors(elem))
msg234205 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-17 23:52
Even in the mesh algorithm, we let resizing periodically clean-up the dummies.   The idea is to not pay the freeslot tracking cost on every lookup and instead only clean-up periodically (which would likely give better performance for the mesh algorithm as well, since making a single pass clean-up during resizing is cheaper than doing multi-step tracking for every insertion).  The slots do get reused, just not immediately.

Also, the idea is to not let the possibility of pop-change-update algorithms create a cost for the more common uses of sets (uniquification, fast membership testing, and set-to-set operations such as union, intersection, and difference).
msg234207 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2015-01-18 00:31
> 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.

Do you have a benchmark showing the slowing down?
msg234211 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2015-01-18 01:26
Fewer instructions doesn't necessarily translate into better performance. The bottleneck in superscalar, pipelined processors is often the data dependency path between instructions. Adding instructions may as well not slow anything down, if those instructions don't lengthen the dependency path.

It would be interesting to know what the impact of the patch is on the workloads that were supposed to be helped by the removed logic.
msg234226 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-18 08:21
In some cases the slowdown is over 100x.

$ ./python -m timeit -s "s = set(range(10**4))" -- "s.discard(0); s.add(0)"

Unpatched: 1000000 loops, best of 3: 1.68 usec per loop
Patched: 10000 loops, best of 3: 183 usec per loop
msg234227 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-01-18 08:32
If you want to decrease the number of executed instructions, I suggest to duplicate lookup functions (actually add boolean flag and switch one of two branches). On read lookup function should ignore dummy entries, on modification it should behave as now.
msg234278 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-01-18 20:58
I'll just close this one.  There seems to be little interest in it.

Originally, I characterized freeslot tracking as an optimization that mildly benefited an uncommon case (adds/deletes/moreadds) at the expense of the common cases (uniquification, membership testing, and set-to-set operations).

As Antoine pointed-out, on some systems the cost of a predictable branch routinely not take can be almost zero.  There was still benefit in code simplification, reducing the size of the stack frame, freeing a register that needed to saved and restored when called PyRich_CompareBool(), etc. But no one seems to care about those.

As Serhiy found, there is one case where the freeslot tracking benefit wasn't "mild".  In the unusual but possible case of deleting and reinserting the exact same value in a large set, dummy reuse prevents a catastrophic linear pile-up.

And so it goes.   Free slot tracking lives.
History
Date User Action Args
2015-01-18 20:58:59rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg234278
2015-01-18 20:41:47rhettingersetmessages: - msg234210
2015-01-18 08:32:46serhiy.storchakasetmessages: + msg234227
2015-01-18 08:21:00serhiy.storchakasetmessages: + msg234226
2015-01-18 01:26:40pitrousetmessages: + msg234211
2015-01-18 01:20:01rhettingersetnosy: + tim.peters
messages: + msg234210
2015-01-18 00:31:23pitrousetnosy: + pitrou
messages: + msg234207
2015-01-17 23:52:25rhettingersetmessages: + msg234205
2015-01-17 21:44:01serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg234200
2015-01-17 20:46:06rhettingercreate