Repository navigation
Topological sort has a significant performance penalty #170
Description
I'm using a Graph of type graph.Graph[Resource, Resource] with a hash function that returns the original pointer to build a directed, acylic resource graph. Due to the nature of current implementation, each graph node contains exactly one edge to its parent resource, all the way to a root node.
With 4043 total resources (so v=4043, e=4042 as the root node does not connect to any parent), running inside a Docker on a M2 Pro mac, a Topological Sort using graph.TopologicalSort takes >1.5s (1.876445292s as a typical value), with a significant memory usage of >200M. Upon profiling the heap with pprof, the following is yield:
Memory snapshot for a single request that requires Topological Sorting:
$ go tool pprof mem.pprof
flat flat% sum% cum cum%
332.92MB 96.06% 96.06% 336.85MB 97.19% github.com/dominikbraun/graph.TopologicalSort[go.shape.struct { Domain string; Instance int64 },go.shape.struct { Domain string; Instance int64 }]
I thought the excessive memory usage might have been caused by the fact that I'm using a struct and basically no hashing (which is, of course, more memory intensive); so I changed to graph.Graph[*Resource, *Resource]. While the below snapshot did not capture the exact memory usage at the moment, the memory allocation from the start of the program after a few request is:
$ go tool pprof --alloc_space mem.pprof
> top1
flat flat% sum% cum cum%
339.98GB 87.45% 87.45% 342.07GB 87.99% github.com/dominikbraun/graph.TopologicalSort[go.shape.*go.shape.struct { Domain string; Instance int64 },go.shape.*uint8]
...well exceeding 300GB.
Meanwhile, a naive implementation by keeping track of inEdgesCount for each vertex (using adjacentMap provided by graph) takes <20ms, with negligible memory footprint.
Using graph (as "github.com/dominikbraun/graph") v0.23.0.
Activity
dominikbraun commentedon Mar 8, 2024
Thanks for reporting this!
bersace commentedon Apr 16, 2025
I confirm this.
Topological sort is actually the feature I want from graph.
How to help ?