Skip to content

TopoSort: Count unvisited ancestor instead of BitVector of 'visited' status

vlorentz requested to merge vlorentz/swh-graph:next-mr into master

This is much more performant on the dir layer: it only takes 27 hours on swh1.enst.fr instead of an ETA of one or two years, most of it spent on this particular line:

LazyLongIterator successorAncestors = graph.successors(successorNodeId);

even when replacing all the code that used successorAncestors, it was still the major cause of the huge expected runtime.

Merge request reports