Copying large digraphs is slow

[james-d-mitchell]

While working on something, @mariatsalakou and I noticed:

gap> D := CycleDigraph(10 * 10 ^ 6);
<immutable cycle digraph with 10000000 vertices>
gap> time;
3268
gap> D := DigraphCopy(D);
<immutable digraph with 10000000 vertices, 10000000 edges>
gap> time;
20714

which is surprisingly slow...

[wilfwilson]

gap> D := CycleDigraph(10 * 10 ^ 6);; time;
910

DigraphCopy in this instance is doing DigraphImmutableCopy, which does the following three things:

gap> copy := ConvertToImmutableDigraphNC( OutNeighboursMutableCopy( D ) );; time;
1072
gap> SetDigraphVertexLabels( copy, StructuralCopy( DigraphVertexLabels( D ) ) );; time;
2
gap> SetDigraphEdgeLabelsNC( copy, StructuralCopy( DigraphEdgeLabelsNC( D ) ) );; time;
5090

which we can verify sums up to about the same time that DigraphCopy takes:

gap> D := CycleDigraph(10 * 10 ^ 6);; DigraphCopy(D);; time;
6462

What is the expensive part of this? It's dealing with the edge labels, especially creating the edge labels of the cycle digraph (which are otherwise unset):

gap> D := CycleDigraph(10 * 10 ^ 6);;
gap> el := DigraphEdgeLabelsNC(D);; time;
4276
gap> el := StructuralCopy(el);; time;
418

Perhaps we need some way of a digraph knowing whether its edge labels have ever been set, or if they're just the default. That way, when doing copy operations (or other operations that preserve the edge labels), then we can simply not do anything.

[james-d-mitchell]

Nice analysis. Yes, we should play with the edge labels code, and try to improve this. Important question: how is your computer 3 times faster than mine??

[wilfwilson]

Maybe I don't have a million browser tabs open in the background?? 😉 No idea though, because I think our computers are roughly the same model.

[james-d-mitchell]

Resolved in v1.4.0