Generator finalization is slower in 3.11 vs 3.10

[Onlooker2186]

I found that the Python 3.11.1 implementation of all() is 30% slower compared to Python 3.10.9.

any() also seems to be around 4% slower on my device

Environment

• CPython versions tested on: Python 3.10.9 and Python 3.11.1
• Operating system and architecture: Windows 10 22H2 (Build 19045) 64 bit

Code to test all():

import timeit
from functools import partial
import platform


def find_by_keys(
 keys: list[str],
 table: list[dict[str, str | int]],
 match_data: dict[str, str | int],
) -> dict[str, str | int] | None:
 for item in table:
 if all(item[k] == match_data[k] for k in keys):
 return item
 return None


def main():
 keys: list[str] = ["id", "key_1", "key_2"]
 table: list[dict[str, str | int]] = [
 {
 "id": i,
 "key_1": "val_1",
 "key_2": "val_2",
 }
 for i in range(1, 5001)
 ]
 match_data: dict[str, str | int] = {
 "id": 3000,
 "key_1": "val_1",
 "key_2": "val_2",
 }

 timeit_output = timeit.repeat(
 partial(find_by_keys, keys, table, match_data), repeat=10000, number=1
 )

 average_time = sum(timeit_output) / len(timeit_output)
 best_time = min(timeit_output)
 tps_output = 1 / average_time

 print(f"Python version = {platform.python_version()}")
 print(f"Average time = {average_time}")
 print(f"Best time = {best_time}")
 print(f"Average transactions per second = {tps_output}")


if __name__ == "__main__":
 main()

Results for all()

Console output using Python 3.10.9:

Python version = 3.10.9
Average time = 0.0008256170657486655
Best time = 0.0007106999401003122
Average transactions per second = 1211.2152733824669

Console output using Python 3.11.1:

Python version = 3.11.1
Average time = 0.0011819988898839802
Best time = 0.001033599954098463
Average transactions per second = 846.0244832363215

Code to test any():

import timeit
from functools import partial
import platform


def find_by_keys(
 keys: list[str],
 table: list[dict[str, str | int]],
 match_data: dict[str, str | int],
) -> dict[str, str | int] | None:
 for item in table:
 if any(item[k] == match_data[k] for k in keys):
 return item
 return None


def main():
 keys: list[str] = ["id", "key_1", "key_2"]
 table: list[dict[str, str | int]] = [
 {
 "id": i,
 "key_1": "foo_1",
 "key_2": "foo_2",
 }
 for i in range(1, 5001)
 ]
 match_data: dict[str, str | int] = {
 "id": 3000,
 "key_1": "val_1",
 "key_2": "val_2",
 }

 timeit_output = timeit.repeat(
 partial(find_by_keys, keys, table, match_data), repeat=10000, number=1
 )

 average_time = sum(timeit_output) / len(timeit_output)
 best_time = min(timeit_output)
 tps_output = 1 / average_time

 print(f"Python version = {platform.python_version()}")
 print(f"Average time = {average_time}")
 print(f"Best time = {best_time}")
 print(f"Average transactions per second = {tps_output}")


if __name__ == "__main__":
 main()

Results for any()

Console output using Python 3.10.9:

Python version = 3.10.9
Average time = 0.0009300541202770546
Best time = 0.00090230000205338
Average transactions per second = 1075.206246817238

Console output using Python 3.11.1:

Python version = 3.11.1
Average time = 0.0009645268900785595
Best time = 0.000930099980905652
Average transactions per second = 1036.7777303943815

Linked PRs

• gh-100762: Switch order of exception match in gen_close #101011
• GH-100762: Don't call gen.throw() in gen.close(), unless necessary. #101013
• [3.11] GH-100762: Don't call gen.throw() in gen.close(), unless necessary #101316
• gh-100762: Fix optimization in gen_close  #111069
• [3.12] gh-100762: Fix optimization in gen_close (GH-111069) #115818

[eendebakpt]

I can confirm this issue (comparing 3.10.8 to 3.12.0a3+). A shorter minimal example is:

import timeit
import platform

