Specialized match_keys for exact dictionary type

Feature or enhancement

I think it's probably worthwhile to write a specialized version of match_keys (for structural pattern matching of mappings) for exact dictionary types

Pitch

The most common mapping type is almost certainly the built-in dict. The match_keys function in ceval.c could be specialized to handle this type. Doing so would allow you to skip the dummy object, and replace the get call with PyDict_GetItemWithError. I don't think this should change the observable behaviour at all for exact dict

I'm in the process of reimplementing structural pattern matching on Cython, and this change gives ~2x optimization of some microbenchmarks.

If this change is deemed desirable I'm happy to implement it myself.

Previous discussion

Not aware of any

What you mean is something like

if(PyDIct_CheckExact(o)) {
    PyDIct_GetItemWIthError(o, key)
}
else {
// The current code goes here
}

right? (Whenever I see the word "specialize" now I immediately think of PEP 659, so I wanted to clear that up).

Link to the current match_keys function just to make it easier to discuss:

cpython/Python/ceval.c

Line 912 in 4c496f1

match_keys(PyThreadState *tstate, PyObject *map, PyObject *keys)

I was thinking of having a second copy of the function that operates on dicts. So match_keys starts something like:

if (PyDict_CheckExact(map)) {
    return match_keys_dict(tstate, map, keys);
}

and match_keys_dict then uses PyDIct_GetItemWIthError(o, key) instead of calling mapping.get.

And no - I wasn't proposing anything like PEP 659 - just an if statement to pick a slightly faster implementation

@brandtbucher

In theory this seems sound to me and I'm +1. But I'll wait to hear what @brandtbucher has to say.

@tonybaloney

I actually discovered during a PyCon all-nighter (thanks to some nerd-sniping by @tonybaloney) that we can get a huge speedup for mapping patterns by moving this logic into the bytecode and:

removing the length check
using CONTAINS_OP and BINARY_SUBSCR instead of two-argument get
not building a set to check for duplicate keys if they’re all known statically (common case)
some other tidying up

As a bonus, with this scheme we get dictionary specialization for free, since the logic is being moved “into Python code”.

My plan is to make this change in 3.12. I have a branch with the work, just haven’t gotten around to cleaning it up and opening a PR yet. 😬

I’d be okay merging a PR that does what you describe now since it’s always better to make things faster. But just know that there’s a pretty good chance it could get completely ripped out and replaced before 3.12 is released, haha.

Unfortunately it’s documented that get has to be used, to prevent defaultdict’s behaviour from being triggered.

Indeed, that’s the main sticking point. Although I'm pretty confident that it won't be much of an issue because:

We already require the Mapping interface, which includes containment and subscription
Checking for containment before subscription still avoids creating new keys in defaultdicts, which is the main reason why we went with 2-argument get in the first place

Thanks for the comments.

Give that it's a fairly easy change I'll submit a PR with it, in the hope/expectation that it gets dropped when you finalize moving the logic into bytecode. If nothing else it'll help if the move away from get proves to be a real sticking point.

not building a set to check for duplicate keys if they’re all known statically (common case)

I'd already spotted that as a worthwhile optimization for the Cython implementation of structural pattern matching. It wasn't so obvious that this'd be an easy change to the implementation here.

PR in #93752

@brandtbucher

@brandtbucher one further comment

using CONTAINS_OP and BINARY_SUBSCR instead of two-argument get

You could also drop the BINARY_SUBSCR for irrefutable and targetless patterns. (You'd probably already got that, but I thought it worth mentioning just in case)

Navigation Menu

Repository navigation

Specialized `match_keys` for exact dictionary type #93714

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Specialized match_keys for exact dictionary type #93714

Description

Activity

Fidget-Spinner commented on Jun 11, 2022

da-woods commented on Jun 11, 2022

Fidget-Spinner commented on Jun 11, 2022

brandtbucher commented on Jun 12, 2022

TeamSpen210 commented on Jun 12, 2022

brandtbucher commented on Jun 12, 2022

da-woods commented on Jun 12, 2022

da-woods commented on Jun 12, 2022

da-woods commented on Jun 13, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

Specialized `match_keys` for exact dictionary type #93714