search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.48k stars 488 forks source link

Meta ticket: Simplify and speed up graph backends #28895

Open kliem opened 4 years ago

kliem commented 4 years ago

This ticket collects tickets simplifying and improving the graph backends.

It is motivated by the following post:

https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

Possibly related tickets:

Here are some timings we try to improve along the way:

sage: import itertools
sage: def test_speed(n):
....:     for struct in ('dense', 'sparse'):
....:         print("\nnow doing {}".format(struct))
....:         G = Graph(n, data_structure=struct)
....:         edges = itertools.combinations(range(n), 2)
....:         print("adding edges")
....:         %time G.add_edges(edges)
....:         print("copy to dense")
....:         %time _ = copy(G)
....:         print("copy to sparse")
....:         %time _ = G.copy(sparse=True)
....:         print("copy to statice sparse")
....:         %time H = G.copy(immutable=True)
....:         edges = itertools.combinations(range(n), 2)
....:         print("delete edges")
....:         %time G.delete_edges(edges)
....:     
....:         print("copying static sparse to {}".format(struct))
....:         %time _ = H.copy(data_structure=struct)
....:   
sage: test_speed(1000)

now doing dense
adding edges
CPU times: user 169 ms, sys: 4 µs, total: 169 ms
Wall time: 169 ms
copy to dense
CPU times: user 2.14 s, sys: 0 ns, total: 2.14 s
Wall time: 2.14 s
copy to sparse
CPU times: user 2.44 s, sys: 0 ns, total: 2.44 s
Wall time: 2.44 s
copy to statice sparse
CPU times: user 2.75 s, sys: 3.61 ms, total: 2.75 s
Wall time: 2.75 s
delete edges
CPU times: user 613 ms, sys: 0 ns, total: 613 ms
Wall time: 613 ms
copying static sparse to dense
CPU times: user 282 ms, sys: 0 ns, total: 282 ms
Wall time: 282 ms

now doing sparse
adding edges
CPU times: user 434 ms, sys: 0 ns, total: 434 ms
Wall time: 435 ms
copy to dense
CPU times: user 619 ms, sys: 0 ns, total: 619 ms
Wall time: 619 ms
copy to sparse
CPU times: user 747 ms, sys: 3.84 ms, total: 750 ms
Wall time: 750 ms
copy to statice sparse
CPU times: user 997 ms, sys: 0 ns, total: 997 ms
Wall time: 997 ms
delete edges
CPU times: user 896 ms, sys: 0 ns, total: 896 ms
Wall time: 896 ms
copying static sparse to sparse
CPU times: user 582 ms, sys: 0 ns, total: 582 ms
Wall time: 582 ms
sage: test_speed(2000)

now doing dense
adding edges
CPU times: user 672 ms, sys: 0 ns, total: 672 ms
Wall time: 671 ms
copy to dense
CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
Wall time: 16.1 s
copy to sparse
CPU times: user 17.4 s, sys: 34.7 ms, total: 17.5 s
Wall time: 17.5 s
copy to statice sparse
CPU times: user 18.9 s, sys: 51.6 ms, total: 18.9 s
Wall time: 18.9 s
delete edges
CPU times: user 2.49 s, sys: 0 ns, total: 2.49 s
Wall time: 2.49 s
copying static sparse to dense
CPU times: user 1.18 s, sys: 0 ns, total: 1.18 s
Wall time: 1.18 s

now doing sparse
adding edges
CPU times: user 1.87 s, sys: 0 ns, total: 1.87 s
Wall time: 1.87 s
copy to dense
CPU times: user 2.64 s, sys: 0 ns, total: 2.64 s
Wall time: 2.64 s
copy to sparse
CPU times: user 3.21 s, sys: 47.8 ms, total: 3.26 s
Wall time: 3.26 s
copy to statice sparse
CPU times: user 4.25 s, sys: 36 ms, total: 4.28 s
Wall time: 4.28 s
delete edges
CPU times: user 3.86 s, sys: 0 ns, total: 3.86 s
Wall time: 3.86 s
copying static sparse to sparse
CPU times: user 2.55 s, sys: 0 ns, total: 2.55 s
Wall time: 2.55 s

CC: @dcoudert @kliem

Component: graph theory

Keywords: backends

Issue created by migration from https://trac.sagemath.org/ticket/28895

kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -3,3 +3,5 @@
 It is motivated by the following post:

 https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ
+
+-  #28896: Graphs: Move common methods of backends to CGraph
kliem commented 4 years ago
comment:2

The idea is that in the end, most top level function should be handled in c_graph.pyx. If possible, only the low level functions are done separate for each backend.

Once things are unified (as good as different backends allow), one should speed up things. E.g. the following is extremely slow:

sage: import itertools
sage: def test_speed(n):
....:     G = Graph(n, data_structure='dense')
....:     edges = itertools.combinations(range(n), 2)
....:     %time G.add_edges(edges)
....:     edges = itertools.combinations(range(n), 2)
....:     %time G.delete_edges(edges)
sage: test_speed(1000)
CPU times: user 175 ms, sys: 8 µs, total: 175 ms
Wall time: 175 ms
CPU times: user 574 ms, sys: 0 ns, total: 574 ms
Wall time: 574 ms

I got both things down to about 80 ms by calling add_edges on the top level and then actually using the unsafe methods wherever possible (if we already obtained the indices safely, there should be nothing preventing as from using unsafe methods). Similar for delete_edges.

kliem commented 4 years ago
comment:3

Adding this, because I missed it on my first try to optimize add_edges. This would have created a mistake in BipartiteGraph without a doctest catching on.

kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -5,3 +5,4 @@
 https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

 -  #28896: Graphs: Move common methods of backends to CGraph 
+-  #28897: BipartiteGraph blindly trusts generic graphs
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -5,4 +5,117 @@
 https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

 -  #28896: Graphs: Move common methods of backends to CGraph 
--  #28897: BipartiteGraph blindly trusts generic graphs 
+-  #28897: BipartiteGraph blindly trusts generic graphs
+
+Here are some timings we try to improve along the way:
+
+```
+sage: def test_speed(n):
+....:     for struct in ('dense', 'sparse'):
+....:         print("\nnow doing {}".format(struct))
+....:         G = Graph(n, data_structure=struct)
+....:         edges = itertools.combinations(range(n), 2)
+....:         print("adding edges")
+....:         %time G.add_edges(edges)
+....:         print("copy to dense")
+....:         %time _ = copy(G)
+....:         print("copy to sparse")
+....:         %time _ = G.copy(sparse=True)
+....:         print("copy to statice sparse")
+....:         %time H = G.copy(immutable=True)
+....:         edges = itertools.combinations(range(n), 2)
+....:         print("delete edges")
+....:         %time G.delete_edges(edges)
+....:     
+....:         print("copying static sparse to {}".format(struct))
+....:         %time _ = H.copy(data_structure=struct)
+....:   
+```
+
+```
+sage: test_speed(1000)
+
+now doing dense
+adding edges
+CPU times: user 169 ms, sys: 4 µs, total: 169 ms
+Wall time: 169 ms
+copy to dense
+CPU times: user 2.14 s, sys: 0 ns, total: 2.14 s
+Wall time: 2.14 s
+copy to sparse
+CPU times: user 2.44 s, sys: 0 ns, total: 2.44 s
+Wall time: 2.44 s
+copy to statice sparse
+CPU times: user 2.75 s, sys: 3.61 ms, total: 2.75 s
+Wall time: 2.75 s
+delete edges
+CPU times: user 613 ms, sys: 0 ns, total: 613 ms
+Wall time: 613 ms
+copying static sparse to dense
+CPU times: user 282 ms, sys: 0 ns, total: 282 ms
+Wall time: 282 ms
+
+now doing sparse
+adding edges
+CPU times: user 434 ms, sys: 0 ns, total: 434 ms
+Wall time: 435 ms
+copy to dense
+CPU times: user 619 ms, sys: 0 ns, total: 619 ms
+Wall time: 619 ms
+copy to sparse
+CPU times: user 747 ms, sys: 3.84 ms, total: 750 ms
+Wall time: 750 ms
+copy to statice sparse
+CPU times: user 997 ms, sys: 0 ns, total: 997 ms
+Wall time: 997 ms
+delete edges
+CPU times: user 896 ms, sys: 0 ns, total: 896 ms
+Wall time: 896 ms
+copying static sparse to sparse
+CPU times: user 582 ms, sys: 0 ns, total: 582 ms
+Wall time: 582 ms
+```
+
+```
+sage: test_speed(2000)
+
+now doing dense
+adding edges
+CPU times: user 672 ms, sys: 0 ns, total: 672 ms
+Wall time: 671 ms
+copy to dense
+CPU times: user 16.1 s, sys: 0 ns, total: 16.1 s
+Wall time: 16.1 s
+copy to sparse
+CPU times: user 17.4 s, sys: 34.7 ms, total: 17.5 s
+Wall time: 17.5 s
+copy to statice sparse
+CPU times: user 18.9 s, sys: 51.6 ms, total: 18.9 s
+Wall time: 18.9 s
+delete edges
+CPU times: user 2.49 s, sys: 0 ns, total: 2.49 s
+Wall time: 2.49 s
+copying static sparse to dense
+CPU times: user 1.18 s, sys: 0 ns, total: 1.18 s
+Wall time: 1.18 s
+
+now doing sparse
+adding edges
+CPU times: user 1.87 s, sys: 0 ns, total: 1.87 s
+Wall time: 1.87 s
+copy to dense
+CPU times: user 2.64 s, sys: 0 ns, total: 2.64 s
+Wall time: 2.64 s
+copy to sparse
+CPU times: user 3.21 s, sys: 47.8 ms, total: 3.26 s
+Wall time: 3.26 s
+copy to statice sparse
+CPU times: user 4.25 s, sys: 36 ms, total: 4.28 s
+Wall time: 4.28 s
+delete edges
+CPU times: user 3.86 s, sys: 0 ns, total: 3.86 s
+Wall time: 3.86 s
+copying static sparse to sparse
+CPU times: user 2.55 s, sys: 0 ns, total: 2.55 s
+Wall time: 2.55 s
+```
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -4,8 +4,22 @@

 https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

