PEP 795 revamped: Deep Immutability for Efficient Sharing and Concurrency Safety

PEPs
21

I like the focus on the high-level programming model in the revamped PEP. It helps highlight some useful semantics that we may want to see in future Python. There are certain points in the PEP that hint at a different way than how things are handled in the language now, which I think will be worth discussing first in their own merits.

Freezing functions is particularly interesting to me. Listing 14 in the PEP:

# pure function -- freezing will not propagate
def function1(a, b):
    return a + b

# freezing will propagate to function1
def function2(a, b):
    return function1(a, b)

freeze(x)
# only captures immutable state -- freezing will not propagate
def function3(a):
    a.append(x)

# freezing will propagate to y
def function4(a):
    y.append(a) # Note -- will throw exception always when called

Currently function (and code) objects in Python are dynamic in the sense that they don’t actually hold references to the objects referred by the closures in their body (free variables, globals, builtins). What they do effectively hold is the same live globals dict as the module through which they do the name lookups. The bytecode also shows that in function2 the function1 is a global name lookup. y in functon4 is also a global name lookup, while the append methods in function3 and function4 are attribute lookups.

dis.dis() of Listing 14 
  0           RESUME                   0

  2           LOAD_CONST               0 (<code object function1 at 0x000001FDD0174B70, file "<dis>", line 2>)
              MAKE_FUNCTION
              STORE_NAME               0 (function1)

  6           LOAD_CONST               1 (<code object function2 at 0x000001FDD0174C60, file "<dis>", line 6>)
              MAKE_FUNCTION
              STORE_NAME               1 (function2)

  9           LOAD_NAME                2 (freeze)
              PUSH_NULL
              LOAD_NAME                3 (x)
              CALL                     1
              POP_TOP

 11           LOAD_CONST               2 (<code object function3 at 0x000001FDD016CD30, file "<dis>", line 11>)
              MAKE_FUNCTION
              STORE_NAME               4 (function3)

 15           LOAD_CONST               3 (<code object function4 at 0x000001FDD016F830, file "<dis>", line 15>)
              MAKE_FUNCTION
              STORE_NAME               5 (function4)
              LOAD_CONST               4 (None)
              RETURN_VALUE

Disassembly of <code object function1 at 0x000001FDD0174B70, file "<dis>", line 2>:
  2           RESUME                   0

  3           LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
              BINARY_OP                0 (+)
              RETURN_VALUE

Disassembly of <code object function2 at 0x000001FDD0174C60, file "<dis>", line 6>:
  6           RESUME                   0

  7           LOAD_GLOBAL              1 (function1 + NULL)
              LOAD_FAST_BORROW_LOAD_FAST_BORROW 1 (a, b)
              CALL                     2
              RETURN_VALUE

Disassembly of <code object function3 at 0x000001FDD016CD30, file "<dis>", line 11>:
 11           RESUME                   0

 12           LOAD_FAST_BORROW         0 (a)
              LOAD_ATTR                1 (append + NULL|self)
              LOAD_GLOBAL              2 (x)
              CALL                     1
              POP_TOP
              LOAD_CONST               0 (None)
              RETURN_VALUE

Disassembly of <code object function4 at 0x000001FDD016F830, file "<dis>", line 15>:
 15           RESUME                   0

 16           LOAD_GLOBAL              0 (y)
              LOAD_ATTR                3 (append + NULL|self)
              LOAD_FAST_BORROW         0 (a)
              CALL                     1
              POP_TOP
              LOAD_CONST               0 (None)
              RETURN_VALUE

By deep-freezing functions we may want to lock down the name lookups so that they are resolved and bound eagerly at freeze-time. This means we have to

  • eliminate closures (by means of having the code object bind actual references to the objects referred by the names, like how methods are bound to the self object),
  • or at least freeze their namespaces (which depending on case may not be possible)

