Repository navigation
Speed up pattern matching via shared checks #158687
Description
Activity
Would that only be done with known "well-behaved" types? An object might match some pattern value at first but then change its mind and not match the same value again for the next pattern.
Would that only be done with known "well-behaved" types? An object might match some pattern value at first but then change its mind and not match the same value again for the next pattern.
I think the pattern matching PEP was fairly clear that objects should be "well-behaved" to allow this kind optimization ( see the "side effects and undefined behaviour" section of https://peps.python.org/pep-0634/#side-effects-and-undefined-behavior). Obviously it's been a while since then so the policy may have been reconsidered but this was certainly the original intent.
I think it's only guards that you have to be careful of because they're explicitly allowed to have side-effects. (This is mentioned in the issue already)
Reacted by Stefan Pochmann@pochmann The version I've been trying isn't limited to built-in types. You're right that this can change the result for an object that returns different answers on repeated comparisons or attribute reads.
@da-woods Yes, that's the part of the PEP I had in mind. PEP 634 leaves which methods get called, and how often, unspecified. It also explicitly allows caching sequence lengths. My reading is that this gives us room to share the common work for user-defined types too.
Guards still need to run in order, and later cases need to see any changes they make. I'm keeping guarded cases out of sharing in the version I've been testing. Tracing callbacks and the lifetime of temporary objects also need care, so I wouldn't say guards are the only thing to check.
Ah, right. The doc even says "Users should generally never rely on a pattern being evaluated. Depending on implementation, the interpreter may cache values or use other optimizations which skip repeated evaluations."
Reacted by Pablo Galindo Salgadofinishing a PR soon
Yep, I’ve been very interested in seeing this happen for a long time (see my first PyCon talk). I’ve tried from scratch about once a year, but most of the designs I came up with either (a) weren’t sufficiently general or (b) horribly complicated the bytecode compiler. It’s not very hard to make checks shared for certain top-level adjacent patterns, but trying to do it in a way that recurses into subpatterns and works for all compound patterns always turned into stack management hell IME (captures really complicated things too). Last time I tried was last summer or so.
Very excited to see what you’re cooking up here. And yes, the intended reading of the PEP is that any checks can be assumed to be side effect free, but the actual execution of any guard must act as an optimization barrier (i.e. all previously established info/captures must be discarded across failing guards).
Reacted by Stefan PochmannThanks @brandtbucher! The version I've been playing with keeps the existing pattern compiler, then shares the common start of the instructions generated for consecutive cases. That can include nested patterns, while the existing compiler still handles capture ordering and stores.
I'm treating every guarded case as a barrier and falling back when sharing would need too much stack space.
Does this sound like a reasonable first version, particularly finding the shared work in the generated instructions? It won't catch every opportunity, but the same approach works across sequences, mappings and classes.
Which nested patterns or capture combinations caused the most trouble in your attempts? I'd like to check those against this version before sending the PR.
Yep, probably I was letting perfect be the enemy of good in my earlier attempts. Trying to schedule an optimal instruction sequence is a much hairier problem than just threading jumps through common prefixes after-the-fact. It seems good enough and relatively straightforward to implement, and hopefully the way it’s implemented will turn things like this…
match color: case Color.RED: ... case Color.RED: ... case Color.GREEN: ... case Color.BLUE: ...
…into a single global load of
Color, three attribute accesses, and aSyntaxWarningfor the second case being unreachable.Not saying any implementation must work that way, but that was sort of one of several expected outcomes I was holding my own implementations to (without making it too brittle and value-pattern-specific, of course). Anecdotally, pattern matching is used this way quite a bit. :)
Separately, I would also hope that…
match color: case Color.RED if foo(): ... case Color.GREEN if bar(): ... case Color.BLUE if baz(): ...
…would only load
Coloronce if neither of thefoo()orbar()guards execute (although there would be 3 such loads statically present in the code for the failing-guard cases).On my phone, but IIRC stuff like this was where trying to to the “best” thing could quickly get hairy:
match foo: case [42]: ... case [42, *_]: ... case [*_, 42]: ...
Again, not a standard I would hold somebody else’s implementation to, just the sort of stuff I probably spent far too long thinking about. :)
I've been playing with ways to speed up pattern matching. When several cases have the same shape, we often repeat checks and lookups that already succeeded. I think we can do better here. For example:
Here, every case checks that
eventis a mapping and looks up the same two keys. If thetypevalue does not match, we do those checks and lookups again for the next case.The idea is to find consecutive cases that start with the same work and share that part. Once we have checked the mapping and read the values, we can keep them and try the different
typestrings in order. If one does not match, we move on to the next comparison without repeating the common work.The same idea applies to sequences with the same shape and class patterns that read the same attributes. We would still try cases in their original order and stop at the first match. We need to be careful with guards, since they can change what the next case sees.
This seems useful for longer matches where most cases only differ in a tag or a literal value. How much it helps would depend on which cases usually match and how much work they share.