Speed up pattern matching via shared checks

[pablogsal]

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:

match event:
    case {"type": "start", "value": value}: ...
    case {"type": "stop", "value": value}: ...
    case {"type": "pause", "value": value}: ...
    case {"type": "resume", "value": value}: ...

Here, every case checks that event is a mapping and looks up the same two keys. If the type value 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 type strings 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.

[pochmann]

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.

[da-woods]

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)

[pablogsal]

@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.

[pochmann]

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."

[pablogsal]

finishing a PR soon

[pablogsal]

CC @Fidget-Spinner @brandtbucher

[brandtbucher]

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).

[pablogsal]

Thanks @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.