Opened 5 years ago

Closed 3 years ago

#18395 closed enhancement (fixed)

(moderate) Speedup in layout_spring

Reported by: ncohen Owned by:
Priority: major Milestone: sage-8.1
Component: graph theory Keywords:
Cc: vbraun, vdelecroix, dcoudert Merged in:
Authors: Nathann Cohen, David Coudert Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 09a8953 (Commits) Commit: 09a8953cbcb10a64c4a555fe54017be6db75ec21
Dependencies: Stopgaps:

Description (last modified by ncohen)

This branch improves (a bit) the performances of the 'layout_spring' algorithm, i.e. the attraction/repulsion layout for graphs.

I tested it on the CameronGraph (big and dense), with the following results:

Before:

sage: g = graphs.CameronGraph()
sage: %time _=g.layout_spring(iterations=100000)
CPU times: user 30.8 s, sys: 8 ms, total: 30.8 s
Wall time: 30.8 s

After

sage: g = graphs.CameronGraph()
sage: %time _=g.layout_spring(iterations=100000)
CPU times: user 14.3 s, sys: 4 ms, total: 14.3 s
Wall time: 14.3 s

Honestly, that is mostly a failure. Most of the speedup comes from templating the code so that dim=2 and dim=3 are decided at compile-time. Most of the time it spent multiplying floats, and that's what I have been trying to reduce. Not with obvious success :-/

Nathann

Change History (66)

comment:1 Changed 5 years ago by ncohen

  • Branch set to public/18395
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 49ddee04c89bbe5a5536305e47bfe777dde7f79a

Branch pushed to git repo; I updated commit sha1. New commits:

e0555d7trac #18395: zero-change cleaning
fcb201btrac #18395: Ugly hack for a 30% speedup
8011e8etrac #18395: Intermediate variable
ecfaf11trac #18395: heap variable -> stack variable
49ddee0trac #18395: Approx sqrt

comment:3 follow-up: Changed 5 years ago by vdelecroix

mulsitplying floats? Never heard of that ;-)

comment:4 in reply to: ↑ 3 Changed 5 years ago by ncohen

mulsitplying floats? Never heard of that ;-)

Can't you fix the typo instead of commenting on it?

comment:5 Changed 5 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 5 years ago by ncohen

  • Description modified (diff)

comment:7 Changed 5 years ago by git

  • Commit changed from 49ddee04c89bbe5a5536305e47bfe777dde7f79a to 0e09b28c7042adf81611beebc709613a04a1083b

Branch pushed to git repo; I updated commit sha1. New commits:

0e09b28trac #18395: Merged with 6.8.beta6

comment:8 Changed 5 years ago by dcoudert

  • Milestone changed from sage-6.7 to sage-6.8
  • Status changed from needs_review to needs_work

I tried on top of 6.8.rc0

sage -t --long src/sage/graphs/generic_graph_pyx.pyx
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 54, in sage.graphs.generic_graph_pyx.spring_layout_fast_split
Failed example:
    spring_layout_fast_split(G)
Expected:
    {0: [0.452..., 0.247...], ..., 502: [25.7..., 0.505...]}
