Add back fast path for non-gappy syncs

[erikjohnston]

PR #16942 removed an invalid optimisation that avoided pulling out state for non-gappy syncs. This causes a large increase in DB usage. c.f. #16941 for why that optimisation was wrong.

However, we can still optimise in the simple case where the events in the timeline are a linear chain without any branching/merging of the DAG.

cc. @richvdh

[richvdh]

have you considered how this behaves in longer-lived forks:

             E1
           ↗    ↖
          |      S2
          |      ↑
          E3     |
          ↑      |
        --|------|----   <- prev sync
          |      |
          E4     E5       
          ↑      |
        --|------|----   <- this sync
          |      |
           ↖    /
             E6                (the distant future)

E4 and E5 both have single prev events, but I'm not convinced it is safe to drop the state delta between the forks here?

[erikjohnston]

The state returned is currently (timeline_start | timeline_end) - previous_timeline_end - timeline_contains. If we have a linear chain with no gaps, my assumption is that timeline_start == previous_timeline_end and timeline_end == timeline_start + timeline_contains, which then all cancels out.

But bleurghghghghghg you're right that we need to actually check that all the events are in the same chain and point to the previous timeline end. BLEURGH.

(Though does the current code sensibly work in this case?)

[richvdh]

(Though does the current code sensibly work in this case?)

WHO KNOWS

[richvdh]

More constructively: it would be good to add a test for this case.

[erikjohnston]

Having thought about this over lunch:

If we have a linear chain with no gaps, my assumption is that timeline_start == previous_timeline_end

I think with long lived forks this may or may not be true, depending on if the the end and start are part of the same fork. In the present code, we'll come to the wrong answer if that is the case, and in the new code it will come to the wrong answer either way.

Given that, I'm somewhat tempted to take accept that and fix the performance regression. The other option is to do an extra DB hit to check if the event ID corresponding to previous_timeline_end matches the prev event of the start of the timeline.

I think if we want to remove all these edge cases we'll need to change all this to try and use the current state (based on the extremities at the time), though that's quite a big change (but perhaps we can do it for sliding sync?)

[anoadragon453]

Looks to optimise for the linear case.