gh-91603: Speed up `UnionType` instantiation by uriyyo · Pull Request #91865 · python/cpython

uriyyo · 2022-04-23T19:09:52Z

Summary

Remove types.UnionType.__args__ recreation (flatten_args and dedup_and_flatten_args ).
Use the fact that in the case when union with another types.UnionType that union has deduplicated normalized __args__.

As a result complexity from O((M+N)^2) was reduced to O(M*N), where M - length of left union args, N - length of right union args.

Benchmarks:

Benchmark	this	main
int \| float	67.5 ns	121 ns: 1.80x slower
int \| (list \| float)	153 ns	250 ns: 1.64x slower
(int \| float) \| list	142 ns	238 ns: 1.67x slower
(int \| float) \| (list \| set)	253 ns	411 ns: 1.63x slower
(float \| set) \| int \| int \| (float \| list)	450 ns	687 ns: 1.53x slower
float \| set \| int \| int \| float \| list	416 ns	750 ns: 1.80x slower
Geometric mean	(ref)	1.67x slower

For big unions:

Benchmark	this	main
bool \| int \| float \| complex \| str \| bytes \| bytearray \| list \| set \| frozenset \| dict \| range \| property \| classmethod \| staticmethod \| Exception	1.38 us	4.08 us: 2.96x slower

JelleZijlstra

Thanks, this overall makes sense to me, but I found a few style issues and one bigger problem.

Objects/unionobject.c

JelleZijlstra · 2022-04-25T13:35:15Z