Assuming we read append in the above examples as a non-mutating method called my_method, the dot attribute lookup on global name (y.my_method ) in function4 can be frozen, but not a.my_methodin function3 which must remain virtual dispatch. If we choose to eliminate closures by means static dispatch of y.my_method, this will allow the interpreter to elide a global name lookup at invoke-time and may actually be useful for optimization projects like JIT, which will now be able to “see through” a code object’s name bindings more easily and provide better specialization. But doing things this way doesn’t work well[1] with PEP 810 – Explicit lazy imports | peps.python.org where any lazy import will need to be resolved eagerly by function deep freezing.

  1. The compatibility matrix of the multiple projects trying to enable parallelism and/or optimization into Python (free-threading, subinterpreters, JIT, lazy import and freezing) is only to get more complicated over time. ↩︎

1 Like
22

FYI, I have now addressed your first two bullet points. Will report back later on the remaining stuff. Thanks!

1 Like
23

I have now added a section about this: Accessing subclass information and subclassing immutable classes.

24

I sort of agree with @beauxq point that when the PEP is justifying treating frozen objects as having the same (runtime) type, this example is a weak argument.

More important than the particular choice of example though, I’d push the authors to consider more broadly the question of how Python’s type system should interact with (deep) immutability. For example, what about type annotations and static typing? Even though the language allows doing at runtime lots of things that violate the conceptual model of the static type system, and vice versa there can be constraints on what calls will work that cannot be captured by static types, people still find type checkers useful! It would be good to have a section about this even if very brief. It’s reasonable if, say, you want to postpone static typing to a follow-up post implementation because typing_extensions and 3rd party type checkers can evolve independently of CPython’s release schedule.

For example, some ideas that were probably mentioned in previous threads): should there be a special form Frozen[T] that checkers understand and then warn about write attempts? (There are alternative ways the same idea could be “spelled”). If my function expects its argument is immutable and I annotate it as such, checkers could enforce that only variables they understand to be of Frozen type can be passed at a call site. is_frozen should be supported as a TypeGuard.

25

This could only ever work in one direction. A type checker would never be able to prove that an object is not frozen because anything anywhere could freeze it in place at any time. I don’t think that is something that could ever be fixed by adapting the type system as long as freezing is an in-place operation.

If it is important to know that an object is not frozen then you end up with the Py_CHECKWRITE mess that @ZeroIntensity shows above.

How does Py_CHECKWRITE work in the free-threading build? The example from the PEP looks like a data race to me:

if (!Py_CHECKWRITE(op)) {
    PyErr_WriteToImmutable(op);
    return NULL;
}

/* What prevents another thread from freezing the 
 * object between the check above and the write below? */ 

... // code that performs the write

Is there some lock that prevents other threads from freezing the object?

2 Likes
26

For free-threading we can just use the existing free-threading atomic biased reference counting for all objects. It is only for GIL enabled builds that we need to adapt the reference counting for sharing of immutable objects.

In your particular, example that would only require a single check just before the assignment? But if there were more updates, than there would need one for each location if things can change. If you have multiple updates and between those updates you call into Python, then care is needed. This is the case for many things. If you read a value from a field, and call back into Python, then you don’t know it has the same value. I think this is tricky to get right for immutability, but I am not convinced it is worse than what developers already should be handling to work with concurrency in a GIL enabled build.

In a GIL disabled build, then there are update to last_result in @ZeroIntensity’s example would already require some care to correctly handle the old value, and potential concurrent updates. That really would involve either a lock or an atomic exchange. If it uses a lock, then we would place the Py_CHECKWRITE inside the lock.

For example, in the prototype we have tried to place the checks inside already held locks. E.g. the first one I found inside dictobject.c:

I think that immutability would not be possible to work with exchange in free-threading. As it would always be a time of check - time of use bug.

We are using the mimalloc build, so different interpreters can deallocate objects than created them in the first place. In the GIL enabled build, we remove objects from the per-interpreter doubly linked list of objects when they become immutable. In the GIL disabled build, we rely on the free-threaded work to collect cycles.

The prototype is somewhat lacking in support for free-threading, and my plan is to advance that next.

1 Like
27

Well, in theory, yes – but in practice, people aren’t as careful as you’d think. The problem is that with weird re-entrancy problems, getting something wrong is currently just a slap on the wrist. If you break an object by doing something strange in a __bool__ method or similar, then that’s just a cool party trick (assuming it doesn’t crash). But if you’re able to break immutability by doing that, then that’s a real thread-safety problem.

