Skip to content

Fix memory usage estimate of TopoSort

vlorentz requested to merge vlorentz/swh-graph:toposort into master

I underestimated the memory needed to run the toposort because I had only skimmed the code.

In particular, it assumed arrays used as many nodes as the subgraph made of only the selected object types; but actually the array needs one cell for each node id; and was missing space for the 'unvisited' array.

As fixing this makes the memory usage considerably higher, this commit also includes a finer estimate of the size of the 'ready' set.

This was tested by fully running the toposort on the 'ori,snp,rel,rev,dir' subgraph.

Merge request reports

Loading