Objects/unionobject.c

 {
    assert(PyTuple_CheckExact(args));

-    args = dedup_and_flatten_args(args);


We still need this logic for the callsite in union_getitem.

Consider this case:

>>> from typing import TypeVar >>> T = TypeVar("T") >>> (list[T] | list[int]) list[~T] | list[int] >>> (list[T] | list[int])[int] list[int]

If I'm reading your code correctly, it would no longer deduplicate the two members. It would be good to also add a test case based on this example.

We should probably put the deduping logic directly in union_getitem.

@JelleZijlstra Actually, we don't need it, as far as such case already handled by tests:

cpython/Lib/test/test_types.py

Line 823 in 1cd8c29

self.assertEqual((list[T] | list[S])[int, int], list[int])

That's because after parameter substitution new UnionType is recreated by reducing newargs using bitwise or operator:

cpython/Objects/unionobject.c

Lines 380 to 388 in 1cd8c29

res = PyTuple_GET_ITEM(newargs, 0);

Py_INCREF(res);

for (Py_ssize_t iarg = 1; iarg < nargs; iarg++) {

PyObject *arg = PyTuple_GET_ITEM(newargs, iarg);

Py_SETREF(res, PyNumber_Or(res, arg));

if (res == NULL) {

break;

}

}

Oh good catch! That seems a bit inefficient too, but we don't need to fix that in this PR; in any case it's probably a less performance-critical path.

Co-authored-by: Jelle Zijlstra <[email protected]>

serhiy-storchaka

Some nitpicks. Did not review the code deeply yet.

Objects/unionobject.c

bedevere-bot · 2022-04-26T08:30:47Z

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

Co-authored-by: Serhiy Storchaka <[email protected]>

Objects/unionobject.c

uriyyo · 2022-04-26T09:49:23Z

I have made the requested changes; please review again

bedevere-bot · 2022-04-26T09:49:26Z

Thanks for making the requested changes!

@JelleZijlstra, @serhiy-storchaka: please review the changes made to this pull request.

Fidget-Spinner

LGTM in general, I just have one question.

Objects/unionobject.c

serhiy-storchaka

Mostly LGTM, except _PyTuple_Resize and some formatting.

But the code can be much smaller. I have refactored it in #91955.

Objects/unionobject.c

…stance

serhiy-storchaka

LGTM.

Although I prefer #91955, which is simpler. 😉

uriyyo · 2022-04-28T11:04:10Z

Closed because #91955 merged

Speed up UnionType instantiation

1d5de83

bedevere-bot added the awaiting review label Apr 23, 2022

uriyyo added 2 commits April 23, 2022 22:48

Don't use list

ac2b3a0

Fix issue with uncopied data

b8f9eae

JelleZijlstra self-requested a review April 24, 2022 05:02

uriyyo added 4 commits April 24, 2022 09:54

Remove deduplication and flatting

d3dba88

Return assert

3ac3013

Minor fixes

7e87ef0

Fix issue

fde9507

Fidget-Spinner self-requested a review April 24, 2022 09:15

JelleZijlstra reviewed Apr 25, 2022

View reviewed changes

AlexWaygood added performance Performance or resource usage topic-typing labels Apr 25, 2022

uriyyo and others added 4 commits April 25, 2022 18:52

Update Objects/unionobject.c

bc348c9

Co-authored-by: Jelle Zijlstra <[email protected]>

Update Objects/unionobject.c

fbc7934

Co-authored-by: Jelle Zijlstra <[email protected]>

Update Objects/unionobject.c

4321116

Co-authored-by: Jelle Zijlstra <[email protected]>

Fix formatting

f1e06da

JelleZijlstra approved these changes Apr 25, 2022

View reviewed changes

bedevere-bot added awaiting merge and removed awaiting review labels Apr 25, 2022

serhiy-storchaka requested changes Apr 26, 2022

View reviewed changes

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

bedevere-bot added awaiting changes and removed awaiting merge labels Apr 26, 2022

uriyyo and others added 3 commits April 26, 2022 11:42

Update Objects/unionobject.c

70d9d30

Co-authored-by: Serhiy Storchaka <[email protected]>

Update Objects/unionobject.c

e928a6c

Co-authored-by: Serhiy Storchaka <[email protected]>

Update Objects/unionobject.c

8c3e307

Co-authored-by: Serhiy Storchaka <[email protected]>

serhiy-storchaka reviewed Apr 26, 2022

View reviewed changes

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

Fix formatting

97b2944

serhiy-storchaka reviewed Apr 26, 2022

View reviewed changes

Objects/unionobject.c Outdated Show resolved Hide resolved

Refactor merge functions

6b8e2e7

bedevere-bot added awaiting change review and removed awaiting changes labels Apr 26, 2022

bedevere-bot requested review from JelleZijlstra and serhiy-storchaka April 26, 2022 09:49

Fidget-Spinner reviewed Apr 26, 2022

View reviewed changes

Objects/unionobject.c Outdated Show resolved Hide resolved

Fidget-Spinner reviewed Apr 26, 2022

View reviewed changes

Objects/unionobject.c Show resolved Hide resolved

Objects/unionobject.c Show resolved Hide resolved

uriyyo requested a review from Fidget-Spinner April 26, 2022 11:05

serhiy-storchaka mentioned this pull request Apr 26, 2022

gh-91603: Speed up UnionType instantiation (alt) #91955

Merged

serhiy-storchaka reviewed Apr 26, 2022

View reviewed changes

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

Objects/unionobject.c Outdated Show resolved Hide resolved

uriyyo added 2 commits April 26, 2022 15:15

Fix formatting

eb784c4

Remove Py_DECREF after resize failed

c82eca6

uriyyo requested a review from serhiy-storchaka April 26, 2022 12:21

uriyyo added 2 commits April 26, 2022 15:38

Minor fixes

0cef035

Merge remote-tracking branch 'fork/main' into feature/faster-union-in…

c361b10

…stance

serhiy-storchaka reviewed Apr 26, 2022

View reviewed changes

serhiy-storchaka approved these changes Apr 26, 2022

View reviewed changes

bedevere-bot added awaiting merge and removed awaiting change review labels Apr 26, 2022

uriyyo closed this Apr 28, 2022

	res = PyTuple_GET_ITEM(newargs, 0);
	Py_INCREF(res);
	for (Py_ssize_t iarg = 1; iarg < nargs; iarg++) {
	PyObject *arg = PyTuple_GET_ITEM(newargs, iarg);
	Py_SETREF(res, PyNumber_Or(res, arg));
	if (res == NULL) {
	break;
	}
	}

Uh oh!

Comments

Conversation

uriyyo commented Apr 23, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Benchmarks:

Uh oh!

JelleZijlstra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

JelleZijlstra Apr 25, 2022

Choose a reason for hiding this comment

Uh oh!

uriyyo Apr 25, 2022

Choose a reason for hiding this comment

Uh oh!

JelleZijlstra Apr 25, 2022

Choose a reason for hiding this comment

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bedevere-bot commented Apr 26, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

uriyyo commented Apr 26, 2022

Uh oh!

bedevere-bot commented Apr 26, 2022

Uh oh!

Fidget-Spinner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

uriyyo commented Apr 28, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

uriyyo commented Apr 23, 2022 •

edited

Loading