With that in mind, here’s an idea: instead of freezing an object in-place, there could be a protocol that steals data from a mutable object and reuses it in a frozen object. For example:

from immutable import freeze

class Foo:
    def __init__(self):
        self.value = 42

foo = Foo()
frozen_foo = freeze(foo)
assert frozen_foo.value == 42
# Accessing foo.value would now raise an AttributeError, since its data was stolen by frozen_foo.

I see two major benefits to this approach:

  1. We can avoid issues with the Py_CHECKWRITE dance in most places, because we know that an object won’t magically become immutable. This solves my concerns from above.
  2. If we copy a little bit of the data (such as the type), we can still achieve deep immutability without viral freezing. This will help support more objects.

In fact, we already have bytearray.take_bytes in 3.15 that does something very similar. Basically, my idea is to turn that functionality into a protocol.

My other comments aside, I think it would be a lot easier to make a stop-the-world pause when making objects immutable. That way, there are no additional cases to handle in the free-threaded build that aren’t already present in the GIL-ful build.

Is that something mimalloc really lets you do? As of now, most interpreters have their own obmalloc state (except for ones that have PyInterpreterConfig.use_main_obmalloc = 1), so subinterpreters generally can’t deallocate objects that they don’t own, because the object would try to release an allocation belonging to a different allocator.

Even if mimalloc happens to work with this right now, I still think we need a better solution. Embedders are allowed to install their own allocators via PyMem_SetAllocator, and those are not guaranteed to be cross-interpreter safe either.

2 Likes
28

Thanks for revising the PEP. This does clarify some things from before and removing the automatic freeze-propagation is a big improvement. However, I still have some uncertainty.

From now on, we will use immutable to mean deeply immutable, and use shallow immutability to mean the protection offered by tuples and frozen sets in Python 3.14.

I fear that that using the terminology in this way will lead to enormous confusion later on in the Python community if this PEP is accepted. I realize this is just a PEP, but we have seen before that the terminology a PEP uses tends to propagate into wider use. The words “mutable” and “immutable” have established usages in Python stretching back decades, and under that usage (as an example) tuples are immutable. Introducing new terminology that says tuples are not immutable is going to be really really confusing for anyone looking at anything written in a blog post, StackOverflow answer, etc. Sometimes this is unavoidable but given how basic this distinction is current Python I think it’s worth trying to avoid it here.

I’m not sure what the best alternative is though. “Demutable” (for “deeply immutable”, and with the “de-” also implying “not mutable”, as “de-escalate” means to un-escalate)? “Frozen” (already used throughout the PEP)? “Ice-nined” (which I suggested before as a humorous riff on the propagation of freezing)?

The separation of the PEP into these two aspects is prompted by discussions at DPO in order to clarify the “return on investment” for various aspects of this PEP

I realize what I’m saying may sound ungrateful after all you’ve done :upside_down_face: but I still find this PEP mixes things in a way that’s a bit difficult to wrap my head around. The reason is that from my perspective the “costs” of the proposal primarily lie in its (potential) unexpected effects on code that has no intention of using freezing or subinterpreters at all, while its benefits lie in its use by code that wants to use multiple subinterpreters. But the PEP mixes its discussion of the specification of freezing per se with discussion of the way that subinterpreters want to use frozen objects.

I’m not suggesting another total rewrite of course! But would it be possible to state, up front (or at the two “fronts” of the section on freezing already-immutable objects and on freezable objects), a brief and comprehensive explanation of just how freezing and its propagation work, with no reference to the concept of subinterpreters at all? In other words, if I have never heard of subinterpreters but I have some code and I get some kind of error because something was frozen and I didn’t expect it to be, what do I need to know about freezing in order to understand what is going on? Presumably some dependency I’m using froze something, but subinterpreters only represent the motivation for freezing things; what I want to know is mainly the specification of how the freezing takes place, at the level of Python code (i.e., not the C implementation).

The changes proposed by this PEP require a way to find all objects which are reachable from a given object.

