Enum creation non-linear in the number of values

[olliemath]

BPO	45417
Nosy	@warsaw, @arigo, @cfbolz, @ethanfurman, @mattip, @olliemath
PRs	bpo-45417: fix quadratic behaviour when creating an enum #28907
Files	huge.py: A single very large enum quadratic-fix-2.diff

^{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/ethanfurman'
closed_at = None
created_at = <Date 2021-10-08.23:52:33.688>
labels = ['3.11', '3.10', 'performance']
title = 'Enum creation non-linear in the number of values'
updated_at = <Date 2021-10-15.16:07:46.518>
user = 'https://github.com/olliemath'

bugs.python.org fields:

activity = <Date 2021-10-15.16:07:46.518>
actor = 'ethan.furman'
assignee = 'ethan.furman'
closed = False
closed_date = None
closer = None
components = []
creation = <Date 2021-10-08.23:52:33.688>
creator = 'olliemath'
dependencies = []
files = ['50332', '50341']
hgrepos = []
issue_num = 45417
keywords = ['patch']
message_count = 5.0
messages = ['403512', '403585', '403592', '403751', '403947']
nosy_count = 7.0
nosy_names = ['barry', 'arigo', 'Carl.Friedrich.Bolz', 'eli.bendersky', 'ethan.furman', 'mattip', 'olliemath']
pr_nums = ['28907']
priority = 'normal'
resolution = None
stage = 'backport needed'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue45417'
versions = ['Python 3.10', 'Python 3.11']

[olliemath]

Creating large enums takes a significant amount of time. Moreover this appears to be nonlinear in the number of entries in the enum. Locally, importing a single python file and taking this to the extreme:

1000 entries - 0.058s
10000 entries - 4.327s

This is partially addressed by https://bugs.python.org/issue38659 and I can confirm that using @_simple_enum does not have this problem. But it seems like that API is only intended for internal use and the 'happy path' for user-defined enums is still not good.

Note that it is not simply parsing the file / creating the instances, it is to do with the cardinality. Creating 100 enums with 100 entries each is far faster than a single 10000 entry enum.

[arigo]

The timing is clearly quadratic:

number of attributes time
1500 0.24s
3000 0.94s
6000 3.74s
12000 15.57s

Pressing Ctrl-C in the middle of the execution of the largest examples points directly to the cause: when we consider the next attribute, we loop over all previous ones at enum.py:238.

[mattip]

Over at PyPy arigo authored and we applied this fix to the as-yet unreleased pypy3.8. Note that it cannot be applied directly to CPython as sets are not ordered. Does the fix break anything? Tests in Lib/test/test_enum.py passed after applying it.

[cfbolz]

I fixed the reliance of set being insertion ordered in pypy and opened a pull request.

[ethanfurman]

New changeset b2af211 by Carl Friedrich Bolz-Tereick in branch 'main':
bpo-45417: [Enum] fix quadratic behavior during creation (GH-28907)
b2af211