concrete.Graph edge representation: consider reducing memory load

[gonum]

concrete.Graph edge representation: consider reducing memory load

[UserAB1236872]

The graph generates Neighbors(n) by grabbing all keys in g.neighbors[n.ID()]. That's probably why it broke Dijkstra.

[kortschak]

Yes. That fixes it. I have a working version, but I'd like to do benchmarking on it to see whether the downsides are too much.

[kortschak]

I have done benchmarking now on the two most relevant methods, and the upshot is that if memory is not limiting then the current situation should be kept (quoted because the tests require substantial memory to run - >10GB for the current code):

benchmark                        old ns/op    new ns/op    delta
BenchmarkNeighbours1e4div1e2         19359      1241667  +6313.90%
BenchmarkNeighbours1e2div1e1          1629         8686  +433.21%
BenchmarkNeighbours1e3div1e1         16628       105654  +535.40%
BenchmarkNeighbours1e4div1e1        162591      1379850  +748.66%
BenchmarkNeighbours1e2div5e1         12413        19218  +54.82%
BenchmarkNeighbours1e3div5e1         64127       154844  +141.46%
BenchmarkNeighbours1e4div5e1        641413      1914623  +198.50%
BenchmarkEdgeBetween1e4div1e2          514          404  -21.40%
BenchmarkEdgeBetween1e2div1e1          942          815  -13.48%
BenchmarkEdgeBetween1e3div1e1          420          364  -13.33%
BenchmarkEdgeBetween1e4div1e1          518          715  +38.03%
BenchmarkEdgeBetween1e2div5e1          702          631  -10.11%
BenchmarkEdgeBetween1e3div5e1          486          416  -14.40%
BenchmarkEdgeBetween1e4div5e1          519          471   -9.25%

benchmark                       old allocs   new allocs    delta
BenchmarkNeighbours1e4div1e2             1            1    0.00%
BenchmarkNeighbours1e2div1e1             1            1    0.00%
BenchmarkNeighbours1e3div1e1             1            1    0.00%
BenchmarkNeighbours1e4div1e1             1            1    0.00%
BenchmarkNeighbours1e2div5e1             1            1    0.00%
BenchmarkNeighbours1e3div5e1             1            1    0.00%
BenchmarkNeighbours1e4div5e1             1            2  100.00%
BenchmarkEdgeBetween1e4div1e2            1            1    0.00%
BenchmarkEdgeBetween1e2div1e1            1            1    0.00%
BenchmarkEdgeBetween1e3div1e1            1            1    0.00%
BenchmarkEdgeBetween1e4div1e1            1            1    0.00%
BenchmarkEdgeBetween1e2div5e1            1            1    0.00%
BenchmarkEdgeBetween1e3div5e1            1            1    0.00%
BenchmarkEdgeBetween1e4div5e1            1            1    0.00%

benchmark                        old bytes    new bytes    delta
BenchmarkNeighbours1e4div1e2          3341         3090   -7.51%
BenchmarkNeighbours1e2div1e1           245          260    6.12%
BenchmarkNeighbours1e3div1e1          3091         3091    0.00%
BenchmarkNeighbours1e4div1e1         32844        32838   -0.02%
BenchmarkNeighbours1e2div5e1          1417         1417    0.00%
BenchmarkNeighbours1e3div5e1         12367        12366   -0.01%
BenchmarkNeighbours1e4div5e1        122880       274432  123.33%
BenchmarkEdgeBetween1e4div1e2           32           32    0.00%
BenchmarkEdgeBetween1e2div1e1           32           32    0.00%
BenchmarkEdgeBetween1e3div1e1           32           32    0.00%
BenchmarkEdgeBetween1e4div1e1           32           32    0.00%
BenchmarkEdgeBetween1e2div5e1           32           32    0.00%
BenchmarkEdgeBetween1e3div5e1           32           32    0.00%
BenchmarkEdgeBetween1e4div5e1           32           32    0.00%

The code for the bench (which should probably get included in the repo at some stage - preferably sooner; I'll file an issue for discussion to determine a minimum set of tests for each of the concrete types) is here and the changes I was using are here (I think there are some optimisations in that that should go in, to reduce interface method calls, but that can happen later).