PEP 841: Adding Frozen Syntax to Make Immutable Types Optimizable

PEPs
1

Hi all,

@sobolevn and I would like to propose PEP 841, which adds frozen display
syntax: f{1, 2, 3} creates a frozenset and f{'a': 1} creates a
frozendict.

Why we think Python needs this:

  • frozenset and frozendict are builtin immutable types, but they
    have no display syntax. Today the only way to create them is calling
    the builtin functions.
  • Dedicated syntax makes optimization much easier. The compiler gets a
    guarantee that the result is immutable, so it can fold constant
    displays into constants. There are other approaches, but they are much harder than using a
    guarantee that the syntax itself provides.
  • f{...} looks similar to f-string syntax, but they are different at
    the tokenizer level, so there is no conflict. Also, f-strings produce
    an immutable string anyway, so the f prefix consistently gives you
    an immutable value.
  • Based on the above, we believe this is a needed step toward a safer
    future Python, where immutable data is easy to write and cheap to use.

PR for the PEP: PEP 841: Adding Frozen Syntax to Make Immutable Types Optimizable by corona10 · Pull Request #5049 · python/peps · GitHub
Reference implementation: GitHub - corona10/cpython at fset_fdict · GitHub

We will keep this discussion open for at least two weeks before moving
forward. Any feedback is welcome.

cc @vstinner

26 Likes
2

Thank you Donghee and Nikita for working on this, it’s an interesting idea.

I think after reading over the PEP I would request that you expand on a few points:

  1. Are there significant performance gains to be won here, and have you investigated what that might look like? I understand that syntax is easier to optimize but I don’t see any analysis of what the impact of the optimization would be other than there are ~100 sites of frozen containers in CPython. It isn’t clear to me if the performance wins are worth the new syntax.
  2. Have you done any research into whether users would be easily confused with f-strings? The fact that we are giving a new meaning to an f prefix might confuse users. Perhaps it would be useful to confer with some Python educators or hold a poll about it and cover the results in the “How to teach this” section.
  3. In rejected ideas you say that freezing methods are not real alternatives but do not discuss why. I think it would be good to cover that because it is not immediately evident to me.
4 Likes
3

I think this is a chicken-and-egg problem. If immutable containers do not offer the same level of support as their mutable counterparts, people will be less likely to use them, especially since they share most of the same underlying structure apart from mutation operations.
One of our main goals is therefore to enable the same level of optimization and usage through syntax for immutable containers.

Actually, we had a poll for this `frozenset` and `frozendict` comprehensions - #48 by sobolevn, and I believe that the f prefix would not be a bad choice with the reasons that I listed.

Thanks will do :slight_smile:

1 Like
5

That syntax is already used for indexing.

6

… I should stop asking my questions just after waking up. Yes… (so I deleted my post)

7

Are they really “much” harder? The compiler should have some kind of symbol table for every name used in the file, and the only case where frozenset could be overridden without appearing in it should be import *. Everything else is really just going to be “has there been any use of this name other than as a call target” question - we’re optimising, not proving correctness.

I’d be quite happy with the presence of import * disabling the compile-time optimization of frozen collections. The contexts where a statically defined frozen collection provide any benefit can easily avoid import *.

Speaking of benefits, what contexts are there a benefit? It’s usually accepted that a small number of elements are cheaper to handle with linear search than doing a hash calculation, and I’m not sure where that line gets crossed but I’m fairly confident I don’t want to type out a big enough frozen set to make it worth it not just being a tuple. It has to be compile-time static, which means the values are almost certainly singletons or interned strings, so we’re really just talking about very large generated files, right? Is the optimization of converting from a mutable set to a frozen one the biggest cost here, given we have the ability to transfer the internal data for practically free[1]?

From a reading point of view, how does this information quickly help someone understand the code they’re looking at? Most developers are going to read a top-level variable from a generated file and assume that it’s constant, even if it’s technically a mutable type, unless there’s other evidence around it showing that it’s intended to be mutated (such as a comment, or a helper function that does it). Adding one character doesn’t seem to be a big benefit here.

From a typing[2] point of view, how often are people having to type frozenset() that abbreviating it becomes important? Why isn’t the more appropriate and efficient abbreviation simply to use a regular set and then not mutate it (thinking of REPL usage here)?

