Opened 8 years ago
Closed 5 years ago
#18395 closed enhancement (fixed)
(moderate) Speedup in layout_spring
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage8.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, GitHub, GitLab)  Commit:  09a8953cbcb10a64c4a555fe54017be6db75ec21 
Dependencies:  Stopgaps: 
Description (last modified by )
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 compiletime. 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 8 years ago by
Branch:  → public/18395 

Status:  new → needs_review 
comment:2 Changed 8 years ago by
Commit:  → 49ddee04c89bbe5a5536305e47bfe777dde7f79a 

comment:4 Changed 8 years ago by
mulsitplying floats
? Never heard of that ;)
Can't you fix the typo instead of commenting on it?
comment:5 Changed 8 years ago by
Description:  modified (diff) 

comment:6 Changed 8 years ago by
Description:  modified (diff) 

comment:7 Changed 8 years ago by
Commit:  49ddee04c89bbe5a5536305e47bfe777dde7f79a → 0e09b28c7042adf81611beebc709613a04a1083b 

Branch pushed to git repo; I updated commit sha1. New commits:
0e09b28  trac #18395: Merged with 6.8.beta6

comment:8 Changed 8 years ago by
Milestone:  sage6.7 → sage6.8 

Status:  needs_review → 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 8 years ago by
Commit:  0e09b28c7042adf81611beebc709613a04a1083b → 84896d7af56fafb00baf61cd2a52ce850525b92b 

comment:10 Changed 8 years ago by
Commit:  84896d7af56fafb00baf61cd2a52ce850525b92b → 73662a95fb6e58805aa149f039f4c5b925785104 

Branch pushed to git repo; I updated commit sha1. New commits:
73662a9  trac #18395: Better constant

comment:11 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:12 Changed 8 years ago by
Cc:  dcoudert added 

Status:  needs_review → 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 8 years ago by
Commit:  73662a95fb6e58805aa149f039f4c5b925785104 → 0a5461da982420160000c48c417dcb374863a16a 

Branch pushed to git repo; I updated commit sha1. New commits:
0a5461d  trac #18395: Broken doctests

comment:14 Changed 8 years ago by
Status:  needs_work → needs_review 

Sorry 'bout that :/
Fixed.
Nathann
comment:15 Changed 8 years ago by
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 5 years ago by
Status:  needs_review → needs_work 

Needs to be rebased on sage8.1beta3
comment:17 followup: 18 Changed 5 years ago by
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 Changed 5 years ago by
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 5 years ago by
Commit:  0a5461da982420160000c48c417dcb374863a16a → f58edb0a8f46ea5519776256e1d246d3449a4193 

Branch pushed to git repo; I updated commit sha1. New commits:
f58edb0  trac #18395: resolve merge conflict

comment:20 Changed 5 years ago by
Outch... I did a git add .
before the commit. Sorry for that.
How can I erase that and try again ?
comment:21 Changed 5 years ago by
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 5 years ago by
Though if your commit is a merge commit that is not a good idea...
comment:23 Changed 5 years ago by
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 followup: 25 Changed 5 years ago by
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 Changed 5 years ago by
Replying to dcoudert:
is this correct to push the changes
git push f trac HEAD:public/18395
?
It is.
comment:26 Changed 5 years ago by
Commit:  f58edb0a8f46ea5519776256e1d246d3449a4193 → 88b2ba5db4ab9aa2c7dae65869938fbc61ec6477 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
88b2ba5  trac #18395: rebase on 8.1.beta3

comment:27 Changed 5 years ago by
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 5 years ago by
Authors:  Nathann Cohen → Nathann Cohen, David Coudert 

Milestone:  sage6.8 → sage8.1 
Status:  needs_work → needs_review 
comment:29 Changed 5 years ago by
Branch:  public/18395 → u/dcoudert/18395_spring 

Commit:  88b2ba5db4ab9aa2c7dae65869938fbc61ec6477 → 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:
be30ed8  trac #18395: fresh rebase on 8.1.beta5

comment:30 Changed 5 years ago by
LGTM except some more nitpicktype 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 5 years ago by
Reviewers:  → Travis Scrimshaw 

comment:32 Changed 5 years ago by
Commit:  be30ed88e02d33442167f36c4ea8e608351e7e2c → ed02cfb81b50b180110c40e19d062146e1242824 

Branch pushed to git repo; I updated commit sha1. New commits:
ed02cfb  trac #18395: reviewers comments on the documentation

comment:33 Changed 5 years ago by
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 5 years ago by
Status:  needs_review → positive_review 

