MRO computation could be faster

[pitrou]

BPO	32379
Nosy	@pitrou, @vstinner, @methane, @serhiy-storchaka
PRs	bpo-32379: Faster MRO computation for single inheritance #4932

^{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 = None
closed_at = <Date 2017-12-20.14:58:51.444>
created_at = <Date 2017-12-19.19:54:59.746>
labels = ['interpreter-core', '3.7', 'performance']
title = 'MRO computation could be faster'
updated_at = <Date 2017-12-20.14:58:51.443>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2017-12-20.14:58:51.443>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2017-12-20.14:58:51.444>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2017-12-19.19:54:59.746>
creator = 'pitrou'
dependencies = []
files = []
hgrepos = []
issue_num = 32379
keywords = ['patch']
message_count = 5.0
messages = ['308674', '308675', '308733', '308734', '308737']
nosy_count = 4.0
nosy_names = ['pitrou', 'vstinner', 'methane', 'serhiy.storchaka']
pr_nums = ['4932']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue32379'
versions = ['Python 3.7']

[pitrou]

MRO computation involves a complicated merge calculation over several lists. But, for the simple (common) case where a class has a single base, the computation could be much simpler: take the base's MRO and prepend the derived class.

[pitrou]

Benchmarks:

• before:

$ ./env-orig/bin/pyperf timeit "class Test: pass"
.....................
Mean +- std dev: 9.51 us +- 0.17 us

• after:

$ ./env/bin/pyperf timeit "class Test: pass"
.....................
Mean +- std dev: 8.89 us +- 0.09 us

[serhiy-storchaka]

LGTM in general. But mro() returns a list.

"class Test: pass" is a trivial case. What are results if the class has a parent?

[pitrou]

Benchmarks with a parent:

• Before:

$ ./env-orig/bin/pyperf timeit -s "from unittest import TestCase" "class Test(TestCase): pass"
.....................
Mean +- std dev: 10.4 us +- 0.1 us

• After:

$ ./env/bin/pyperf timeit -s "from unittest import TestCase" "class Test(TestCase): pass"
.....................
Mean +- std dev: 9.89 us +- 0.12 us

[pitrou]

New changeset 1f1a34c by Antoine Pitrou in branch 'master':
bpo-32379: Faster MRO computation for single inheritance (bpo-4932)
1f1a34c