some basic dag optimizations #23811
some basic dag optimizations #23811
Conversation
ghost
added
the
sdkv1
|
Added a fairly coarse benchmark, comprised of the 2 most expensive operations usually done by core -- find all node dependencies, and reduce the graph. While not perfect, it provides some numbers to start with. |
| s := new(Set) | ||
| start := AsVertexList(g.DownEdges(v)) | ||
| func (g *AcyclicGraph) Ancestors(v Vertex) (Set, error) { | ||
| s := make(Set) |
There was a problem hiding this comment.
Go question -- make is for "type slice, map, or chan (only)" https://golang.org/pkg/builtin/#make. Why is this okay to use the dag package's Set type here?
There was a problem hiding this comment.
The underlying type of Set is map[interface{}]interface{}, so it is equivalent to calling Set(make(map[interface{}]interface{})). The same can be done with named slice and chan types (though the latter would be pretty unusual).
| @@ -335,6 +335,63 @@ func TestAcyclicGraphWalk_error(t *testing.T) { | |||
|
|
|||
| } | |||
|
|
|||
| func BenchmarkDAG(b *testing.B) { | |||
This allows iteration directly over the set, removing the need to allocate and copy a new slice for every iteration.
Since the set can be iterated over directly, we no longer need to copy the values into a new slice.
Make the default walks always use the sets directly, which avoids repeated copying of every set into a new slice.
Remove the abandoned graph debugger
Also removing unnecessary uses of the Set.List
There's no need for the json2dot command since we can't create json debug graphs.
|
I'm going to lock this issue because it has been closed for 30 days ⏳. This helps our maintainers find and focus on the active issues. If you have found a problem that seems similar to this, please open a new issue and complete the issue template so we can capture all the details necessary to investigate further. |
This removes a massive amount of unnecessary allocations from the graph operations. The graph is based on set data structures, and every time a set was iterated over (which is needed for most any graph operation) a new slice was allocated, and the set elements were copied into the slice.
The fundamental change here is making the
dag.Settype a simple map, so that it can be iterated over directly, and passed between functions without first converting it to a slice. This also allows us to continue to use the same basic graph data structures, without overhauling everything to a new interface that would be required for a more efficient or safer dag design.A rough benchmark from the CLI using a config with 400 dependent instances that takes 2m54s to build the apply graph before this change only takes 11s after the change with 1/2 the memory allocation (and much less pressure on GC).