Can you clarify what that way is in pure-Python terms? Is it anything else besides the set of all values of all attributes of an object?

Sometimes it is necessary to run some code just before an object is frozen. This can be done by calling set_pre_freeze_hook with a callable that will be invoked just before freezing the object.

The phrasing “just before freezing the object” implies to me that nothing can intervene between the return of the pre-freeze hook and the actual freezing of the object. However, later:

The freeze function is arguably the most important function in this PEP. A call to freeze(obj, ...) will traverse the object graph starting in obj. For each object it will check the freezability of the object, if the object is freezable, the pre-freeze hook of the object will be called.

This reads to me like the hook is not actually called before freezing, but when the check-if-freezable propagation reaches the object.

These are different things. If the pre-freeze hook of obj is called “just before freezing obj” it would mean to me that all objects reachable from obj have already had their pre-freeze hooks called and have in fact already been frozen (i.e., objects are frozen bottom-up from the “leaves” of the reference graph). If it is called when check-if-freezable propagation reaches obj then it means the objects references by obj will subsequently have their own hooks called, which could mean that obj turns out not to be freezable even if its pre-freeze hook says all is well.

Can this be clarified? If I have an object a and another object referenced via a.b (with no back-reference), in what order do the following steps occur:

  1. a.__pre_freeze__ is called
  2. a.b.__pre_freeze__ is called
  3. a is actually frozen
  4. a.b is actually frozen

Relatedly, this is getting at what I meant above by a subinterpreter-less explanation of the freezing process. It would be nice to see a simple example (or a few related ones) that has a few objects and shows in excruciating detail the sequence of operations that occur when freeze is called on one of them (but without focusing on the C implementation details of this). The PEP has some useful such examples, but as far as I can see they don’t actually zoom in on the propagation process. This is kind of important given the notes in the PEP about how the effects of __pre_freeze__ are not undone; in that case it’s going to be crucial to know the order in which different hooks are going to be called.

When a function is frozen, we decouple it from its defining context in two ways. This logic is handled transparently in the pre-freeze hook of the function type object:

  1. We re-point its captured globals to point to a copy that contains only the values that the function captured. (So random and x in our example above, but not y.) The copy is shallow.
  2. We freeze the globals copy which freezes the values which are shared between the globals dictionaries, but keeps the variables in the defining context’s globals dictionary mutable. Thus, x = [5, 6, 7] is permissible, and because that updates the sender’s x to point to a mutable object, the subsequent append is permitted.

Every function contains a reference to its globals in func.__globals__. The globals will also contain a reference to pretty much everything else in the module (perhaps via intermediate objects like classes), including in particular any other modules imported by the module. This would seem to suggest that in most existing code, freezing a function will not be possible, because it would require freezing all imported modules (and modules are by default not freezable). It means that actually writing a function that is actually freezable would be a rather tricky task, since you’d have to make sure not to import anything or otherwise leak any “normal” objects into the module.

Now, to be clear, that sounds pretty good to me! :slight_smile: It’s a lot better than the previous proposal where freezing could propagate willy-nilly. But I think it might be worth saying that explicitly and maybe giving an example and/or use case of how this might be done. Because it does mean that in general it’s not going to be possible to just take some existing code and start freezing stuff. Freezing would be more like an async-style “coloring” where a module would have to be deliberately designed to support it.

The concept of the state of the type already exists in Python for example, a file cannot be read from or written to when it is closed. Thus, making an object immutable in-place can be viewed as consistent with existing Python mental model.

I agree with @beauxq that this is a rather weak justification. In particular, file closure does not propagate to anything else, but freezing may. It’s certainly true that people can write Python code that objects that can change state in ways that profoundly affect their usage. But it’s also pretty clear that this PEP is proposing layering such possibilities over pretty much the entirety of Python’s object model. The magnitude of that change is not comparable to isolated cases like closed file objects.

Hopefully it’s clear from my comments that I’m mainly approaching this PEP from the perspective of someone who will probably not use it. :slight_smile: But even people who won’t use it will potentially be impacted by it. So my questions are aimed at making sure that the essentials are crystal clear even to people who do not want to know anything about subinterpreters, but still want to know what the practical effects may be if their code (or its dependencies) somehow freezes an object.b