+-  #7720: Digraph.reverse() should be rewritten more efficiently ( not hard ) 
+- #12387: Everything is not well with dense graph backends
+- #12540: Graph library passes almost surelly erroneous calls without an exception
+-  #28259: graph add_edges/delete_edges are dramatically slow 
 -  #28896: Graphs: Move common methods of backends to CGraph 
 -  #28897: BipartiteGraph blindly trusts generic graphs
+
+Possibly related tickets:
+
+- #6604: Polish the use of iterators in C graphs 
+- #9143: Speed up graph generation using Cython 
+- #9301: Modified check_edge_label in the sparse graph backend to consider equals the same objects rather than objects with the same contents
+- #22374: {c,sparse}_graph: systematically turn integer-like vertices into ints
+- #24989: G.edges_incident returns edges with vertices swapped
+- #25465: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
+- #28309: improvement of method allow_multiple_edges

 Here are some timings we try to improve along the way:
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -18,7 +18,7 @@
 - #9301: Modified check_edge_label in the sparse graph backend to consider equals the same objects rather than objects with the same contents
 - #22374: {c,sparse}_graph: systematically turn integer-like vertices into ints
 - #24989: G.edges_incident returns edges with vertices swapped
-- #25465: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
+- #25465, #28865: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
 - #28309: improvement of method allow_multiple_edges

 Here are some timings we try to improve along the way:
dcoudert commented 4 years ago
comment:6

just mentioned that #25465, #28865 are for the same issue.

kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -10,6 +10,7 @@
 -  #28259: graph add_edges/delete_edges are dramatically slow 
 -  #28896: Graphs: Move common methods of backends to CGraph 
 -  #28897: BipartiteGraph blindly trusts generic graphs
+-  #28904: Move reversed graph from backend to CGraph for sparse graphs 

 Possibly related tickets:
embray commented 4 years ago
comment:8

Ticket retargeted after milestone closed

mkoeppe commented 4 years ago
comment:9

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

dcoudert commented 4 years ago
comment:10

22349 could also be part of this task.

kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -7,6 +7,7 @@
 -  #7720: Digraph.reverse() should be rewritten more efficiently ( not hard ) 
 - #12387: Everything is not well with dense graph backends
 - #12540: Graph library passes almost surelly erroneous calls without an exception
+-  #22349: Deprecate sorting of Graph vertices and edges by default 
 -  #28259: graph add_edges/delete_edges are dramatically slow 
 -  #28896: Graphs: Move common methods of backends to CGraph 
 -  #28897: BipartiteGraph blindly trusts generic graphs
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -11,7 +11,8 @@
 -  #28259: graph add_edges/delete_edges are dramatically slow 
 -  #28896: Graphs: Move common methods of backends to CGraph 
 -  #28897: BipartiteGraph blindly trusts generic graphs
