Possible easy performance improvement: tuple/list literals -> set literals

[joepie91]

Description

In many places in the Synapse code, some variation of the following code exists:

if foo in ("bar", "baz", "qux"):
# ... or ...
if foo in ["bar", "baz", "qux"]:
# ... or ...
STUFF = ["bar", "baz", "qux"]
if foo in STUFF:

These use tuple and list literals respectively, while the resulting tuples/lists are only ever used for presence checking of particular entries. Some quick microbenchmarking suggested, however, that set literals would be significantly faster here (relatively speaking), for both hits and misses:

$ python3 -m timeit '"nyet" in { "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }'
10000000 loops, best of 5: 21.8 nsec per loop
$ python3 -m timeit '"baz" in { "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }'
20000000 loops, best of 5: 18.1 nsec per loop

$ python3 -m timeit '"nyet" in [ "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 ]'
1000000 loops, best of 5: 276 nsec per loop
$ python3 -m timeit '"baz" in [ "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 ]'
5000000 loops, best of 5: 54 nsec per loop

$ python3 -m timeit '"nyet" in ( "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 )'
1000000 loops, best of 5: 264 nsec per loop
$ python3 -m timeit '"baz" in ( "foo", "bar", "baz", 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 )'
5000000 loops, best of 5: 53.8 nsec per loop

Even for very small collections:

$ python3 -m timeit '"bar" in { "foo", "bar" }'
20000000 loops, best of 5: 18.6 nsec per loop
$ python3 -m timeit '"bar" in [ "foo", "bar" ]'
10000000 loops, best of 5: 35.6 nsec per loop
$ python3 -m timeit '"bar" in ( "foo", "bar" )'
10000000 loops, best of 5: 36.1 nsec per loop

... pretty much only being slower - and even then, only marginally slower - when literally the first element in the collection is a hit:

$ python3 -m timeit '"foo" in { "foo", "bar" }'
20000000 loops, best of 5: 17.8 nsec per loop
$ python3 -m timeit '"foo" in [ "foo", "bar" ]'
20000000 loops, best of 5: 13.9 nsec per loop
$ python3 -m timeit '"foo" in ( "foo", "bar" )'
20000000 loops, best of 5: 14.8 nsec per loop

While I have not analyzed it in detail, I strongly suspect that at least some of these checks are in a hot path, where they could provide a significant performance improvement - and I expect that blindly changing all non-iterated list/tuple literals to set literals across the codebase, could provide a significant performance improvement with very little work.

It appears that the performance benefit comes from list/tuple literals with constant values being compiled to tuples, whereas set literals with constant values are compiled to frozensets, paying the entire set-building cost at compile time while incurring no runtime overhead.

Steps to reproduce

N/A

Version information

Current develop HEAD.

[clokep]

I suspect that there's no reason not to use set literals in those places (even if they're iterated over for some reason, a set is still an iterable). Any interest in preparing a PR or two?

[joepie91]

I'm unfortunately totally not set up to develop on Synapse; this discovery was the result of an idle browse through the code, and I don't expect to have the time any time soon to get things set up properly for testing and measuring the changes (especially as I use NixOS, which tends to make it a bit more work to get non-Nix development environments going).

So I could prepare a PR, but it will probably take a while before I get around to it, and it looks like a relatively fast change for someone who already has a functioning testing/measuring environment set up anyway :)

even if they're iterated over for some reason, a set is still an iterable

While true, it's possible that an internal conversion back to a sequence has a higher runtime cost than is being gained by improving lookup performance. I don't really do Python, so I have no idea how this is implemented internally. The performance differences here are individually measured in nanoseconds, so it's not impossible for such a normally-insignificant difference to make things worse in this particular situation.

[clokep]

I'm unfortunately totally not set up to develop on Synapse; this discovery was the result of an idle browse through the code

I looked briefly and only found a couple of instances. Curious what parts you had in mind?

[joepie91]

There are quite a few cases (too many to list here) where there's an existence lookup in a literal that's specified either a) directly in the if...in statement, or b) defined as a constant first.

This is the regex I used to find them: if [a-z_]+ (?:not )?in [^\[(]

I haven't looked through the entire resultset, but I've gone through probably 40-50 results, and most of them are either a dict lookup or a list/tuple presence check. I've been using the Python extension for VS Code to identify and discard many of the dict checks (through its type inference).

[clokep]

One downside of this approach is that it has the potential to raise a TypeError, e.g.

>>> x = []
>>> x in ("foo", "bar")
False
>>> x in {"foo", "bar"}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

So a better microbenchmark might compare x in ("foo", "bar") to isinstance(x, str) and x in {"foo", "bar"}, at least for any place where we're looking at message contents this would need to be done.

[ShadowJonathan]

@clokep once #8351 is passed, maybe that could not be a problem anymore?

[clokep]

@clokep once #8351 is passed, maybe that could not be a problem anymore?

This doesn't really have to do with type annotations. There's quite a few places where we check user input against a list of constants to ensure it is valid. If the user input is not validated first it can be a non-hashable type, which raises an error. I have a WIP branch that adds some workarounds for that though.

[ShadowJonathan]

It does have to do with type annotations and validation, once type annotations have been set in place, static analysis can root out the bugs that eventually could cause that situation you described (TypeError), once you know the types of all parameters and variables, its easy to validate this before such a TypeError bug can ever take place.

While mypy does not seem to be able to validate this statically (python/mypy#2455) at the moment, I think revisiting this after having annotated every possible type could help a lot when going over the code while being able to know every type that'll visit that in set() operation, if that developer knows what hashable types are.

If possible, I'd be willing to do this after annotations and checking is in place.

P.S: If a developer has to do isinstance(obj, str) as insurance against wild unknown types, that to me is a sign that no actual validation or checking at all internally is taking place, which means that is the bigger problem.

[clokep]

It does have to do with type annotations and validation, once type annotations have been set in place, static analysis can root out the bugs that eventually could cause that situation you described (TypeError), once you know the types of all parameters and variables, its easy to validate this before such a TypeError bug can ever take place.

I disagree. You don't know the incoming types of JSON data against APIs.

P.S: If a developer has to do isinstance(obj, str) as insurance against wild unknown types, that to me is a sign that no actual validation or checking at all internally is taking place, which means that is the bigger problem.

I agree, but it is the reality right now.

[ShadowJonathan]

I disagree. You don't know the incoming types of JSON data against APIs.

Then that JSON should be checked against specification when received, before being passed through for processing. If it's an actual variant type that's allowed by spec, then a isinstance check should take place, but only in a branching fashion (or similar) (if isinstance(json["variant_key"], list): handle_list(json); else: handle_other_type(json))

[clokep]

I disagree. You don't know the incoming types of JSON data against APIs.

Then that JSON should be checked against specification when received, before being passed through for processing. If it's an actual variant type that's allowed by spec, then a isinstance check should take place, but only in a branching fashion (or similar) (if isinstance(json["variant_key"], list): handle_list(json); else: handle_other_type(json))

We're saying the same thing. My point is that until that is done, this issue is harder to fix.

[joepie91]

We're saying the same thing. My point is that until that is done, this issue is harder to fix.

Is there a tracking issue for the validation work that this depends on?

[ShadowJonathan]

We're saying the same thing. My point is that until that is done, this issue is harder to fix.

Is there a tracking issue for the validation work that this depends on?

I mentioned #8351, but that doesn't inherently fix the JSON spec validation side of it.

[richvdh]

This doesn't feel terribly actionable. We'd welcome PRs improve performance in this way, but I don't think it's a wholesale project we are likely to schedule.