setup="""
def go( ) :
 item=[1,2,3]
 for ii in range(3000):
 all(item[k] == 2 for k in range(3))
""" 

cmd='go()'
timeit_output = timeit.repeat(
 cmd, setup=setup , repeat=500, number=10,
)

average_time = sum(timeit_output) / len(timeit_output)
best_time = min(timeit_output)
tps_output = 1 / average_time

print(f"Python version = {platform.python_version()}")
print(f"Average time = {average_time}")
print(f"Best time = {best_time}")
print(f"Average transactions per second = {tps_output}")

The expression inside the all(...) evaluates to a generator. Replacing this with all( [item[k] == 2 for k in range(3)] ) also shows a performance regression, but it is much smaller.
Some more tests show:

 all(k for k in item) # has no regression
 all(k == 2 for k in item) # has a regression

With git bisect I tried to identify the commit where the regression is introduced, but I could not pinpoint it (there seem to be multiple regressions, and not all commits build on my system)

[pochmann]

What makes you blame all() instead of the generator and all it involves?

Do you see a difference with all((False,))? That's an iterable likewise starting with False that eliminates almost everything else.

@eendebakpt What times did you get?

[eendebakpt]

@pochmann I executed the the following code:

import pyperf
runner = pyperf.Runner()

for stmt in ['g=(k == 2 for k in item)','g=all(k for k in item)', 'g=all(k == 2 for k in item)' ]:
 time = runner.timeit(name=stmt, stmt=stmt, setup="item=[1,2,3]")

Results 3.10.9:

.....................
g=(k == 2 for k in item): Mean +- std dev: 321 ns +- 10 ns
.....................
g=(k == 2 for k in item); h=list(g): Mean +- std dev: 504 ns +- 7 ns
.....................
g=all(k for k in item): Mean +- std dev: 388 ns +- 9 ns
.....................
all((False,)): Mean +- std dev: 74.1 ns +- 2.3 ns
.....................
g=all(k == 2 for k in item): Mean +- std dev: 434 ns +- 8 ns

Results 3.12.0a3+:

.....................
g=(k == 2 for k in item): Mean +- std dev: 351 ns +- 20 ns
.....................
g=(k == 2 for k in item); h=list(g): Mean +- std dev: 442 ns +- 5 ns
.....................
g=all(k for k in item): Mean +- std dev: 325 ns +- 3 ns
.....................
all((False,)): Mean +- std dev: 45.5 ns +- 1.5 ns
.....................
g=all(k == 2 for k in item): Mean +- std dev: 567 ns +- 7 ns

I am not sure what to conclude from the numbers, but the last statement tested g=all(k == 2 for k in item) is the regression reported in this issue.

[thatbirdguythatuknownot]

There doesn't seem to be any difference in the implementation code of all() and any() between 3.10 and main. Maybe the generators are the issue?

[mdboom]

Yes, indeed signs point to generators (or maybe generator expressions specifically) more than all or any.

[mdboom]

EDIT: I wasn't measuring what I thought I was here. See below for corrected results.

I tried to see if the new overhead is in the setup/starting of the generator or the actual iteration (is the overhead constant per generator used, or scales with the number of items iterated over) and it seems it's maybe both...?

I modified this script so that the number of keys in the dictionary is configurable (using only 3 here seems like a hard case if the regression is in generator creation), and then ran it for powers of 2 from 2 to 2048. It definitely gets better as the number of keys goes up, but it never gets on par with 3.10.

Not sure what any of this means, but maybe some other faster CPython folks may have insight.

Code example with a variable number of keys