--  #28904: Move reversed graph from backend to CGraph for sparse graphs 
+-  #28904: Move reversed graph from backend to CGraph for sparse graphs
+-  use iterators for outgoing and ingoing arcs 

 Possibly related tickets:
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -12,7 +12,8 @@
 -  #28896: Graphs: Move common methods of backends to CGraph 
 -  #28897: BipartiteGraph blindly trusts generic graphs
 -  #28904: Move reversed graph from backend to CGraph for sparse graphs
--  use iterators for outgoing and ingoing arcs 
+-  #30641: equality of graphs is 60 times slower than equality of their list of edges 
+-  use iterators for outgoing and ingoing arcs

 Possibly related tickets:
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -7,13 +7,15 @@
 -  #7720: Digraph.reverse() should be rewritten more efficiently ( not hard ) 
 - #12387: Everything is not well with dense graph backends
 - #12540: Graph library passes almost surelly erroneous calls without an exception
--  #22349: Deprecate sorting of Graph vertices and edges by default 
--  #28259: graph add_edges/delete_edges are dramatically slow 
--  #28896: Graphs: Move common methods of backends to CGraph 
--  #28897: BipartiteGraph blindly trusts generic graphs
--  #28904: Move reversed graph from backend to CGraph for sparse graphs
--  #30641: equality of graphs is 60 times slower than equality of their list of edges 
--  use iterators for outgoing and ingoing arcs
+- #22349: Deprecate sorting of Graph vertices and edges by default 
+- #28259: graph add_edges/delete_edges are dramatically slow 
+- #28896: Graphs: Move common methods of backends to CGraph 
+- #28897: BipartiteGraph blindly trusts generic graphs
+- #28904: Move reversed graph from backend to CGraph for sparse graphs
+- #30641: equality of graphs is 60 times slower than equality of their list of edges 
+- #30769: Unify graph backends
+- #30753: Further improvements in method subgraph 
+- use iterators for outgoing and ingoing arcs

 Possibly related tickets:
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -30,6 +30,7 @@
 Here are some timings we try to improve along the way:

+sage: import itertools sage: def test_speed(n): ....: for struct in ('dense', 'sparse'): ....: print("\nnow doing {}".format(struct))

dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -13,6 +13,7 @@
 - #28897: BipartiteGraph blindly trusts generic graphs
 - #28904: Move reversed graph from backend to CGraph for sparse graphs
 - #30641: equality of graphs is 60 times slower than equality of their list of edges 
+- #30665: Optimize edge iterator for graphs
 - #30769: Unify graph backends
 - #30753: Further improvements in method subgraph 
 - use iterators for outgoing and ingoing arcs
kliem commented 4 years ago

Description changed:

--- 
+++ 
@@ -15,7 +15,8 @@
 - #30641: equality of graphs is 60 times slower than equality of their list of edges 
 - #30665: Optimize edge iterator for graphs
 - #30769: Unify graph backends
-- #30753: Further improvements in method subgraph 
+- #30753: Further improvements in method subgraph
+- #30777: Improve deleting of edges of graphs
 - use iterators for outgoing and ingoing arcs

 Possibly related tickets:
kliem commented 4 years ago
comment:19

With #30776 and #30777 things are looking much better:

sage: test_speed(1000)                                                                                                                                                                                                                                                                                                                                                     

now doing dense
adding edges
CPU times: user 81.9 ms, sys: 0 ns, total: 81.9 ms
Wall time: 81.9 ms
copy to dense
CPU times: user 10.2 ms, sys: 0 ns, total: 10.2 ms
Wall time: 10.2 ms
copy to sparse
CPU times: user 89.5 ms, sys: 7.87 ms, total: 97.4 ms
Wall time: 97.1 ms
copy to statice sparse
CPU times: user 423 ms, sys: 11.9 ms, total: 435 ms
Wall time: 435 ms
delete edges
CPU times: user 79.1 ms, sys: 0 ns, total: 79.1 ms
Wall time: 79.1 ms
copying static sparse to dense
CPU times: user 81.3 ms, sys: 51 µs, total: 81.4 ms
Wall time: 81.4 ms