1 Like
29

This is what point 1. in the quote you posted is about: this is not true for a frozen function, it’s __globals__ gets reduced to a smaller set of objects, those that are actually used from inside the function.

This makes it significantly easier to freeze functions, especially if you use from imports.

30

How will functions like these be handled:

x = []

def func1():
	globals()['x'].append("?")

def func2():
	def inner():
		x.append("??")
	inner()
31

func1 fails with a KeyError when called because globals() doesn’t contain 'x'.

func2 is going to fail because x is frozen when it’s captured by func2 being frozen.

32

You mean it will fail in that way when frozen? Yeah that doesn’t seem like great behavior to me.

What is the reference chain from func2 to to x?

33

The global x is referenced within the body of func2. This is something the static analyzer that decides how function objects are frozen needs to detect, even if the reference is inside a local function. Then when the inner function is constructed it inherits func2.__globals__, which is a frozen dict containing the frozen x.

:person_shrugging: Maybe. But it’s the obvious consequence of the currently described behavior, and I am not sure if any changes to the behavior are better. My argument was just that you misunderstood the current behavior in this regard, I am not going to invest energy into defending the behavior.

34

Okay, but for instance currently if you have:

x = []

def func():
    x.append("?")

Then at least you can see that 'x' is in func.__code__.co_names. But for my func2 example with the nested function, x is not in func2.__code__.co_names. This is kind of what I was getting at in my original comments with wanting a more comprehensive Python-level specification of how the process works. Right now, as you say, it seems all we know is that “this is something the static analyzer that decides how function objects are frozen needs to detect”. But I’m not really comfortable with that. I would want a complete specification of how that algorithm works and what information it takes account of.

35

There are certain points in the PEP that hint at a different way than how things
are handled in the language now, which I think will be worth discussing first in
their own merits.

Indeed, specialising frozen functions or types is a possibility that we have also been talking about. However, this seems to be something that should be looked at after this PEP. Let’s wait until this PEP
(hopefully) lands as well as PEP810. (Happy to discuss them further though!)

36

PEP text:

The concept of the state of the type already exists in Python for example

Several people have complained about the file type being opened or closed being poor motivation or justification for freezing type objects in-place instead of making a frozen copy for types. Note that this was not intended to motivate or justify this decision – the motivation is the first list in Immutable objects have different types under Rejected alternatives. For convenience, here is that list again:

  • It requires duplicating much of the code for each type, leading to code bloat and maintenance issues.
  • It requires copying the entire object graph to create an immutable version of an object, which can be expensive both in time and memory.
  • It requires programmers to change the types they use when they want immutability, leading to code changes and potential compatibility issues.

There are more reasons which didn’t make the PEP for brevity which revolve around how CPython internally uses class object identity for things like isinstance and issubclass, lookup caches, etc.

I suggest we will remove this example in the PEP to avoid this obvious red herring.

37

Context: PEP proposes that globals()['x'] inside a frozen function will fail (unless x is captured
elsewhere in the same frozen function).

I disagree. It is possible to a limited extent to analyse the function and support things like this but this falls apart pretty quickly – e.g. if y is computed by the function being frozen, then the meaning of globals()[y] will not be known until run-time, and may even vary between calls. IMO, the behaviour that is most consistent and easiest to understand and explain is that calls to globals() inside a frozen function will only be able to access the frozen function’s copy of globals and hence only see the variables which the function captured from global scope. This is not so different from globals()['x'] failing in normal Python because there wasn’t an x (ever or anymore) in globals().

Most functions that use globals() should probably not be frozen in the first place. To that end, the @unfreezable decorator can be used.

(Another option is to pass in globals as an argument.)

2 Likes
38

Excellent suggestion. We will update the PEP’s section The freeze function with a pure
Python sketch of how freeze() works to clarify this. We will also add a forward reference
to this earlier in the PEP when introducing the freeze function and the pre-freeze hook. Please take a look at the following which is a draft of how we will update the PEP.

