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: | 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, 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 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 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: | sage-6.7 → sage-6.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 follow-up: 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 follow-up: 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: | sage-6.8 → sage-8.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 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 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 32-bit, 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#special-markup-to-influence-doctests
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 32-bits 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#writing-testable-examples 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#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 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 64-bit 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 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 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 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 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: zero-change cleaning
trac #18395: Ugly hack for a 30% speedup
trac #18395: Intermediate variable
trac #18395: heap variable -> stack variable
trac #18395: Approx sqrt