now doing sparse
adding edges
CPU times: user 169 ms, sys: 0 ns, total: 169 ms
Wall time: 169 ms
copy to dense
CPU times: user 158 ms, sys: 0 ns, total: 158 ms
Wall time: 158 ms
copy to sparse
CPU times: user 290 ms, sys: 0 ns, total: 290 ms
Wall time: 290 ms
copy to statice sparse
CPU times: user 544 ms, sys: 0 ns, total: 544 ms
Wall time: 544 ms
delete edges
CPU times: user 166 ms, sys: 0 ns, total: 166 ms
Wall time: 166 ms
copying static sparse to sparse
CPU times: user 187 ms, sys: 0 ns, total: 187 ms
Wall time: 187 ms
sage: test_speed(2000)                                                                                                                                                                                                                                                                                                                                                     

now doing dense
adding edges
CPU times: user 340 ms, sys: 0 ns, total: 340 ms
Wall time: 340 ms
copy to dense
CPU times: user 40.9 ms, sys: 0 ns, total: 40.9 ms
Wall time: 40.8 ms
copy to sparse
CPU times: user 396 ms, sys: 3.93 ms, total: 400 ms
Wall time: 400 ms
copy to statice sparse
CPU times: user 2 s, sys: 68 ms, total: 2.07 s
Wall time: 2.07 s
delete edges
CPU times: user 321 ms, sys: 32 µs, total: 321 ms
Wall time: 321 ms
copying static sparse to dense
CPU times: user 396 ms, sys: 0 ns, total: 396 ms
Wall time: 396 ms

now doing sparse
adding edges
CPU times: user 768 ms, sys: 0 ns, total: 768 ms
Wall time: 768 ms
copy to dense
CPU times: user 791 ms, sys: 0 ns, total: 791 ms
Wall time: 791 ms
copy to sparse
CPU times: user 1.32 s, sys: 48 ms, total: 1.36 s
Wall time: 1.36 s
copy to statice sparse
CPU times: user 2.48 s, sys: 0 ns, total: 2.48 s
Wall time: 2.48 s
delete edges
CPU times: user 825 ms, sys: 0 ns, total: 825 ms
Wall time: 825 ms
copying static sparse to sparse
CPU times: user 876 ms, sys: 0 ns, total: 876 ms
Wall time: 876 ms
dcoudert commented 4 years ago

Description changed:

--- 
+++ 
@@ -7,6 +7,7 @@
 -  #7720: Digraph.reverse() should be rewritten more efficiently ( not hard ) 
 - #12387: Everything is not well with dense graph backends
 - #12540: Graph library passes almost surelly erroneous calls without an exception
+- #13730: Speed up some graph iterations
 - #22349: Deprecate sorting of Graph vertices and edges by default 
 - #28259: graph add_edges/delete_edges are dramatically slow 
 - #28896: Graphs: Move common methods of backends to CGraph
dcoudert commented 3 years ago

Description changed:

--- 
+++ 
@@ -29,6 +29,8 @@
 - #24989: G.edges_incident returns edges with vertices swapped
 - #25465, #28865: Memory error with graphs generators: JankoKharaghaniGraph and SquaredSkewHadamardMatrixGraph
 - #28309: improvement of method allow_multiple_edges
+- #31117: Improve Breadth First Search in c_graph.pyx
+- #31129: Improve Depth First Search in c_graph.pyx

 Here are some timings we try to improve along the way:
kliem commented 3 years ago

Description changed:

--- 
+++ 
@@ -19,6 +19,7 @@
 - #30753: Further improvements in method subgraph
 - #30777: Improve deleting of edges of graphs
 - use iterators for outgoing and ingoing arcs
+- #31197: Use bitsets/binary matrix for edges of dense graphs 

 Possibly related tickets:
mkoeppe commented 3 years ago
comment:23

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

dcoudert commented 3 years ago

Description changed:

--- 
+++ 
@@ -4,6 +4,7 @@

 https://groups.google.com/d/msg/sage-devel/JhirgrbcFMc/CVfHhPCdAgAJ

+- #6604: Polish the use of iterators in C graphs
 -  #7720: Digraph.reverse() should be rewritten more efficiently ( not hard ) 
 - #12387: Everything is not well with dense graph backends
 - #12540: Graph library passes almost surelly erroneous calls without an exception