matrix-org / synapse

Synapse: Matrix homeserver written in Python/Twisted.
https://matrix-org.github.io/synapse
Apache License 2.0
11.82k stars 2.13k forks source link

Speed up persisting large number of outliers #16649

Closed erikjohnston closed 11 months ago

erikjohnston commented 11 months ago

Recalculating the roots tuple every iteration could be very expensive, so instead let's do a topological sort.

(Note that sorted_topologically_batched is basically a slightly modified sorted_topologically, and the tests are more or less a copy and paste)