One operation on sets < 1/100th as efficient in 3.9 than before

[eamartin]

BPO	43198
Nosy	@tim-one, @rhettinger, @zware, @sweeneyde
PRs	bpo-43198: Revert 3dd2157 that removed freeslot tracking. #25010

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2021-03-24.22:33:57.764>
created_at = <Date 2021-02-11.00:15:07.462>
labels = ['interpreter-core', '3.10', 'performance']
title = 'One operation on sets < 1/100th as efficient in 3.9 than before'
updated_at = <Date 2021-03-24.22:33:57.763>
user = 'https://bugs.python.org/eamartin'

bugs.python.org fields:

activity = <Date 2021-03-24.22:33:57.763>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2021-03-24.22:33:57.764>
closer = 'rhettinger'
components = ['Interpreter Core']
creation = <Date 2021-02-11.00:15:07.462>
creator = 'eamartin'
dependencies = []
files = []
hgrepos = []
issue_num = 43198
keywords = ['patch']
message_count = 9.0
messages = ['386815', '386816', '386817', '386819', '386848', '386849', '388326', '388349', '389491']
nosy_count = 5.0
nosy_names = ['tim.peters', 'rhettinger', 'zach.ware', 'eamartin', 'Dennis Sweeney']
pr_nums = ['25010']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue43198'
versions = ['Python 3.10']

[eamartin]

Run on a MacBook Pro (15-inch, 2019)
2.3 GHz 8-Core Intel Core i9
16 GB 2400 MHz DDR4

Python 3.8.7 (default, Dec 24 2020, 19:07:18) 
[Clang 12.0.0 (clang-1200.0.32.27)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> S = set(range(10_000))
>>> timeit('S.remove(5000); S.add(5000)', globals=globals(), number=100_000)
0.01933291699999984

$ python3.9
Python 3.9.1 (default, Dec  8 2020, 13:10:53) 
[Clang 12.0.0 (clang-1200.0.32.27)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from timeit import timeit
>>> S = set(range(10_000))
>>> timeit('S.remove(5000); S.add(5000)', globals=globals(), number=100_000)
3.8517225489999998

[zware]

Can reproduce on Linux:

$ for python in /usr/bin/python3.? /usr/local/bin/python3.?
do 
    $python -VV
    $python -m timeit -r 10 -n 100_000 -u usec -s 'S = set(range(10_000))' 'S.remove(5000);S.add(5000)'
done
Python 3.8.5 (default, Jul 28 2020, 12:59:40) 
[GCC 9.3.0]
100000 loops, best of 10: 0.0831 usec per loop
Python 3.6.11 (tags/v3.6.11:d56cd4006a, Jul  1 2020, 10:47:06) 
[GCC 9.3.0]
100000 loops, best of 10: 0.0968 usec per loop
Python 3.7.9 (tags/v3.7.9:13c94747c7, Oct 19 2020, 23:50:03) 
[GCC 9.3.0]
100000 loops, best of 10: 0.0935 usec per loop
Python 3.9.0 (tags/v3.9.0:9cf6752276, Nov 14 2020, 15:41:20) 
[GCC 9.3.0]
100000 loops, best of 10: 50.2 usec per loop

[sweeneyde]

I bisected the change to here:

#19881
commit 3dd2157
Author: Raymond Hettinger <rhettinger@users.noreply.github.com>
Date: Sun May 3 04:51:05 2020 -0700

Simplify set entry insertion logic. (GH-19881)

"""Dictionaries no longer reuse dummy entries. Instead, dummies accumulate until cleared by resizes. That is a good strategy because it tightens the inner search loop and it makes the code cleaner. Here, we do the same thing for sets"""

It looks like this was a deliberate change to speed up lookups, but it also looks like it adversely affected this case. With dictionaries, mutation typically occurs as setting a different value for the same key---no dummy entries get created, so dummy entries are less common. But with sets, mutation can only come from adding/discarding, so maybe this optimization is less worthwhile for sets.

[rhettinger]

This only affects the contrived case of adding and removing exactly the same element in a tight loop, when the set is large. Optimizing that one corner case came at the expense of all other cases. The code is now simpler and slightly faster than before. This is also what we do for dictionaries.

$ python3.8 -m timeit -r 11 -s 's=set(range(10_000))' 'for i in range(10_000): (s.discard(i), s.add(10_000 - i))'
200 loops, best of 11: 1.72 msec per loop

$ python3.9 -m timeit -r 11 -s 's=set(range(10_000))' 'for i in range(10_000): (s.discard(i), s.add(10_000 - i))'
200 loops, best of 11: 1.09 msec per loop

Thank you for the report, but this was an intended change.

[rhettinger]

Addenda [reposted to fix a premature submission].

Top use cases for sets (roughly in order of commonality):

1. Eliminate duplicates from an iterable input and loop over the result.
2. Store elements in a set just once but do many membership tests.
3. Perform data analysis on multiple sets using union, intersection, difference, and isdisjoint.
4. Remove elements from a set, one at a time, until it is empty.
5. Algorithms and that alternately add and remove different elements over time (toposort, NFA, DFA, etc).

The first three are all penalized by an extra inner loop test and the loss of the register to track the freeslot. Those use cases get no offsetting benefit.

Case 4 doesn't exercise the dummy reuse at all. So, it is unaffected.

The last is approximately a net wash. It pays the inner loop price, suffers the loss of a register, and incurs an extra test outside the loop, but it occasionally gets lucky and reuses a freeslot. The benefit for reuse is that it is delays the inevitable resize which would have reclaimed the dummy entries earlier. (The comparable use case for dicts is LRU/LFU caches where new entries are added at the same rate as old entries are removed. That use case also showed a net wash when freeslot tracking was removed from dicts).

Not on the list at all is the case of a large set, where exactly the same element is added and removed in a tight loop. The payoff for this case is that the O(n) resize step never occurs; however, this case is so rare that there is no reason to preference it over the common cases.

If the addition and removal of the same element happens only a few times, with no other set updates, the performance is about the same as case 5.

However, if there are many such updates and the set is large (as in the OP's code sample), the add() operation becomes quadratic because the chain of dummy or used entries grows larger and larger with each reinsertion. (FWIW, dicts also face the same issue and some additional ones related to maintaining insertion order). The question is whether this unhappy case is worth burdening all of the normal use cases. If this turns out to be a real issue in practice, we can reopen this; otherwise, let's stick with what we have.

[eamartin]

Many thanks Raymond for these insights and thorough explanations, I appreciate it very much. Your conclusions are of course most reasonable. For me, I cannot say that it is a real issue in practice. I have teaching notes in which I illustrate with plots the differences in complexity when working with sets versus lists. One such plot showed that the cost of removing an element from a set does not depend on what the element is (which is why I reused the same element again and again) and is orders of magnitude less than for removing an element from the middle of a list. I just found out that something had changed with Python3.9 when I last run the cell of the jupyter notebook in which that plot was produced...

[rhettinger]

I've had misgivings about this and will revert the change for Python 3.10.

Usually, it is safe for sets to implement whatever has been battle-tested with dicts, but sets should aspire to do better for alternating deletions and re-additions of the same element, even if that isn't a common case.