For me, the premise doesn’t rise to the level of needing syntax, regardless of what shape that syntax takes. Python is a scripting language, so defaulting to mutable is entirely defensible, and those who are trying to build robust, systems-level apps in it should be the ones to do additional work, such as using wrappers or tools to detect their own mistakes[3].

  1. If you have allocated 1001 objects (contents + set), then allocating 1002 (contents + set + frozenset) is practically free. ↩︎

  2. As in, pressing keys on a keyboard. I don’t want to assume that everyone knows I’m not going to factor in static typing into any design until the point where we want to make the static typing actually match the feature. If you ever see me write “typing”, it means someone actually pressing the keys on the keyboard to transfer their ideas into a shareable, executable format. ↩︎

  3. Not a criticism, just an observation that “step toward a safer future Python” implies that this will help detect mistakes made that are written in Python code, therefore by the user, rather than mistakes in the runtime. ↩︎

8 Likes
8
Please ignore this Is this the intended output of this script? 
>>> class MyCustomFrozenDict(frozendict):
...     def __new__(self, o):
...         super().__new__(self, o)
...         print("created custom frozendict")
...
>>> frozendict = MyCustomFrozenDict
>>> frozendict({1:2})
created custom frozendict
>>> f{1:2}
frozendict({1: 2})
>>>

If so, I think it’s a bit surprising. (This what I got when running the reference implementation.) Would this be a necessary corner case for the proposed optimizations to work?

I don’t dislike the new syntax, but I also think these optimizations could be performed by a hopefully-staying JIT.

EDIT: it’s the same behavior for dict/set/etc., so it’s totally fine for frozendict/set to behave the same way.

1 Like
9

The simple reality is that a one-symbol prefix will make frozensets and frozendicts many times (5x? 10x?) more popular and often-used than clunky frozenset()/frozendict() calls. This is a core construct for the functional coding style. Making it as friction-free as possible is absolutely vital.

One thing I wish would happen is that people stop blocking things that are important for a (completely valid and popular enough) style of coding they personally don’t use or like. This happens all the time here, just look at the Annotated thread.

3 Likes
10

I don’t dislike the new syntax, but I also think these optimizations could be performed by a hopefully-staying JIT.

Yeah, the JIT already does something similar. To fold len(“abc”) into 3, it first has to guard that the name still means the builtin len: gh-144140: Optimize len for string constants in optimizer by y1yang0 · Pull Request #144142 · python/cpython · GitHub

If we add new frozen syntax, BUILD_FROZENSET and BUILD_FROZENMAP fix the semantics in the instruction itself, so the same fold becomes unconditional. So guard or deopt will not be needed.

And the compile-time fold works where a JIT does not. :slight_smile:

1 Like
11

The annotated thread has actual technical issues raised, it’s not an issue of style or not wanting to allow easier use.

There are also things we shouldn’t encourage to be used more than needed. I don’t think this is one of those, but if for example someone came along and proposed some shorter syntax for modifying globals/nonlocals, the objection on making something easier would be valid.

Pointing out that a tuple is almost always better than a frozenset for cases where it can be constant folded because of the overhead of hashing is also a technical consideration, not a style one. I don’t personally think it’s a strong enough one to turn into something we should be needing to actively consider if doing this would be steering people toward a worse option, there are cases frozensets work in that tuples do not.

Tying the annotated discussion to this isn’t helpful.

5 Likes
12

If that’s so, then you should be able to easily create some realistic sample code that is significantly easier to read and significantly easier to write correctly by using this feature compared to the function calls or just using mutable data structures and not mutating them.

Python has never been a language that lets object designers “protect” against malicious mutation. If that’s a feature you desperately need, then you really desperately need a different language. If you desperately need to convert Python into a different language, then at least be honest that that’s your goal.

The matrix multiplication proposal is one of the strongest examples to reach for. They had some great demonstrations of how the operator makes a drastic improvement for a range of code that has significant, though not majority, usage. Neither the PEP text nor this discussion have anything approaching that.

3 Likes
13

But it’s a question of balance. Concise new syntax is one of the main way things become much easier and widely adopted in PL; it’s also one of the hardest things to get approved on DPO because of the IMO disproportional opposition it causes. Of course people who don’t use one style or approach will find that encouraging that style is not needed, it’s understandable, but following that impulse to block improvements for other people is a worrying trend I’ve been observing here for quite a while. And sometimes it seems to me that small technical concerns get over-exaggerated just to block stuff they don’t need from getting in.

This is getting offtopic so I’ll drop it here.

14

This is needlessly hostile.

4 Likes
15

I agree with this, although I strongly disagree with the characterisation of the function calls as “clunky”.

