[New-bugs-announce] [issue44283] Add jump table for certain safe match-case statements

[Dennis Sweeney]

New submission from Dennis Sweeney <sweeney.dennis650 at gmail.com>:

Anecdotally, a few people I've talked to have expected that match-case statements would improve performance in the same way that switch-cases sometimes do in C-like languages. While this is impossible in general without changing semantics (since, for example, __eq__ can have side effects), it would be nice if a jump table was implemented in certain safe cases.

My idea was to implement this whenever the list of cases begins with 2 or more of the following in a row:

    (1) ints
    (2) strings
    (3) None
    (4) OR (`|`) patterns of any of the above
    (5?) potentially later add support for tuples

Example:

    match x:
        case 10:             # safe
            print("A")
        case 20:             # safe
            print("B")
        case 30 | 31:        # safe
            print("C")
        case 40:             # safe
            print("D")
        case MyClass(10, 20): # unsafe
            print("E")
        case []:              # unsafe
            print("F")
        case whatever:        # unsafe
            print("G")


This would compile to something like

    LOAD_FAST (x)
    LOAD_CONST 16            ({10: 16, 20: 38, 30: 80, 31: 80, 40: 102})
    ATTEMPT_SAFE_MATCH 110

    ... all the rest of the code is the same ...

Where the new opcode would be would be something like

case TARGET(ATTEMPT_SAFE_MATCH): {
    PyObject *jump_dict = POP();
    PyObject *x = TOP();
    
    if (PyLong_CheckExact(x) ||
        PyUnicode_CheckExact(x) ||
        Py_Is(x, Py_None))
    {
        PyObject *boxed = PyDict_GetItemWithError(jump_dict, x);
        Py_DECREF(jump_dict);
        if (res == NULL) {
            if (PyErr_Occurred()) {
                goto error;
            }
            else {
                JUMPBY(oparg);
            }
        }
        assert(PyLong_CheckExact(boxed));
        int target = (int)PyLong_AsLong(boxed);
        JUMPBY(target);
    }
    else {
        // fall back to general matching code
        Py_DECREF(jump_dict);
        DISPATCH();
    }
}

I can work on an implementation in the next couple of weeks.

----------
components: Interpreter Core
messages: 394874
nosy: Dennis Sweeney
priority: normal
severity: normal
status: open
title: Add jump table for certain safe match-case statements
type: performance
versions: Python 3.11

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44283>
_______________________________________