search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 466 forks source link

Fix performance issue in OpSet.getMissingChanges #369

Closed ept closed 3 years ago

ept commented 3 years ago

@skokenes I think this fixes your issue #367. Could you give it a try please?

In a history with a lot of branching and merging, the slow path algorithm in OpSet.getMissingChanges would traverse a number of paths that grows exponentially in the length of the history. Ooops! Should have been O(n), was actually O(2^n). No wonder it would grind to a halt.

skokenes commented 3 years ago

Looks good to me!