(moderate) Speedup in layout_spring

[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

[git]

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

​e0555d7	trac #18395: zero-change cleaning
​fcb201b	trac #18395: Ugly hack for a 30% speedup
​8011e8e	trac #18395: Intermediate variable
​ecfaf11	trac #18395: heap variable -> stack variable
​49ddee0	trac #18395: Approx sqrt

[vdelecroix]

mulsitplying floats? Never heard of that ;-)

[ncohen]

mulsitplying floats? Never heard of that ;-)

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

[git]

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

​0e09b28

trac #18395: Merged with 6.8.beta6

[dcoudert]

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

[git]

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

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

[git]

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

​73662a9

trac #18395: Better constant

[dcoudert]

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

[git]

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

​0a5461d

trac #18395: Broken doctests

[ncohen]

Sorry 'bout that :-/

Fixed.

Nathann

[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.

[mderickx]

Needs to be rebased on sage8.1beta3

[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).

[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.

[git]

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

​f58edb0

trac #18395: resolve merge conflict

[dcoudert]

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

[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 ....

[vdelecroix]

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

[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

[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.

[vdelecroix]

Replying to dcoudert:

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

It is.

[git]

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

​88b2ba5

trac #18395: rebase on 8.1.beta3

[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.

[dcoudert]

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:

​be30ed8

trac #18395: fresh rebase on 8.1.beta5

[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.)

[git]

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

​ed02cfb

trac #18395: reviewers comments on the documentation

[dcoudert]

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

[tscrim]

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

[vbraun]

Fails on 32-bit, e.g. ​http://build.sagemath.org/#/builders/36/builds/14

[dcoudert]

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

[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

[tscrim]

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

[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

[git]

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

​021188a

trac #18395: specific doctests for 32 and 64 bits machines

[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.

[git]

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

​97684d6	trac #18395: Merged with 8.1.beta6
​dc5b80a	trac #18395: python3 compatibility

[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.

[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.

[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.

[tscrim]

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

[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.

[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).

[git]

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

​caf4da6

trac #18395: try abs tol 0.03 for problematic doctests

[dcoudert]

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

[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.

[git]

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

​8b5c9b1

trac #18395: correct use of rel tol in doctest

[dcoudert]

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

[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.

[git]

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

​a1c7286

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

[dcoudert]

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.

[vbraun]

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]

[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.

[tscrim]

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

[git]

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

​aa1d5b0	trac #18395: Merged with 8.1.beta7
​09a8953	trac #18395: increase relative tolerance in doctests

[dcoudert]

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