Explaining how freezing works through sketching its implementation in Python

# Defined in the immutable module
def freeze(*explicit_args):
    from gc import get_referents
    from immutable import is_frozen, get_freezable, YES, \
        EXPLICIT, PROXY, NotFreezableError

    tentatively_frozen = []
    proxies = []

    # Make obj immutable (possibly also a proxy)
    def do_freeze(obj):
        if obj in proxies:
            # Turns obj into immutable proxy for mutable
            # copy on the current sub-interpreter
            pass
        else:
            # Set flag in object header
            pass

    # Return all objects reachable from obj
    def reachable(obj):
        # Note: in practise we cannot use this method because
        # it is not guaranteed to return *all* reachable sub-objects
        return get_referents(obj)

    # Check if obj is freezable
    def is_freezable(obj):
        status = get_freezable(obj)
        if status is YES:
            return True
        elif status is PROXY:
            proxies.append(obj)
            return True
        elif status is EXPLICIT:
            return obj in explicit_args
        else:
            return False

    # Populate the tentatively_frozen and proxies lists by
    # traversing the heap from obj
    def traverse(obj):
        if is_frozen(obj) or obj in tentatively_frozen:
            pass
        elif is_freezable(obj):
            if hasattr(obj, "__pre_freeze__"):
                obj.__pre_freeze__()
            tentatively_frozen.append(obj)
            # Actual implementation uses a work list, not recursion
            for r in reachable(obj):
                traverse(r)
        else:
            raise Exception()

    try:
        for obj in explicit_args:
            traverse(obj)
        for o in tentatively_frozen:
            do_freeze(o)
        return explicit_args
    except Exception:
        # Failure to freeze
        raise NotFreezableError()
1 Like
39

You are listing a bunch of different reasons here for why it is better to be able to freeze in-place rather than have separate immutable types but I think the only valid reason listed is the copying one. Programmers already change types like list to tuple when needed. There are ways to reduce the code duplication or the duplication is not that big of a problem.

There are many advantages in having separate immutable types:

  • The code for the types knows that they are immutable and does not have things like methods that would be broken by freezing.
  • You can check if the object is of an immutable type at runtime with isinstance.
  • Type checkers can track the difference between mutable and immutable types.

I can try to make a longer list if you like but the reasons are basically the reasons that Python already has immutable and mutable types rather than anything like the mechanism proposed here. If people thought that a list.freeze() method was a good idea then it could have been added at any time but instead we have tuple(mylist).

The fact that programmers have to change the types for immutability is actually a good thing because it is then clear in the code where that conversion is happening which is what makes it clear to readers of the code and type checkers and so on.

I see only two real advantages for in-place freezing one of which is what you listed:

  • It avoids making a potentially expensive in memory copy.
  • It allows freezing existing types that had not been designed with the mechanism in this PEP in mind.

The latter reason is I think questionable since it means effectively being able to break types from existing libraries i.e. I would expect to see bug reports like “I tried to freeze libfoo.SomeType and everything broke”. It would be better to turn that around as a feature request like “Can we add a libfoo.FrozenSomeType?”.

So really I think it just comes down to the in-memory copy. The question is basically the trade off between having to copy some potentially large object to be able share it vs all the other brokenness that would come from objects being unpredictably frozen in ways that type checkers, runtime checks, library code etc would have no way of keeping track of.

It is difficult to think about that trade off without thinking about actual use cases. I can certainly imagine wanting to share say a large numpy array across interpreters and threads. But do we even need in-place freezing for that example? I thought I heard that numpy arrays could already be shared across subinterpreters or at least that the memory buffer can be. What exactly are the situations where people want to share lots of stuff across interpreters and how much of a problem would the copying be?

3 Likes
40

Just to clarify, I’m not thinking about this example or the freeze-in-place semantics as just competing with an alternative in which there are separate frozen types. It’s an open question for me whether the freezing benefits are worth the cost at all. In other words, either freeze-in-place or separate-frozen-types might still be too much complexity to justify, and there’s a real chance the right answer is to just reject both options and keep the status quo, with no freezing at all.

2 Likes