Speed up fetching device lists changes in sync.

[erikjohnston]

Currently we copy users_who_share_room needlessly about three times,
which is expensive when the set is large (which it can easily be).

This is based off a commit that is common to develop and matrix-org-hotfixes

[erikjohnston]

I've checked all the callers and this matches their types fwiw

[clokep]

https://wiki.python.org/moin/TimeComplexity#set has some stuff to say about this:

Average case: O(min(len(s), len(t))
Worst case: O(len(s) * len(t))

replace "min" with "max" if t is not a set

[erikjohnston]

Well that is interesting, I did:

In [1]: from synapse.util.stringutils import random_string                                                                                                                                                         

In [2]:                                                                                                                                                                                                            

In [2]: a = [random_string(10) for _ in range(10000)]                                                                                                                                                              

In [3]: b = [random_string(10) for _ in range(10)]                                                                                                                                                                 

In [4]: %timeit set(a).intersection(b)                                                                                                                                                                             
299 µs ± 3.41 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit set(b).intersection(a)                                                                                                                                                                             
141 µs ± 9.19 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

I'm slightly surprised that they're symmetric when t is not a set

(I'm going to wait for you to point out my embarrassing typo now....)

[clokep]

This looks sane to me. The only thing I can think of is that this is partially bound by the creation of the set() and not by the intersction code.

[erikjohnston]

Ah, that'd make sense if they ignored the time requirements for creating the set s

[clokep]

Right, so it'd be interesting to see:

>>> sa = set(a)
>>> sb = set(b)
>>> %timeit sa.intersection(b)
>>> %timeit sb.intersection(a)

[clokep]

I looked at this a bit more and I think your conclusion is sane, but the gist of my exploration is that converting things to sets is expensive. 👍