#12371: The graph_decompositions/ code seems to have bounds issues
--------------------------------+-------------------------------------------
Reporter: Snark | Owner: jason, ncohen, rlm
Type: defect | Status: needs_info
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Comment (by ncohen):
Yooooooo !!!
Well, I just did the tests, and you can find attached the patch I used to
do that. I actually first did the tests by replacing "return popcount32"
in the code by "return \_\_builtin_popcount", and there was no difference
that I could see in the runtimes of path_decomposition. I was about to say
"ok you are right, there is no difference after all", but short of my
natural dislike of acknowledging my own mistakes, I was really convinced
that there was a real diference between the two.
And it turns out that if I did not see the difference anymore, it is
because of some change I made late in the path_decomposition algorithm (a
previous version was *MUCH* slower than the current one), and this
popcount is not the critical function anymore.
The "stupid test" (try many integers, compute what's left afterwards) is
clear enough though :
{{{
sage: from sage.graphs.graph_decompositions.vertex_separation import
test_handmade, test_builtin
sage: time test_builtin()
-805306368
Time: CPU 5.94 s, Wall: 5.95 s
sage: time test_handmade()
-805306368
Time: CPU 1.85 s, Wall: 1.85 s
}}}
Of course, these tests are immediately destroyed if you are lucky enough
to compile the code on a machine with the popcnt instruction enabled...
But so far I found no way to do that in a way that would not make the code
crash on a machine that does *not* have it enabled.
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12371#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
