Speed up slot lookup for class creation

[pitrou]

BPO	32346
Nosy	@gvanrossum, @pitrou, @scoder, @methane, @serhiy-storchaka
PRs	bpo-32346: speed up slot lookup during class creation #4902
Files	benchgcclasses.py benchgcclasses2.py

^{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 2018-01-15.18:34:21.427>
created_at = <Date 2017-12-16.12:21:18.352>
labels = ['interpreter-core', '3.7', 'performance']
title = 'Speed up slot lookup for class creation'
updated_at = <Date 2018-01-15.18:34:21.426>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2018-01-15.18:34:21.426>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2018-01-15.18:34:21.427>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2017-12-16.12:21:18.352>
creator = 'pitrou'
dependencies = []
files = ['47378', '47379']
hgrepos = []
issue_num = 32346
keywords = ['patch']
message_count = 23.0
messages = ['308474', '308475', '308476', '308738', '308744', '308747', '308866', '308867', '309384', '309411', '309420', '309444', '309465', '309474', '309476', '309824', '309828', '309845', '309848', '309849', '309850', '309851', '309892']
nosy_count = 5.0
nosy_names = ['gvanrossum', 'pitrou', 'scoder', 'methane', 'serhiy.storchaka']
pr_nums = ['4902']
priority = 'low'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue32346'
versions = ['Python 3.7']

[pitrou]

As mentioned in https://mail.python.org/pipermail/python-dev/2017-December/151298.html, slot lookup can take 75 to 80% of the runtime when creating a new class. This was slightly improved in https://bugs.python.org/issue31336 but we're still doing one lookup per possible slot name *and* per class along the MRO.

I propose to speed up this step by caching the known descriptors for each class. This way, when instantiating a new class, you can simply iterate over the known descriptors of the MRO without wasting time on hundreds of dict lookups.

(and it is reasonably easy to find all slot descriptors in a dict: first select only __dunder__ names, then look them up in a dedicated mapping)

[pitrou]

I posted #4902 for this.

This approach has two drawbacks:

• uses an additional tp_ slot (and a corresponding TPFLAGS)
• adds a bit of code complexity (but quite localized)

[pitrou]

Some micro-benchmarks:

$ ./python -m timeit "class Test: pass"
- before: 8.84 usec per loop
- after: 7.03 usec per loop

$ ./python -m timeit "class Test(tuple): pass"
- before: 10.1 usec per loop
- after: 8.4 usec per loop

$ ./python -m timeit -s "from logging import Logger" "class Test(Logger): pass"
- before: 12 usec per loop
- after: 6.25 usec per loop

$ ./python -m timeit -s "from logging.handlers import DatagramHandler" "class Test(DatagramHandler): pass"
- before: 15 usec per loop
- after: 6.68 usec per loop

$ ./python -m timeit -s "from unittest.mock import MagicMock" "class Test(MagicMock): pass"
- before: 18.2 usec per loop
- after: 6.56 usec per loop

$ ./python -m timeit -s "from shelve import Shelf" "class Test(Shelf): pass"
- before: 28.6 usec per loop
- after: 18.4 usec per loop

[pitrou]

Updated benchmarks against git master (and using pyperf):

• before:

$ ./env-orig/bin/pyperf timeit -q "class Test: pass"
Mean +- std dev: 8.89 us +- 0.09 us
$ ./env-orig/bin/pyperf timeit -q -s "from logging import Logger" "class Test(Logger): pass"
Mean +- std dev: 12.0 us +- 0.2 us
$ ./env-orig/bin/pyperf timeit -q -s "from unittest.mock import MagicMock" "class Test(MagicMock): pass"
Mean +- std dev: 18.6 us +- 0.2 us

• after:

$ ./env/bin/pyperf timeit -q "class Test: pass"
Mean +- std dev: 6.90 us +- 0.11 us
$ ./env/bin/pyperf timeit -q -s "from logging import Logger" "class Test(Logger): pass"
Mean +- std dev: 5.86 us +- 0.08 us
$ ./env/bin/pyperf timeit -q -s "from unittest.mock import MagicMock" "class Test(MagicMock): pass"
Mean +- std dev: 6.13 us +- 0.08 us

[serhiy-storchaka]

Due to its complexity it will take a time to make a review of this patch.

[pitrou]

Yes... The patch itself is not very complex, but you have to dive into the intricacies of typeobject.c to understand it :-/

[methane]

New slot is really required?

My idea is:

• Copy slots from MRO
• Iterate namespace dict and override slots if dunder is defined

Is it impossible or harder than my thought?

[pitrou]

I don't really understand your proposal, so it's hard to answer :-) Perhaps you can try to implement it so that we can compare?

[serhiy-storchaka]

./python -m timeit -- "class A: pass"

• before: 6.63 usec per loop
• after: 5.41 usec per loop

./python -m timeit -s "class A: pass" -- "class B(A): pass"

• before: 7.04 usec per loop
• after: 4.91 usec per loop

./python -m timeit -s "class A: pass" -s "class B(A): pass" -- "class C(B): pass"

• before: 8.24 usec per loop
• after: 5.09 usec per loop

./python -m timeit -s "class A: pass" -s "class B(A): pass" -s "class C(B): pass" -- "class D(C): pass"

• before: 9.59 usec per loop
• after: 5.29 usec per loop

./python -m timeit -s "class A: pass" -s "class B(A): pass" -s "class C(B): pass" -s "class D(C): pass" -- "class E(D): pass"

• before: 10.9 usec per loop
• after: 5.45 usec per loop

[methane]

How about reusing tp_cache instead of adding new slot?

[pitrou]

What exactly is tp_cache? Apparently it was added by Guido in 687ae00 but never used (at least officially).

commit 687ae00
Author: Guido van Rossum <guido@python.org>
Date: Mon Oct 15 22:03:32 2001 +0000

Get rid of __defined__ and tp_defined -- there's no need to
distinguish __dict__ and __defined__ any more. In the C structure,
tp_cache takes its place -- but this hasn't been implemented yet.

[gvanrossum]

I don't recall what I meant to use tp_cache for, but everything I can find about it says it's unused, so let's kill it if we can. I guess the ABI requires that we keep the slot around until we find a new use for it?