I’m personally -0 on this proposal - I don’t think the benefits make it worth it, and I find the f{...} syntax a little weird. But I do think there’s a hidden point here, to encourage people to use frozen sets and dicts more often - and I think if that’s genuinely a goal of the PEP, it should be made explicit.

If it isn’t a goal to encourage more use, then I think having dedicated syntax for relatively infrequently used data types (frozendfict isn’t even available in a production version of Python yet!) is questionable. Why these types, and not Decimal, for example?

8 Likes
16

I think people should use immutable data structures more than they do. I don’t have any specific technical objection, and I don’t see an issue with promoting the use thereof, but I don’t particularly like the proposed syntax; I don’t have any use cases where I believe this would be a meaningful improvement. This syntax in particular reads as a downgrade over the explicit option currently available, and I strongly value readability over relatively small performance wins[1]

There’s also the empty frozenset issue mirroring the empty set issue, but the use case for an empty frozenset literal is small enough that it’s hardly worth notice.

  1. creating a constant frozen set in a tight loop isn’t a thing that one can really argue here, that would be a “fix the underlying code” issue. While the constant folding doesn’t have to worry about the name changing with the syntax, the JIT should be capable of working on things that the constant folding can’t. ↩︎

17

I should clarify: I’m saying I wouldn’t use it, but have no objection to the syntax existing that comes at the language level.

I do think this has some other social issues with the pervasive use of tools that push users to change working code just because there is new syntax, new feature, etc, not because the change solves a problem existing code had.

2 Likes
18

The only case where frozenset could be overridden without appearing in the symbol table should be import *.

There is at least one more case: module globals can be modified from outside the module. This is essentially what mock.patch("foo.bar") does. Therefore, optimizing the call form would always require some kind of runtime guard.

The global can also be replaced in several other ways within the module itself:

def hack(*args, **kwargs):
    return "hack"

globals()["frozendict"] = hack

def func():
    return frozendict(x=1)

print(func())  # print "hack"

Speaking of benefits, in what contexts would this be beneficial?

Here is a simple example:

def describe(status):
    return {404: "Not Found", 500: "Server Error"}.get(status)
    # main: 57.8 ns

    return frozendict({404: "Not Found", 500: "Server Error"}).get(status)
    # branch: 92.6 ns

    return f{404: "Not Found", 500: "Server Error"}.get(status)
    # branch: 21.0 ns

Surprisingly, frozendict is currently the slowest of the three. The call form creates a temporary mutable dictionary and then copies or converts it into a frozendict on every invocation. In other words, choosing immutability currently comes with a performance penalty.

Similar overhead may also appear in workloads we have not yet measured. Based on my experience optimizing frozendict across the specializing interpreter and JIT pipeline, frozen display syntax appears to be the simplest and most sustainable way to enable these optimizations.

Here is another benchmark using pyperf from @vstinner :

import pyperf

runner = pyperf.Runner()

runner.timeit(
    "frozendict type",
    setup="""
def func():
    return frozendict(a=1, b=2, c=3, d=4, e=5, f=6)
""",
    stmt="func()",
)

runner.timeit(
    "frozendict literal",
    setup="""
def func():
    return f{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6}
""",
    stmt="func()",
)

Results:

frozendict type:    Mean ± std dev: 236 ns ± 9 ns
frozendict literal: Mean ± std dev: 25.3 ns ± 2.0 ns

In this benchmark, the frozen display is approximately 9 times faster than the current constructor form.

9 Likes
19

This example looks like a case for improving inline dict dispatch-like use, not necessarily for new syntax for frozendicts. There should be no user percievable different in performance here between the dict and frozendict in theory.

5 Likes
20

I would go even further and say that’s an argument against the syntax. Do we want user’s cargo-culting this because one is currently better optimized? The use of a frozendict there isn’t obvious. The dict has no reason to be frozen other than the interpreter’s underlying optimizations.

3 Likes
21

I personally disagree with this argument. Python can still evolve and become safer over time.

When the Steering Council accepted PEP 814, it wrote:

“The absence of an immutable dict counterpart has been a long-standing gap in Python and has been requested for a long time in different forms. We agree this is a clear net positive for the language.”

I believe this reflects how Python can continue to change in response to users’ needs. No one claims that Python is a perfect language, but that does not mean we should say that it can never change.

For clarity, I did not participate in the Steering Council’s decision on PEP 814 because I was one of its authors.

9 Likes