bootstrap is slower on latest build.

[totaloutput]

with the latest changes at :https://github.com/soteria-dag/soterd/commit/2625c407441979b8d7c0045db75aff1e58cb96f6

the current bootstrap speed is slower than the previous version.. It use to be around couple thousand blocks for 5 minutes, now it's at about 500 blocks around the same time..

[colakong]

Why it's not as fast now

In looking at this, the main reason for the slow-down is that the mutation bug between phantom.OrderDAG and phantom.Graph.getVirtual when using an order-cache has been fixed; Sync is slower now because OrderDAG is doing work instead of skipping it.

Previously what would happen is:

1. OrderDAG called

2. Graph.getVirtual called on the dag's graph

3. getVirtual would return a copy of the graph, with a new node, VIRTUAL, added at the tip. So if you had:

   GENESIS <- A <- B

   it would now be:

   GENESIS <- A <- B <- VIRTUAL

4. Graph entries are pointers to nodes, so this new node entry would persist after OrderDAG returned, even though getVirtual was meant to be a temporary data structure.

5. If the height of the dag was tall enough, the node order and tips would be cached.

6. If the height of the dag is tall enough in subsequent calls to OrderDAG, a previous cached entry would be returned. The tips of the cache-entry would be processed first, so if it was our previous entry tip B would process in order: B, VIRTUAL.

7. The loop in OrderDAG works bottom-up (from GENESIS if there's no cache hit) and stops sorting when it sees VIRTUAL, so dag ordering would stop soon after it started and return. The returned order would be incomplete when using the order cache.

So no matter how many performance improvements we make, it'll never be quite as fast as it was before because the ordering work is being done now ^^.

Things we can do to optimize

1. For phantom.Node types, use map[*Node]struct{} for parents and children fields instead of *nodeSet.
   • Using a map is faster than a nodeSet, but it makes getAnticone less deterministic, because the order that the dag is processed when colouring is not going to be as consistent. This means that between runs of OrderDAG (like if soterd restarts) or between nodes, they may come up with slightly different orders.
   • I'd recommend that we drop this as an optimization
2. In Graph.getPast and Graph.getFuture, define our own nodeList type with push, shift, size methods, instead of using collections/list List types.
   • This looks like it's a little faster than the collections/list List type, because we can have nodeList methods not trigger as much garbage-collection.
3. Remove the Node.id comparison code from nodeSet, orderedNodeSet types.
   • This was put in place due to a bug where calculateBlueSet would cache each new VIRTUAL node that was created due to the getVirtual call in OrderDAG
   • Since that bug was taken care of (VIRTUAL nodes aren't ever cached in blueSet), this isn't useful anymore.
   • The string comparisons were slowing down the negative code-path of nodeSet.contains() calls
4. Create cache entries more frequently than every minOrderCacheDistance intervals, with a sliding-window for expiring old entries.

The remaining perf improvement that I could try is:

5. Memoize results of getPast and getFuture in an LRU cache

[colakong]

Implemented optimizations in 33933489942c9211b9b02de17b4f05bb57229d7c.

The increased cache usage increases memory consumption, up to ~2GiB. We can use disk to store results instead of memory, if we want to drop soterd memory requirements down from this point.