Oh that's right, cdef
functions are not included. Thanks.
comment:35 Changed 5 years ago by
Fails on 32bit, e.g. http://build.sagemath.org/#/builders/36/builds/14
comment:36 Changed 5 years ago by
Status:  positive_review → needs_work 

comment:37 Changed 5 years ago by
Numerical issues. I don't know how to make the tests robust to such issues. Anyone has a proposal?
comment:38 Changed 5 years ago by
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#specialmarkuptoinfluencedoctests
comment:39 Changed 5 years ago by
There are also flags you can set for doctest outout specifically for 32 bit and 64 bit machines.
comment:40 Changed 5 years ago by
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
comment:41 Changed 5 years ago by
Commit:  ed02cfb81b50b180110c40e19d062146e1242824 → 021188a3c9f6517baa8a8138caf4686613fa71e1 

Branch pushed to git repo; I updated commit sha1. New commits:
021188a  trac #18395: specific doctests for 32 and 64 bits machines

comment:42 Changed 5 years ago by
I used the values from http://build.sagemath.org/#/builders/36/builds/14 for 32bits machine, since I don't have access to such CPU. I hope it's ok.
comment:43 Changed 5 years ago by
Status:  needs_work → needs_review 

comment:44 Changed 5 years ago by
Commit:  021188a3c9f6517baa8a8138caf4686613fa71e1 → dc5b80a6317cd0d17d48b7e89313e4abb6a48dfe 

comment:45 Changed 5 years ago by
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 5 years ago by
It means you should replace the ...
by ....:
as explained on http://doc.sagemath.org/html/en/developer/coding_basics.html#writingtestableexamples under the heading multiline doctests.
comment:47 Changed 5 years ago by
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#specialmarkuptoinfluencedoctests. It's not for the code part.
I suspect a conflict with the # 32bit
and # 64bit
tags.
comment:48 Changed 5 years ago by
Patchbot plugins can be a little dumb at times. However, it does look like there still is some numerical issues.
comment:49 Changed 5 years ago by
I don't know what to do. All tests pass on my 64bit OSX computer, but since the method uses random initial positions, the result may change from a computer to another.
comment:50 Changed 5 years ago by
Two options: Raise the tolerance by removing sigfigs 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 5 years ago by
Commit:  dc5b80a6317cd0d17d48b7e89313e4abb6a48dfe → caf4da68f040bea3c0fed2bcb04cd5a3ea84994f 

Branch pushed to git repo; I updated commit sha1. New commits:
caf4da6  trac #18395: try abs tol 0.03 for problematic doctests

comment:53 Changed 5 years ago by
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 5 years ago by
Commit:  caf4da68f040bea3c0fed2bcb04cd5a3ea84994f → 8b5c9b17bd4c7d1fdf3d6c6e30d43cbced213e79 

Branch pushed to git repo; I updated commit sha1. New commits:
8b5c9b1  trac #18395: correct use of rel tol in doctest

comment:55 Changed 5 years ago by
I was not using correctly rel tol
. Also, I have simplified the output.
comment:56 Changed 5 years ago by
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 5 years ago by
Commit:  8b5c9b17bd4c7d1fdf3d6c6e30d43cbced213e79 → a1c728647ff1ee02634691ff2600a4c44565fbd6 

Branch pushed to git repo; I updated commit sha1. New commits:
a1c7286  trac #18395: test that we have as many vertices as computed positions

comment:58 Changed 5 years ago by
Status:  needs_review → 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 5 years ago by
Status:  positive_review → 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 4e02 > 3e02 ********************************************************************** 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 5 years ago by
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 5 years ago by
Increase the tolerance (or choose another output that is slightly higher if you think the current is on the low side).
comment:62 Changed 5 years ago by
Commit:  a1c728647ff1ee02634691ff2600a4c44565fbd6 → 09a8953cbcb10a64c4a555fe54017be6db75ec21 

comment:63 Changed 5 years ago by
I have changed the tolerance to 0.1. It should be more robust to the various cpus / systems.
comment:64 Changed 5 years ago by
Status:  needs_work → needs_review 

comment:65 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:66 Changed 5 years ago by
Branch:  u/dcoudert/18395_spring → 09a8953cbcb10a64c4a555fe54017be6db75ec21 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
trac #18395: zerochange cleaning
trac #18395: Ugly hack for a 30% speedup
trac #18395: Intermediate variable
trac #18395: heap variable > stack variable
trac #18395: Approx sqrt