Got:
    {0: [nan, nan],
     1: [nan, nan],
     2: [nan, nan],
...
     902: [nan, nan]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 97, in sage.graphs.generic_graph_pyx.spring_layout_fast
Failed example:
    spring_layout_fast(G)
Expected:
    {0: [-0.0733..., 0.157...], ..., 502: [-0.551..., 0.682...]}
Got:
    {0: [nan, nan],
     1: [nan, nan],
...
     902: [nan, nan]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 113, in sage.graphs.generic_graph_pyx.spring_layout_fast
Failed example:
    spring_layout_fast(G, by_component = True)
Expected:
    {0: [2.12..., -0.321...], ..., 502: [26.0..., -0.812...]}
Got:
    {0: [nan, nan],
     1: [nan, nan],
...
     902: [nan, nan]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 346, in sage.graphs.generic_graph_pyx.sqrt_approx
Failed example:
    polar_plot([1,lambda x:dist(cos(x),sin(x))], (0, 2*pi))
Expected:
    Launched png viewer for Graphics object consisting of 2 graphics primitives
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************
3 items had failures:
   2 of   9 in sage.graphs.generic_graph_pyx.spring_layout_fast
   1 of   5 in sage.graphs.generic_graph_pyx.spring_layout_fast_split
   1 of   3 in sage.graphs.generic_graph_pyx.sqrt_approx
    [81 tests, 4 failures, 3.03 s]
----------------------------------------------------------------------
sage -t --long src/sage/graphs/generic_graph_pyx.pyx  # 4 doctests failed
----------------------------------------------------------------------
Total time for all tests: 3.1 seconds
    cpu time: 2.8 seconds
    cumulative wall time: 3.0 seconds

comment:9 Changed 5 years ago by git

  • Commit changed from 0e09b28c7042adf81611beebc709613a04a1083b to 84896d7af56fafb00baf61cd2a52ce850525b92b

Branch pushed to git repo; I updated commit sha1. New commits:

8442657trac #18395: Merged with 6.8.rc0
84896d7trac #18395: Turns out that the behaviour of 'abs' changed O_o

comment:10 Changed 5 years ago by git

  • Commit changed from 84896d7af56fafb00baf61cd2a52ce850525b92b to 73662a95fb6e58805aa149f039f4c5b925785104

Branch pushed to git repo; I updated commit sha1. New commits:

73662a9trac #18395: Better constant

comment:11 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:12 Changed 5 years ago by dcoudert

  • Cc dcoudert added
  • Status changed from needs_review to needs_work

some problems remain :(

sage -t --long src/sage/graphs/generic_graph_pyx.pyx
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 54, in sage.graphs.generic_graph_pyx.spring_layout_fast_split
Failed example:
    spring_layout_fast_split(G)
Expected:
    {0: [0.452..., 0.247...], ..., 502: [25.7..., 0.505...]}
Got:
    {0: [0.7785109925614286, 0.06976708739098784],
     1: [0.7761449200341834, 0.5516862310233024],
...
     902: [3.130511551759616, 0.22735834286143738]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 97, in sage.graphs.generic_graph_pyx.spring_layout_fast
Failed example:
    spring_layout_fast(G)
Expected:
    {0: [-0.0733..., 0.157...], ..., 502: [-0.551..., 0.682...]}
Got:
    {0: [0.007496865679470362, 0.04129113197411667],
     1: [0.01495366592880235, 0.08850535412927439],
     2: [0.05849657218327249, 0.09484847570321614],
...
     901: [-0.4474352390771702, -0.10570013179405174],
     902: [-0.47861195812354, -0.10660577880837746]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 113, in sage.graphs.generic_graph_pyx.spring_layout_fast
Failed example:
    spring_layout_fast(G, by_component = True)
Expected:
    {0: [2.12..., -0.321...], ..., 502: [26.0..., -0.812...]}
Got:
    {0: [2.2186445972355, -0.008574741789712105],
     1: [2.121454111190332, 0.5076017939042802],
...
     902: [3.0706796988471234, 0.8610997979963941]}
**********************************************************************
File "src/sage/graphs/generic_graph_pyx.pyx", line 348, in sage.graphs.generic_graph_pyx.sqrt_approx
Failed example:
    polar_plot([1,lambda x:dist(cos(x),sin(x))], (0, 2*pi))
Expected:
    Launched png viewer for Graphics object consisting of 2 graphics primitives
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************
3 items had failures:
   2 of   9 in sage.graphs.generic_graph_pyx.spring_layout_fast
   1 of   5 in sage.graphs.generic_graph_pyx.spring_layout_fast_split
   1 of   3 in sage.graphs.generic_graph_pyx.sqrt_approx
    [81 tests, 4 failures, 3.42 s]
----------------------------------------------------------------------
sage -t --long src/sage/graphs/generic_graph_pyx.pyx  # 4 doctests failed
----------------------------------------------------------------------
Total time for all tests: 3.5 seconds
    cpu time: 3.2 seconds
    cumulative wall time: 3.4 seconds

comment:13 Changed 5 years ago by git

  • Commit changed from 73662a95fb6e58805aa149f039f4c5b925785104 to 0a5461da982420160000c48c417dcb374863a16a

Branch pushed to git repo; I updated commit sha1. New commits:

0a5461dtrac #18395: Broken doctests

comment:14 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

Sorry 'bout that :-/

Fixed.

Nathann

comment:15 Changed 5 years ago by vbraun

Those two almost certainly compile to the same binary:

-              for x from 0 <= x < dim:
-                  disp_i[x] += delta[x] * force
-                  disp_j[x] -= delta[x] * force
+              for x in range(dim):
+                  d_tmp = delta[x] * force
+                  disp_i[x] += d_tmp
+                  disp_j[x] -= d_tmp

You can probably speed it by a few orders of magnitude by not using Euler's method.

comment:16 Changed 3 years ago by mderickx

  • Status changed from needs_review to needs_work

Needs to be rebased on sage8.1beta3

comment:17 follow-up: Changed 3 years ago by dcoudert

I tried but there are merge conflicts in file generic_graph_pyx.pyx and I don't know how to fix that (I need some help/pointer/training to do that).

comment:18 in reply to: ↑ 17 Changed 3 years ago by vdelecroix

Replying to dcoudert:

I tried but there are merge conflicts in file generic_graph_pyx.pyx and I don't know how to fix that (I need some help/pointer/training to do that).

For example https://gist.github.com/karenyyng/f19ff75c60f18b4b8149

You can also google "git resolve conflicts" or "git mergetool" and pick the link you prefer.

comment:19 Changed 3 years ago by git

  • Commit changed from 0a5461da982420160000c48c417dcb374863a16a to f58edb0a8f46ea5519776256e1d246d3449a4193

Branch pushed to git repo; I updated commit sha1. New commits:

f58edb0trac #18395: resolve merge conflict

comment:20 Changed 3 years ago by dcoudert

Outch... I did a git add . before the commit. Sorry for that. How can I erase that and try again ?

comment:21 Changed 3 years ago by vdelecroix

To cancel the last commit git reset HEAD^. Then do what you want. At the time you will update the remote branch on trac with git push ... you will have a complain because you changed history. You will have to add the option -f (for force), i.e. do git push -f ....

comment:22 Changed 3 years ago by vdelecroix

Though if your commit is a merge commit that is not a good idea...

comment:23 Changed 3 years ago by vdelecroix

In the case you want to redo the merge, just start from scratch from ​0a5461d. In other words, something like

$ git checkout -b my_new_merge ​0a5461d
$ git merge develop    # or whatever how this is called

comment:24 follow-up: Changed 3 years ago by dcoudert

It's working !!! I'm currently recompiling / testing. It will be long.

is this correct to push the changes git push -f trac HEAD:public/18395 ?

Thank you very much.

comment:25 in reply to: ↑ 24 Changed 3 years ago by vdelecroix

Replying to dcoudert:

is this correct to push the changes git push -f trac HEAD:public/18395 ?

It is.

comment:26 Changed 3 years ago by git

  • Commit changed from f58edb0a8f46ea5519776256e1d246d3449a4193 to 88b2ba5db4ab9aa2c7dae65869938fbc61ec6477

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

88b2ba5trac #18395: rebase on 8.1.beta3

comment:27 Changed 3 years ago by dcoudert

I followed what we said, but when I look at the branch it's really weird. Let me know if I show try again with a different set of commands. Thanks.

comment:28 Changed 3 years ago by dcoudert

  • Authors changed from Nathann Cohen to Nathann Cohen, David Coudert
  • Milestone changed from sage-6.8 to sage-8.1
  • Status changed from needs_work to needs_review

comment:29 Changed 3 years ago by dcoudert

  • Branch changed from public/18395 to u/dcoudert/18395_spring
  • Commit changed from 88b2ba5db4ab9aa2c7dae65869938fbc61ec6477 to be30ed88e02d33442167f36c4ea8e608351e7e2c

I have created a new branched, on top of 8.1.beta5, containing all previous modifications. This way we get rid of all the mess I made with git. I hope we can now go forward with this ticket.


New commits:

be30ed8trac #18395: fresh rebase on 8.1.beta5

comment:30 Changed 3 years ago by tscrim

LGTM except some more nitpick-type things:

-    Approximation of sqrt(x^2+y^2).
+    Approximation of `\sqrt(x^2 + y^2)`.
 
-    Assuming that x>y>0, it is a taylor expansion at x^2. To see how 'bad' the
-    approximation is::
+    Assuming that `x > y > 0`, it is a Taylor expansion at `x^2`. To see how 'bad' the
+    approximation is:
 
+    .. PLOT::
+
+        def dist(x,y):
+            x = abs(x)
+            y = abs(y)
+            return max(x,y) + min(x,y)**2/(2*max(x,y))
+        sphinx_plot(polar_plot([1, lambda x: dist(cos(x),sin(x))], (0, 2*pi)))

(Please check that the plot of the graph is correct.)

comment:31 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

comment:32 Changed 3 years ago by git

  • Commit changed from be30ed88e02d33442167f36c4ea8e608351e7e2c to ed02cfb81b50b180110c40e19d062146e1242824

Branch pushed to git repo; I updated commit sha1. New commits:

ed02cfbtrac #18395: reviewers comments on the documentation

comment:33 Changed 3 years ago by dcoudert

I did the changes in the text (better reading), but not the PLOT part since the method is not in the html doc.

comment:34 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Oh that's right, cdef functions are not included. Thanks.

comment:36 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:37 Changed 3 years ago by dcoudert

Numerical issues. I don't know how to make the tests robust to such issues. Anyone has a proposal?

comment:38 Changed 3 years ago by mderickx

It is quite easy to fix. One should just modify the doctest to only check for the correct ammount of digits. So one could just remove some digits that change between 32 and 64 bits before the ... in the current doctest. A more elegant solution would be to use the support in sage doctest to tolerate a certain ammount of numerical noise. See the tolerance section of: http://doc.sagemath.org/html/en/developer/coding_basics.html#special-markup-to-influence-doctests

comment:39 Changed 3 years ago by tscrim

There are also flags you can set for doctest outout specifically for 32 bit and 64 bit machines.

comment:40 Changed 3 years ago by mderickx

Ah yes, tscrims solution is better in this case, since my solution would uneccesarily sacrifice precission. How to do this is also documented at the link I send previously

Last edited 3 years ago by mderickx (previous) (diff)

comment:41 Changed 3 years ago by git

  • Commit changed from ed02cfb81b50b180110c40e19d062146e1242824 to 021188a3c9f6517baa8a8138caf4686613fa71e1

Branch pushed to git repo; I updated commit sha1. New commits:

021188atrac #18395: specific doctests for 32 and 64 bits machines

comment:42 Changed 3 years ago by dcoudert

I used the values from http://build.sagemath.org/#/builders/36/builds/14 for 32-bits machine, since I don't have access to such CPU. I hope it's ok.

comment:43 Changed 3 years ago by dcoudert

  • Status changed from needs_work to needs_review

comment:44 Changed 3 years ago by git

  • Commit changed from 021188a3c9f6517baa8a8138caf4686613fa71e1 to dc5b80a6317cd0d17d48b7e89313e4abb6a48dfe

Branch pushed to git repo; I updated commit sha1. New commits:

97684d6trac #18395: Merged with 8.1.beta6
dc5b80atrac #18395: python3 compatibility

comment:45 Changed 3 years ago by dcoudert

The patchbot reports incompatibility with python 3. I fixed that.

The patchbot reports an issue with doctest continuation (here) but I don't know what to do with it. Any help is more than welcome.

comment:46 Changed 3 years ago by mderickx

It means you should replace the ... by ....: as explained on http://doc.sagemath.org/html/en/developer/coding_basics.html#writing-testable-examples under the heading multiline doctests.

comment:47 Changed 3 years ago by dcoudert

I'm using ... for the output, as for other doctests in the same file for which the patchbot is not complaining, and as explained on http://doc.sagemath.org/html/en/developer/coding_basics.html#special-markup-to-influence-doctests. It's not for the code part.

I suspect a conflict with the # 32-bit and # 64-bit tags.

comment:48 Changed 3 years ago by tscrim

Patchbot plugins can be a little dumb at times. However, it does look like there still is some numerical issues.

comment:49 Changed 3 years ago by dcoudert

I don't know what to do. All tests pass on my 64-bit OSX computer, but since the method uses random initial positions, the result may change from a computer to another.

comment:50 Changed 3 years ago by tscrim

Two options: Raise the tolerance by removing sig-figs from the output or mark them with a # rel tol or # abs tol. I would suggest the second (unless the doctest framework doesn't like it) as it is more robust (i.e., a difference of 0.01 could change the first decimal place).

comment:51 Changed 3 years ago by git

  • Commit changed from dc5b80a6317cd0d17d48b7e89313e4abb6a48dfe to caf4da68f040bea3c0fed2bcb04cd5a3ea84994f

Branch pushed to git repo; I updated commit sha1. New commits:

caf4da6trac #18395: try abs tol 0.03 for problematic doctests

comment:52 Changed 3 years ago by dcoudert

Let's see if it's better this way.

comment:53 Changed 3 years ago by tscrim

Hmm...that doesn't seem to work. Probably due to a mixing of the ellipses and the rel tol. I guess we just have to lower the sigfigs in the output.

comment:54 Changed 3 years ago by git

  • Commit changed from caf4da68f040bea3c0fed2bcb04cd5a3ea84994f to 8b5c9b17bd4c7d1fdf3d6c6e30d43cbced213e79

Branch pushed to git repo; I updated commit sha1. New commits:

8b5c9b1trac #18395: correct use of rel tol in doctest

comment:55 Changed 3 years ago by dcoudert

I was not using correctly rel tol. Also, I have simplified the output.

comment:56 Changed 3 years ago by tscrim

Since you have changed the output format, you should also add a check that the length is 902. Once done, you can set a positive review on my behalf.

comment:57 Changed 3 years ago by git

  • Commit changed from 8b5c9b17bd4c7d1fdf3d6c6e30d43cbced213e79 to a1c728647ff1ee02634691ff2600a4c44565fbd6

Branch pushed to git repo; I updated commit sha1. New commits:

a1c7286trac #18395: test that we have as many vertices as computed positions

comment:58 Changed 3 years ago by dcoudert

  • Status changed from needs_review to positive_review

902 is not the length but the largest index of a vertex (pos is a dictionary). The graph has 50 vertices. I added a test to check that pos has 50 entries.

I set the ticket to positive review as you proposed.

Thank you.

comment:59 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work
File "src/sage/graphs/generic_graph_pyx.pyx", line 113, in sage.graphs.generic_graph_pyx.spring_layout_fast
Failed example:
    pos[902] # abs tol 0.03
Expected:
    [-0.48..., -0.10...]
Got:
    [-0.48914249502701945, -0.13939583925593196]
Tolerance exceeded in 1 of 2:
    -0.10 vs -0.13939583925593196, tolerance 4e-02 > 3e-02
**********************************************************************
1 item had failures:
   1 of  15 in sage.graphs.generic_graph_pyx.spring_layout_fast
    [94 tests, 1 failure, 2.32 s]

comment:60 Changed 3 years ago by dcoudert

I can either increase the tolerance to e.g. 0.1, or remove this test, but I don't know what would be better.

comment:61 Changed 3 years ago by tscrim

Increase the tolerance (or choose another output that is slightly higher if you think the current is on the low side).

comment:62 Changed 3 years ago by git

  • Commit changed from a1c728647ff1ee02634691ff2600a4c44565fbd6 to 09a8953cbcb10a64c4a555fe54017be6db75ec21

Branch pushed to git repo; I updated commit sha1. New commits:

aa1d5b0trac #18395: Merged with 8.1.beta7
09a8953trac #18395: increase relative tolerance in doctests

comment:63 Changed 3 years ago by dcoudert

I have changed the tolerance to 0.1. It should be more robust to the various cpus / systems.

comment:64 Changed 3 years ago by dcoudert

  • Status changed from needs_work to needs_review

comment:65 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:66 Changed 3 years ago by vbraun

  • Branch changed from u/dcoudert/18395_spring to 09a8953cbcb10a64c4a555fe54017be6db75ec21
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.