Fixing Copy on Writes from reference counting and immortal objects

[eduardo-elizondo]

BPO	40255
Nosy	@tim-one, @nascheme, @gpshead, @pitrou, @vstinner, @carljm, @DinoV, @methane, @markshannon, @ericsnowcurrently, @zooba, @corona10, @pablogsal, @eduardo-elizondo, @remilapeyre, @shihai1991
PRs	gh-84436: Implement Immortal Objects #19474 bpo-43503: Make limited API objects effectively immutable. #24828 bpo-40255: Implement Immortal Instances - Optimization 1 #31488 bpo-40255: Implement Immortal Instances - Optimization 2 #31489 bpo-40255: Implement Immortal Instances - Optimization 3 #31490 bpo-40255: Implement Immortal Instances - Optimizations Combined #31491

^{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 = None
created_at = <Date 2020-04-11.15:40:21.809>
labels = ['interpreter-core', 'type-feature', '3.10']
title = 'Fixing Copy on Writes from reference counting and immortal objects'
updated_at = <Date 2022-02-22.16:42:58.428>
user = 'https://github.com/eduardo-elizondo'

bugs.python.org fields:

activity = <Date 2022-02-22.16:42:58.428>
actor = 'eric.snow'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2020-04-11.15:40:21.809>
creator = 'eelizondo'
dependencies = []
files = []
hgrepos = []
issue_num = 40255
keywords = ['patch']
message_count = 69.0
messages = ['366216', '366221', '366224', '366325', '366326', '366328', '366329', '366330', '366331', '366341', '366344', '366345', '366387', '366388', '366390', '366402', '366403', '366404', '366406', '366407', '366408', '366412', '366413', '366416', '366422', '366423', '366428', '366456', '366518', '366519', '366520', '366536', '366561', '366565', '366566', '366573', '366577', '366578', '366579', '366593', '366605', '366623', '366624', '366625', '366628', '366629', '366744', '366818', '366825', '366826', '366828', '366834', '366835', '366837', '366852', '379644', '379871', '379917', '388525', '388526', '388760', '410592', '410613', '412956', '413080', '413116', '413693', '413694', '413717']
nosy_count = 16.0
nosy_names = ['tim.peters', 'nascheme', 'gregory.p.smith', 'pitrou', 'vstinner', 'carljm', 'dino.viehland', 'methane', 'Mark.Shannon', 'eric.snow', 'steve.dower', 'corona10', 'pablogsal', 'eelizondo', 'remi.lapeyre', 'shihai1991']
pr_nums = ['19474', '24828', '31488', '31489', '31490', '31491']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue40255'
versions = ['Python 3.10']

Linked PRs

• gh-84436: Make Interned Strings Immortal #102887
• gh-84436: Add codemod for _PyVarObject_HEAD_IMMORTAL_INIT #103308
• gh-84436: Add static flag in PyLongObject's lv_tag #103403
• gh-84436: Immortalize in _PyStructSequence_InitBuiltinWithFlags() #103817
• gh-84436: Improve Immortalization for Builtin Types #103823
• gh-84436 Add integration C API tests for immortal objects #103962
• gh-84436: Immortalize in _PyStructSequence_InitBuiltinWithFlags() #104054
• gh-84436: update docs on Py_None/Py_True/Py_False/Py_Ellipsis becoming immortal #105195
• [3.12] gh-84436: update docs on Py_None/Py_True/Py_False/Py_Ellipsis becoming immortal (GH-105195) #105977
• GH-84436: Skip refcounting for known immortals #107605

[eduardo-elizondo]

Copy on writes are a big problem in large Python application that rely on multiple processes sharing the same memory.

With the implementation of gc.freeze, we've attenuated the problem by removing the CoW coming from the GC Head. However, reference counting still causes CoW.

This introduces Immortal Instances which allows the user to bypass reference counting on specific objects and avoid CoW on forked processes.

Immortal Instances are specially useful for applications that cache heap objects in shared memory which live throughout the entire execution (i.e modules, code, bytecode, etc.)

[gpshead]

Thanks for sharing! It's good to have a patch implementing for others who might need it to try out.

We experimented with an implementation of this on CPython 2.7 that we called Eternal Refcounts for YouTube many years ago. For the same reason (saving memory in forked workers by not dirtying pages of known needed objects via refcount changes).

I don't have that old patch handy right now, but looking at yours it was the same concept: A magic refcount value to branch based on.

We wound up not deploying it or pushing for it in CPython because the CPU performance implications of adding a branch instruction to Py_INCREC and Py_DECREF were, unsurprisingly, quite high. I'd have to go digging to find numbers but it _believe_ it was on the order of a 10% slowdown on real world application code. (microbenchmarks don't tell a good story, the python performance test suite should)

