This PR contain memory improvements to the following functions:
Acyclic
BFS
Bipartition
Components
Connected
EulerDirected
EulerUndirected
MST
ShortestPath
ShortestPaths
Sort
TopSort
Transpose
The technique to use less memory is equal in all the functions. I declared the closures (from g.Visit(v, closure)) outside the loop (related: #8), the result is the closure is allocated only one time and not allocated in each loop iteration.
I changed ShortestPath to stop when finding the target vertex.
I added the benchmark results in the testdata directory (it can be removed). The benchmarks were done in my machine with background processes running so the speed results aren't very reliable, but the memory results should be.
Obs: I didn't change the StrongComponents because it uses a recursive function, so the technique didn't fit well, and I didn't change MaxFlow because the improvement in memory was tiny.
Benchmark Results:
name old time/op new time/op delta
Acyclic-8 128µs ± 0% 66µs ± 0% -47.95%
name old alloc/op new alloc/op delta
Acyclic-8 52.0kB ± 0% 12.4kB ± 0% -76.18%
name old allocs/op new allocs/op delta
Acyclic-8 1.17k ± 0% 0.01k ± 0% -98.89%
name old time/op new time/op delta
BFS-8 269µs ± 0% 206µs ± 0% -23.36%
name old alloc/op new alloc/op delta
BFS-8 86.8kB ± 0% 23.2kB ± 0% -73.27%
name old allocs/op new allocs/op delta
BFS-8 1.01k ± 0% 0.02k ± 0% -98.33%
name old time/op new time/op delta
Bipartition-8 1.88µs ± 0% 1.40µs ± 0% -25.44%
name old alloc/op new alloc/op delta
Bipartition-8 3.62kB ± 0% 2.79kB ± 0% -22.79%
name old allocs/op new allocs/op delta
Bipartition-8 26.0 ± 0% 14.0 ± 0% -46.15%
name old time/op new time/op delta
Components-8 196µs ± 0% 149µs ± 0% -24.01%
name old alloc/op new alloc/op delta
Components-8 86.8kB ± 0% 54.8kB ± 0% -36.83%
name old allocs/op new allocs/op delta
Components-8 1.23k ± 0% 0.23k ± 0% -80.96%
name old time/op new time/op delta
Connected-8 151µs ± 0% 104µs ± 0% -31.26%
name old alloc/op new alloc/op delta
Connected-8 40.2kB ± 0% 8.3kB ± 0% -79.45%
name old allocs/op new allocs/op delta
Connected-8 1.00k ± 0% 0.01k ± 0% -99.50%
name old time/op new time/op delta
EulerDirected-8 7.28µs ± 0% 2.00µs ± 0% -72.44%
name old alloc/op new alloc/op delta
EulerDirected-8 5.71kB ± 0% 0.96kB ± 0% -83.19%
name old allocs/op new allocs/op delta
EulerDirected-8 103 ± 0% 4 ± 0% -96.12%
name old time/op new time/op delta
EulerUndirected-8 7.07µs ± 0% 2.39µs ± 0% -66.21%
name old alloc/op new alloc/op delta
EulerUndirected-8 5.72kB ± 0% 0.97kB ± 0% -83.08%
name old allocs/op new allocs/op delta
EulerUndirected-8 104 ± 0% 5 ± 0% -95.19%
name old time/op new time/op delta
MST-8 249µs ± 0% 190µs ± 0% -23.85%
name old alloc/op new alloc/op delta
MST-8 96.9kB ± 0% 33.0kB ± 0% -65.99%
name old allocs/op new allocs/op delta
MST-8 1.01k ± 0% 0.01k ± 0% -99.20%
name old time/op new time/op delta
ShortestPath-8 141µs ± 0% 60µs ± 0% -57.23%
name old alloc/op new alloc/op delta
ShortestPath-8 79.9kB ± 0% 39.8kB ± 0% -50.23%
name old allocs/op new allocs/op delta
ShortestPath-8 856 ± 0% 21 ± 0% -97.55%
name old time/op new time/op delta
ShortestPaths-8 121µs ± 0% 80µs ± 0% -34.06%
name old alloc/op new alloc/op delta
ShortestPaths-8 79.2kB ± 0% 39.7kB ± 0% -49.85%
name old allocs/op new allocs/op delta
ShortestPaths-8 841 ± 0% 19 ± 0% -97.74%
name old time/op new time/op delta
Sort-8 608µs ± 0% 500µs ± 0% -17.79%
name old alloc/op new alloc/op delta
Sort-8 249kB ± 0% 201kB ± 0% -19.25%
name old allocs/op new allocs/op delta
Sort-8 6.03k ± 0% 5.03k ± 0% -16.57%
name old time/op new time/op delta
TopSort-8 135µs ± 0% 69µs ± 0% -48.49%
name old alloc/op new alloc/op delta
TopSort-8 56.1kB ± 0% 16.5kB ± 0% -70.62%
name old allocs/op new allocs/op delta
TopSort-8 1.18k ± 0% 0.02k ± 0% -98.14%
name old time/op new time/op delta
Transpose-8 404µs ± 0% 401µs ± 0% -0.72%
name old alloc/op new alloc/op delta
Transpose-8 218kB ± 0% 170kB ± 0% -22.04%
name old allocs/op new allocs/op delta
Transpose-8 5.00k ± 0% 4.00k ± 0% -19.98%
This PR contain memory improvements to the following functions:
The technique to use less memory is equal in all the functions. I declared the closures (from g.Visit(v, closure)) outside the loop (related: #8), the result is the closure is allocated only one time and not allocated in each loop iteration.
I changed ShortestPath to stop when finding the target vertex.
I added the benchmark results in the testdata directory (it can be removed). The benchmarks were done in my machine with background processes running so the speed results aren't very reliable, but the memory results should be.
Obs: I didn't change the StrongComponents because it uses a recursive function, so the technique didn't fit well, and I didn't change MaxFlow because the improvement in memory was tiny.
Benchmark Results: