Enum creation is quadratic in the number of members (`_hashable_values_` list scan)

[jonbaldie]

Bug report

Bug description:

Creating an Enum is quadratic in the number of members again. When each member is added, _proto_member.__set_name__ runs value not in enum_class._hashable_values_, and _hashable_values_ is a list, so every new member scans all the ones before it.

import time
from enum import Enum

for n in (1000, 4000, 8000, 16000):
    members = {f'M{i:08x}': i for i in range(n)}
    t = time.perf_counter()
    Enum('Generated', members)
    print(n, f'{(time.perf_counter() - t) * 1e3:.0f} ms')

On main (3.16 dev, macOS arm64): 5.8 / 54 / 187 / 713 ms. Each doubling of n costs about 4x.

This is the same symptom as gh-89580, which was fixed. The _hashable_values_ scan came in later.

The scan is only needed when the value was already in _value2member_map_ before this member was added, for example an alias or a Flag pseudo-member that the class cached earlier. If setdefault just added the key, the value can't be in the list yet.

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-158856: Avoid a linear scan per member when creating an Enum #158857