Given that most people's applications don't fork workers, I do not expect to see such an implementation ever become the default. It is a very appropriate hack, but the use case is limited to applications that don't use threads, are on POSIX, and always fork() many workers.

Also note that this is an ABI change as those INCREF and DECREF definitions are intentionally public .h file macros or inlines and thus included within any compiledcode rather than being an expensive function call elsewhere (vstinner's new alternate higher level API proposal presumably changes this). If an interpreter with this loaded a binary using the CPython API built against headers without it, your refcounts could get messed up.

[eduardo-elizondo]

the CPU performance implications of adding a branch instruction to Py_INCREC and Py_DECREF were, unsurprisingly, quite high.

Yeah, makes sense. I guess it really depends on the specific profile of your application.

For Instagram this was an overall net positive change and we still have it in prod. The amount of page faults from Copy on Writes was so large that reducing it resulted in a net CPU win (even with the added branching). And of course, a huge reduction in memory usage.

Microbenchmarks don't tell a good story, the python performance test suite should

Agreed. I only added the Richards benchmark as a reference. I'm hoping someone can pick it up and have more concrete numbers on an average Python workload.

Given that most people's applications don't fork workers, I do not expect to see such an implementation ever become the default.

In any case, I gated this change with ifdefs. In case we don't have it by default, we can always can easily enable it with a simple -DPy_IMMORTAL_INSTANCES flag to the compiler.

Also note that this is an ABI change as those INCREF and DECREF definitions are intentionally public .h file

This has indeed been a bit of a pain for us as well. Due to how our tooling is set-up, there's a small number of third party libraries that are still causing Copy on Writes. Fortunately, that's the only drawback. Even if your immortalized object goes through an extension that has a different Py_{DECREF,INCREF} implementation, the reference count will still be so large that it will never be deallocated.

[pablogsal]

I run the pyperformance test suite with PGO + LTO + full cpu isolation in the speed.python.org machine and these were the results:

+-------------------------+--------------------------------------+---------------------------------------+
| Benchmark | master | immortal_refs_patch |
+=========================+======================================+=======================================+
| pidigits | 289 ms | 290 ms: 1.01x slower (+1%) |
+-------------------------+--------------------------------------+---------------------------------------+
| pickle | 20.2 us | 20.3 us: 1.01x slower (+1%) |
+-------------------------+--------------------------------------+---------------------------------------+
| xml_etree_parse | 253 ms | 258 ms: 1.02x slower (+2%) |
+-------------------------+--------------------------------------+---------------------------------------+
| json_loads | 52.0 us | 53.1 us: 1.02x slower (+2%) |
+-------------------------+--------------------------------------+---------------------------------------+
| scimark_fft | 708 ms | 723 ms: 1.02x slower (+2%) |
+-------------------------+--------------------------------------+---------------------------------------+
| python_startup_no_site | 7.83 ms | 8.04 ms: 1.03x slower (+3%) |
+-------------------------+--------------------------------------+---------------------------------------+
| scimark_sparse_mat_mult | 9.28 ms | 9.57 ms: 1.03x slower (+3%) |
+-------------------------+--------------------------------------+---------------------------------------+
| unpickle | 28.0 us | 28.9 us: 1.03x slower (+3%) |
+-------------------------+--------------------------------------+---------------------------------------+
| regex_effbot | 4.70 ms | 4.86 ms: 1.03x slower (+3%) |
+-------------------------+--------------------------------------+---------------------------------------+
| xml_etree_iterparse | 178 ms | 184 ms: 1.04x slower (+4%) |
+-------------------------+--------------------------------------+---------------------------------------+
| python_startup | 11.5 ms | 12.0 ms: 1.04x slower (+4%) |
+-------------------------+--------------------------------------+---------------------------------------+
| scimark_monte_carlo | 212 ms | 221 ms: 1.04x slower (+4%) |
+-------------------------+--------------------------------------+---------------------------------------+
| pathlib | 38.6 ms | 40.5 ms: 1.05x slower (+5%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sqlite_synth | 7.85 us | 8.26 us: 1.05x slower (+5%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sqlalchemy_imperative | 62.9 ms | 66.2 ms: 1.05x slower (+5%) |
+-------------------------+--------------------------------------+---------------------------------------+
| richards | 138 ms | 145 ms: 1.05x slower (+5%) |
+-------------------------+--------------------------------------+---------------------------------------+
| crypto_pyaes | 199 ms | 210 ms: 1.06x slower (+6%) |
+-------------------------+--------------------------------------+---------------------------------------+
| nbody | 249 ms | 265 ms: 1.06x slower (+6%) |
+-------------------------+--------------------------------------+---------------------------------------+
| raytrace | 937 ms | 995 ms: 1.06x slower (+6%) |
+-------------------------+--------------------------------------+---------------------------------------+
| deltablue | 13.4 ms | 14.2 ms: 1.06x slower (+6%) |
+-------------------------+--------------------------------------+---------------------------------------+
| tornado_http | 276 ms | 295 ms: 1.07x slower (+7%) |
+-------------------------+--------------------------------------+---------------------------------------+
| scimark_lu | 247 ms | 264 ms: 1.07x slower (+7%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sqlalchemy_declarative | 280 ms | 300 ms: 1.07x slower (+7%) |
+-------------------------+--------------------------------------+---------------------------------------+
| dulwich_log | 143 ms | 153 ms: 1.07x slower (+7%) |
+-------------------------+--------------------------------------+---------------------------------------+
| chaos | 210 ms | 226 ms: 1.07x slower (+7%) |
+-------------------------+--------------------------------------+---------------------------------------+
| 2to3 | 594 ms | 639 ms: 1.08x slower (+8%) |
+-------------------------+--------------------------------------+---------------------------------------+
| unpickle_list | 6.60 us | 7.10 us: 1.08x slower (+8%) |
+-------------------------+--------------------------------------+---------------------------------------+
| float | 213 ms | 229 ms: 1.08x slower (+8%) |
+-------------------------+--------------------------------------+---------------------------------------+
| pyflate | 1.27 sec | 1.37 sec: 1.08x slower (+8%) |
+-------------------------+--------------------------------------+---------------------------------------+
| go | 481 ms | 522 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| pickle_pure_python | 966 us | 1.05 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| meteor_contest | 175 ms | 191 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| genshi_xml | 148 ms | 161 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| chameleon | 20.6 ms | 22.5 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| nqueens | 191 ms | 208 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| telco | 14.6 ms | 16.0 ms: 1.09x slower (+9%) |
+-------------------------+--------------------------------------+---------------------------------------+
| logging_format | 22.1 us | 24.2 us: 1.10x slower (+10%) |
+-------------------------+--------------------------------------+---------------------------------------+
| regex_compile | 322 ms | 355 ms: 1.10x slower (+10%) |
+-------------------------+--------------------------------------+---------------------------------------+
| hexiom | 16.4 ms | 18.1 ms: 1.10x slower (+10%) |
+-------------------------+--------------------------------------+---------------------------------------+
| json_dumps | 25.6 ms | 28.3 ms: 1.10x slower (+10%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sympy_sum | 397 ms | 439 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sympy_integrate | 42.7 ms | 47.2 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| django_template | 120 ms | 133 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sympy_str | 633 ms | 702 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| xml_etree_generate | 162 ms | 180 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| spectral_norm | 244 ms | 272 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| xml_etree_process | 134 ms | 149 ms: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| logging_simple | 19.3 us | 21.5 us: 1.11x slower (+11%) |
+-------------------------+--------------------------------------+---------------------------------------+
| mako | 28.2 ms | 31.5 ms: 1.12x slower (+12%) |
+-------------------------+--------------------------------------+---------------------------------------+
| fannkuch | 853 ms | 954 ms: 1.12x slower (+12%) |
+-------------------------+--------------------------------------+---------------------------------------+
| sympy_expand | 983 ms | 1.11 sec: 1.13x slower (+13%) |
+-------------------------+--------------------------------------+---------------------------------------+
| genshi_text | 64.0 ms | 72.9 ms: 1.14x slower (+14%) |
+-------------------------+--------------------------------------+---------------------------------------+
| unpack_sequence | 123 ns | 142 ns: 1.16x slower (+16%) |
+-------------------------+--------------------------------------+---------------------------------------+
| logging_silent | 311 ns | 364 ns: 1.17x slower (+17%) |
+-------------------------+--------------------------------------+---------------------------------------+
| unpickle_pure_python | 581 us | 683 us: 1.17x slower (+17%) |
+-------------------------+--------------------------------------+---------------------------------------+

Not significant (2): pickle_list; regex_dna; pickle_dict; scimark_sor; regex_v8

[pablogsal]

System state
============

CPU: use 12 logical CPUs: 1,3,5,7,9,11,13,15,17,19,21,23
Perf event: Maximum sample rate: 1 per second
ASLR: Full randomization
Linux scheduler: Isolated CPUs (12/24): 1,3,5,7,9,11,13,15,17,19,21,23
Linux scheduler: RCU disabled on CPUs (12/24): 1,3,5,7,9,11,13,15,17,19,21,23
CPU Frequency: 0,2,4,6,8,10,12,14,16,18,20,22=min=1600 MHz, max=3333 MHz; 1,3,5,7,9,13,15,17,19,21,23=min=max=3333 MHz
Turbo Boost (MSR): CPU 1,3,5,7,9,11,13,15,17,19,21,23: disabled
IRQ affinity: irqbalance service: inactive
IRQ affinity: Default IRQ affinity: CPU 0,2,4,6,8,10,12,14,16,18,20,22
IRQ affinity: IRQ affinity: IRQ 0,2=CPU 0-23; IRQ 1,3-15,17,20,22-23,28-51=CPU 0,2,4,6,8,10,12,14,16,18,20,22

[zooba]

If it's easy to set up, it might be interesting to see if there's a difference if (e.g.) all interned strings are marked as immortal, or all small ints. Or type objects. Maybe set a flag during initialization and treat everything created before that as immortal.

There's definitely going to be overhead, but assuming the branch is there we may as well use it to optimise our own operations.

[pablogsal]

Thanks, Eddie for sharing the patch. I think this is an interesting discussion: for instance, in the core dev sprint at Microsoft I recall that we had a quick discussion about having immortal references.

After analyzing the patch, and even assuming that we add conditional compilation, here are some of the things I feel uneasy about:

• Anything that is touched by the immortal object will be leaked. This can also happen in obscure ways
  if reference cycles are created.

• As Eddie mentions in the PR, this does not fully cover all cases as objects that become tracked by the GC
  after they are modified (for instance, dicts and tuples that only contain immutable objects). Those objects will
  still, participate in reference counting after they start to be tracked.

• As Gregory mentions, if immortal objects are handed to extension modules compiled with the other version of the
  macros, the reference count can be corrupted. This may break the garbage collector algorithm that relies on the
  the balance between strong references between objects and its reference count to do the calculation of the isolated cycles.
  This without mentioning that this defies the purpose of the patch in those cases, as a single modification of the reference
  the count will trigger the copy of the whole memory page where the object lives.

• The patch modifies very core mechanics of Python for the benefit of a restricted set of users (as Gregory mentions): no
  threads, POSIX and forking.

• Is not clear to me that leaking memory is the best way to solve this problem compared to other solutions (like having the
  the reference count of the objects separated from them).
  objects separated from them.

There is a trend right now to try to remove immortal objects (started by Victor and others) like static types and transforming them to heap types. I am afraid that having the restriction that the interpreter and the gc needs to be aware
of immortal types can raise considerably the maintenance costs of already complicated pieces of the CPython VM.

[pablogsal]

If it's easy to set up, it might be interesting to see if there's a difference if (e.g.) all interned strings are marked as immortal, or all small ints. Or type objects. Maybe set a flag during initialization and treat everything created before that as immortal.

I can look into it, the main problem is that every run of the pyperformance test suite takes several hours, even more with --full-pgo :( I will try to set up some automation for that when I have some free cycles

[zooba]

There is a trend right now to try to remove immortal objects (started by Victor and others) like static types and transforming them to heap types.

This isn't actually about removing immortal objects, but removing *mutable* objects that would be shared between subinterpreters. Making some objects immortal, such as interned strings or stateless singletons, would actually benefit this work, as they could then be safely shared between subinterpreters.

But as you say, the added complexity here is starting to seem like it'll cost more than it's worth...