``` import timeit from functools import partial import sys

def find_by_keys(
keys: list[str],
table: list[dict[str, str | int]],
match_data: dict[str, str | int],
) -> dict[str, str | int] | None:

for item in table:
 if all(item[k] == match_data[k] for k in keys):
 return item
return None

def main():
nkeys = int(sys.argv[-1])
keys: list[str] = ["id"] + [f"key_{i}" for i in range(nkeys)]
table: list[dict[str, str | int]] = []
for i in range(1, 5001):
d = {
f"key_{j}": f"val_{j}" for j in range(nkeys)
}
d["id"] = i
table.append(d)
match_data = table[2999].copy()

timeit_output = timeit.repeat(
 partial(find_by_keys, keys, table, match_data), repeat=10000, number=1
)

average_time = sum(timeit_output) / len(timeit_output)
print(average_time)

if name == "main":
main()

</details>

[mdboom]

Some additional information -- here's the differences in the bytecode.

3.10 bytecode

Disassembly of <code object <genexpr> at 0x7f019adad630, file "/home/mdboom/Work/builds/tmp-generator-regression/test.py", line 13>:
 0 GEN_START 0

 13 2 LOAD_FAST 0 (.0)
 >> 4 FOR_ITER 11 (to 28)

 14 6 STORE_FAST 1 (k)
 8 LOAD_DEREF 0 (item)
 10 LOAD_FAST 1 (k)
 12 BINARY_SUBSCR
 14 LOAD_DEREF 1 (match_data)
 16 LOAD_FAST 1 (k)
 18 BINARY_SUBSCR
 20 COMPARE_OP 2 (==)

 13 22 YIELD_VALUE
 24 POP_TOP
 26 JUMP_ABSOLUTE 2 (to 4)
 >> 28 LOAD_CONST 0 (None)
 30 RETURN_VALUE

3.11 bytecode

Disassembly of <code object <genexpr> at 0x7fc1302f9530, file "/home/mdboom/Work/builds/tmp-generator-regression/test.py", line 19>:
 0 COPY_FREE_VARS 2

 19 2 RETURN_GENERATOR
 4 POP_TOP
 6 RESUME_QUICK 0
 8 LOAD_FAST 0 (.0)
 10 FOR_ITER 22 (to 56)
 12 STORE_FAST 1 (k)
 14 LOAD_DEREF 2 (item)
 16 LOAD_FAST 1 (k)
 18 BINARY_SUBSCR_DICT
 28 LOAD_DEREF 3 (match_data)
 30 LOAD_FAST 1 (k)
 32 BINARY_SUBSCR_DICT
 42 COMPARE_OP 2 (==)
 48 YIELD_VALUE
 50 RESUME_QUICK 1
 52 POP_TOP
 54 JUMP_BACKWARD_QUICK 23 (to 10)
 >> 56 LOAD_CONST 0 (None)
 58 RETURN_VALUE

[brandtbucher]

I think @mdboom's example is still dominated by generator creation, since the first 2999 loops will only advance the generator once, and the 3000th will advance it n times, then return.

Perhaps put "id" last in the list of keys, so that all will walk the full list of keys every time?

[mdboom]

Thanks, @brandtbucher. Indeed I was not measuring what I thought I was measuring. By putting id at the end and getting more iterations, I get a graph that makes a lot more sense.

As the number of iterations in the generator goes up, it trends toward "at par" between 3.10 and 3.11. So I think it's fair to say that whatever regression exists is due to generator startup, not the time spent iterating over it.

From the bytecode, it definitely is doing "more work" to start the generator, but I don't know if I could say what room there is for improvement.

Code to test with variable number of keys

import timeit
from functools import partial
import sys


def find_by_keys(
 keys: list[str],
 table: list[dict[str, str | int]],
 match_data: dict[str, str | int],
) -> dict[str, str | int] | None:

 for item in table:
 if all(item[k] == match_data[k] for k in keys):
 break
 return None


def main():
 nkeys = int(sys.argv[-1])
 keys: list[str] = [f"key_{i}" for i in range(nkeys)] + ["id"]
 table: list[dict[str, str | int]] = []
 for i in range(1, 5001):
 d = {
 f"key_{j}": f"val_{j}" for j in range(nkeys)
 }
 d["id"] = str(i)
 table.append(d)
 match_data = table[2999].copy()

 timeit_output = timeit.repeat(
 partial(find_by_keys, keys, table, match_data), repeat=10000, number=1
 )

 average_time = sum(timeit_output) / len(timeit_output)
 print(average_time)


if __name__ == "__main__":
 main()