ipfs-shipyard / peer-crdt

Peer CRDT
MIT License
60 stars 8 forks source link

Reduce `_isChildOf` run time cost #8

Closed legastero closed 6 years ago

legastero commented 6 years ago

I conducted tests where three peers were randomly picked to apply a set of 500 or 1000 changes.

Using this patch, it took:

Without this patch, it took:

The original code has two issues:

  1. Does not stop processing once an answer is found.
  2. Does not remember which nodes have been checked.

In a DAG that has many forks and merges, such as this test, those two conditions meant that an extreme amount of time was spent repeatedly searching the tree for a target node that was already found.