[ARM] sage-4.8 ptestlong failures
Julien Puydt
I ran sage-4.8 (with the flint-1.5.2 spkg)'s ptestlong :
Total time for all tests: 29104.6 seconds
There are three kinds of failures in the log :
(1) numerical uncertainty :
sage -t --long -force_lib devel/sage/sage/functions/other.py
**********************************************************************
File "/home/jpuydt/sage-4.8/devel/sage-main/sage/functions/other.py",
line 511:
sage: gamma1(float(6))
Expected:
120.0
Got:
119.99999999999997
**********************************************************************
1 items had failures:
1 of 33 in __main__.example_13
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/other_27290.py
[52.4 s]
sage -t --long -force_lib devel/sage/sage/symbolic/expression.pyx
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/symbolic/expression.pyx",
line 6256:
sage: SR(10.0r).gamma()
Expected:
362880.0
Got:
362880.00000000047
#0: simplify_sum(expr='sum(q^k,k,0,inf))
#1: simplify_sum(expr=a*'sum(q^k,k,0,inf))
**********************************************************************
1 items had failures:
1 of 16 in __main__.example_142
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/expression_27592.py
[171.5 s]
sage -t --long -force_lib devel/sage/sage/interfaces/maxima_abstract.py
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/interfaces/maxima_abstract.py",
line 1595:
sage: float(maxima("1.7e+17"))
Expected:
1.7e+17
Got:
1.6999999999999997e+17
**********************************************************************
1 items had failures:
1 of 6 in __main__.example_54
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/maxima_abstract_7679.py
[83.7 s]
(2) strange graph errors :
sage -t --long -force_lib
devel/sage/sage/graphs/graph_decompositions/vertex_separation.pyx
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/graphs/graph_decompositions/vertex_separation.pyx",
line 252:
sage: path_decomposition(g)
Expected:
(2, [0, 1, 2, 3, 4, 5])
Got:
(6, [])
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/graphs/graph_decompositions/vertex_separation.pyx",
line 302:
sage: vertex_separation(g)
Expected:
(1, [0, 1, 2, 3, 4, 5])
Got:
(6, [])
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/graphs/graph_decompositions/vertex_separation.pyx",
line 319:
sage: vertex_separation(D)
Expected:
(2, ['000', '001', '100', '010', '101', '011', '110', '111'])
Got:
(8, [])
**********************************************************************
2 items had failures:
1 of 9 in __main__.example_2
2 of 11 in __main__.example_3
***Test Failed*** 3 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/vertex_separation_7578.py
[13.4 s]
(3) pickling issues :
sage -t --long -force_lib devel/sage/sage/structure/sage_object.pyx
**********************************************************************
File
"/home/jpuydt/sage-4.8/devel/sage-main/sage/structure/sage_object.pyx",
line 1103:
sage: sage.structure.sage_object.unpickle_all() # (4s on
sage.math, 2011)
Expected:
doctest:... DeprecationWarning: This class is replaced by
Matrix_modn_dense_float/Matrix_modn_dense_double.
Successfully unpickled ... objects.
Failed to unpickle 0 objects.
Got:
* unpickle failure:
load('/home/jpuydt/.sage/temp/hecke/27057/dir_2/pickle_jar/_class__sage_coding_linear_code_LinearCode__.sobj')
* unpickle failure:
load('/home/jpuydt/.sage/temp/hecke/27057/dir_2/pickle_jar/_class__sage_crypto_mq_sr_SR_gf2__.sobj')
doctest:1172: DeprecationWarning: This class is replaced by
Matrix_modn_dense_float/Matrix_modn_dense_double.
* unpickle failure:
load('/home/jpuydt/.sage/temp/hecke/27057/dir_2/pickle_jar/_class__sage_homology_chain_complex_ChainComplex__.sobj')
* unpickle failure:
load('/home/jpuydt/.sage/temp/hecke/27057/dir_2/pickle_jar/_type__sage_coding_binary_code_BinaryCode__.sobj')
* unpickle failure:
load('/home/jpuydt/.sage/temp/hecke/27057/dir_2/pickle_jar/_type__sage_matrix_matrix_mod2_dense_Matrix_mod2_dense__.sobj')
Failed:
_class__sage_coding_linear_code_LinearCode__.sobj
_class__sage_crypto_mq_sr_SR_gf2__.sobj
_class__sage_homology_chain_complex_ChainComplex__.sobj
_type__sage_coding_binary_code_BinaryCode__.sobj
_type__sage_matrix_matrix_mod2_dense_Matrix_mod2_dense__.sobj
Successfully unpickled 582 objects.
Failed to unpickle 5 objects.
**********************************************************************
1 items had failures:
1 of 7 in __main__.example_25
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/sage_object_27055.py
[32.3 s]
(4) that one is... interesting :
sage -t --long -force_lib devel/sage/sage/interfaces/quit.py
**********************************************************************
File "/home/jpuydt/sage-4.8/devel/sage-main/sage/interfaces/quit.py",
line 116:
sage: a, b
Expected:
(2, 3)
Got:
(0(%o19)"__SAGE_SYNCHRO_MARKER_1429138732", 3)
**********************************************************************
1 items had failures:
1 of 10 in __main__.example_4
***Test Failed*** 1 failures.
For whitespace errors, see the file
/home/jpuydt/.sage/tmp/hecke-21596/quit_8048.py
[135.6 s]
Congratulations to those who noticed I announced three kinds of errors
and listed four!
Snark on #sagemath
Dima Pasechnik
Julien Puydt
> sage -t --long -force_lib devel/sage/sage/interfaces/quit.py
> **********************************************************************
> File "/home/jpuydt/sage-4.8/devel/sage-main/sage/interfaces/quit.py",
> line 116:
> sage: a, b
> Expected:
> (2, 3)
> Got:
> (0(%o19)"__SAGE_SYNCHRO_MARKER_1429138732", 3)
> **********************************************************************
> 1 items had failures:
> 1 of 10 in __main__.example_4
> ***Test Failed*** 1 failures.
> For whitespace errors, see the file
> /home/jpuydt/.sage/tmp/hecke-21596/quit_8048.py
> [135.6 s]
I re-ran that test separately and it disappeared.
Snark on #sagemath
Julien Puydt
> That's on 32-but ARM running Ubuntu 11.10, right?
Right.
> So these graph-related things were not here before, or was it the 1st
> time you ran ptestlong?
The previous times I ran ptestlong, there was just numerical noise and
pickle ; I can't remember exactly when that was.
Snark on #sagemath
Julien Puydt
The good news is that if I put the following lines in a test_graphs.py
file, the problem is still there:
from sage.all import *
from sage.graphs.graph_decompositions.vertex_separation import
vertex_separation
from sage.graphs.graph_decompositions.vertex_separation import
path_decomposition
g = graphs.CycleGraph(6)
print(path_decomposition(g))
g = digraphs.Circuit(6)
print(vertex_separation(g))
D = digraphs.DeBruijn(2,3)
print(vertex_separation(D))
Now I just need to find out where the code lies, and what changed since
my last ptestlong run.
Snark on #sagemath
Julien Puydt
The code is in vertex_separation.pyx, and running it in verbose mode on
my main system gives :
Memory allocation
0 1 0 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0
Looking for a strategy of cost 0
Looking for a strategy of cost 1
Looking for a strategy of cost 2
... Found !
Now computing the ordering
(2, [0, 1, 2, 3, 4, 5])
Memory allocation
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
1 0 0 0 0 0
Looking for a strategy of cost 0
Looking for a strategy of cost 1
... Found !
Now computing the ordering
(1, [0, 1, 2, 3, 4, 5])
Memory allocation
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
Looking for a strategy of cost 0
Looking for a strategy of cost 1
Looking for a strategy of cost 2
... Found !
Now computing the ordering
(2, ['111', '112', '211', '121', '212', '122', '221', '222'])
while on the ARM box :
Memory allocation
0 1 0 0 0 1
1 0 1 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 1 0 1
1 0 0 0 1 0
Looking for a strategy of cost 0
Looking for a strategy of cost 1
Looking for a strategy of cost 2
Looking for a strategy of cost 3
Looking for a strategy of cost 4
Looking for a strategy of cost 5
... Found !
Now computing the ordering
(6, [])
Memory allocation
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
1 0 0 0 0 0
Looking for a strategy of cost 0
Looking for a strategy of cost 1
Looking for a strategy of cost 2
Looking for a strategy of cost 3
Looking for a strategy of cost 4
Looking for a strategy of cost 5
... Found !
Now computing the ordering
(6, [])
Memory allocation
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 1
Looking for a strategy of cost 0
Looking for a strategy of cost 1
Looking for a strategy of cost 2
Looking for a strategy of cost 3
Looking for a strategy of cost 4
Looking for a strategy of cost 5
Looking for a strategy of cost 6
Looking for a strategy of cost 7
... Found !
Now computing the ordering
(8, [])
What bothers me is that the "exists" function looks quite portable, so
the reason of the failure is unclear.
Snark on #sagemath
Julien Puydt
> What bothers me is that the "exists" function looks quite portable, so
> the reason of the failure is unclear.
What bothers me even more is that this file has a very short history :
$ hg log sage/graphs/graph_decompositions/vertex_separation.pyx
changeset: 16281:22e24b32f88f
user: Nathann Cohen <nathan...@gmail.com>
date: Fri Nov 18 19:29:56 2011 +0100
summary: Trac #12052: trac #12052 -- Some distance computations
remained *slow*
changeset: 16250:3bc34f3b1579
user: Nathann Cohen <nathan...@gmail.com>
date: Sun Nov 06 00:06:36 2011 +0100
summary: Trac #11994: trac 11994 -- vertex separation in Sage
and I checked that removing the last patch still gives the error.
So I would say something else changed outside of that code, which breaks
on ARM.
I would welcome ideas :-/
Snark on #sagemath
Nathann Cohen
Dima Pasechnik
Nathann Cohen
> a difference...
Yepyep.... It's commented in the code, actually. I used it on a
machine which had the popcount instruction enable, but on others the
__builtin_popcount is slower that the current code. This being said,
it should work, unlike the current code :-p
Nathann
Dima Pasechnik
Nathann
Nathann Cohen
> wired in, so __builtin_popcount(), which is a gcc function, will beat your
> implementation, as time goes by.
Yep but there's a function call "becase" it is a function, while the
current one is inlined. I really have no idea how much time is spent
on that though.
The other detail is that even when available on the computer the
__builtin_popcount is not automatically replaced by the corresponding
instruction -- at least it was not on my former tests. To force it, I
had to add a flag to the top of the Cython file, to force the compiler
to use the -mpopcnt option. But of course if we do this on a computer
that does not support the instruction.... ---> BOOM :-p
Nathann
Dima Pasechnik
Nathann
Nathann Cohen
> I'm sure this is configurable, and it should be configured, when building
> Sage.
Hmmm. That would be GREAT. Definitely worth asking the wise guys
working on Cython.
> And, calling a (very fast) function is faster than using your code, anyway,
> IMHO.
Nonono, I remember I really put this method instead of the builtin one
because it made a difference !
And I did not write this popcount myself, I found it on the (many)
pages on which everybody contributes with his own version of that code
:-D
I just checked it for consistency against __builtin just to be sure :-)
Nathann
Julien Puydt
> And I did not write this popcount myself, I found it on the (many)
> pages on which everybody contributes with his own version of that code
> :-D
Copyright issue?
Snark on #sagemath
Nathann Cohen
For 4 lines of code in a forum thread, given as an answer to a guy
asking "how to code a popcount efficiently" ?
If this can be a copyright issue, by itself it is sufficient to say
that we would be better without copyrights :-p
Nathann
Julien Puydt
I stupidly ran "rm -rf sage-4.8" in the terminal which pointed to
sage-4.8 full install thinking it was the terminal which pointed to
sage-4.8 spkg sources, so I had to rebuild from scratch. Sigh.
Anyway, I finally have sage-4.8 again on that box, and the result of
using the builtin popcount is that it still doesn't work.
Where do we go from that point on?
Snark on #sagemath
Nathann Cohen
> Anyway, I finally have sage-4.8 again on that box, and the result of using
> the builtin popcount is that it still doesn't work.
>
> Where do we go from that point on?
Hmmm O_o
Well, I read the code again and the only weird thing I was able to
find was that : the function find_order defined in
vertex_separation.pyx should have a "cdef int next_set" somewhere,
otherwise the variable is considered as a Python variable. Well, it is
bad from a performance point of view, and perhaps it could also make a
difference there... Could you try adding this cdef int next_set at the
beginning of the function, just to check ? O_o
Nathann
Willem Jan Palenstijn
Is char signed or unsigned on your platform?
If unsigned, vertex_separation.pyx will have some problems.
Does the compiler show any warnings when compiling this file, by the way?
-Willem Jan
Julien Puydt
I added it, and the problem is still there.
Snark on #sagemath
Julien Puydt
> On Fri, Jan 27, 2012 at 02:05:25PM +0100, Julien Puydt wrote:
>> Le 26/01/2012 10:53, Dima Pasechnik a �crit :
>>> Is the popcount() there even big-endian/little-endian safe?
>>> It's not obvious. As well, it will blow on architectures that have
>>> a different from x86 idea about the length of int...
>>> So one quick test would be to use __builtin_popcount(i) and see if it
>>> makes a difference...
>>
>> I stupidly ran "rm -rf sage-4.8" in the terminal which pointed to
>> sage-4.8 full install thinking it was the terminal which pointed to
>> sage-4.8 spkg sources, so I had to rebuild from scratch. Sigh.
>>
>> Anyway, I finally have sage-4.8 again on that box, and the result of
>> using the builtin popcount is that it still doesn't work.
>>
>> Where do we go from that point on?
>
> Is char signed or unsigned on your platform?
Good question ; how do I find out?
> If unsigned, vertex_separation.pyx will have some problems.
Why?
> Does the compiler show any warnings when compiling this file, by the way?
None.
Snark on #sagemath
Julien Puydt
> Le 27/01/2012 16:52, Willem Jan Palenstijn a �crit :
>
> Good question ; how do I find out?
If I put the following in test.c :
#include <limits.h>
#include <stdio.h>
int
main()
{
printf ("%d\n", CHAR_MIN);
return 0;
}
then compile and run it, I get 0 ; so I guess it's unsigned.
Snark on #sagemath
Willem Jan Palenstijn
Indeed. That will mean that the initialization of neighborhoods to (char)-1
will have the effect that the check
if neighborhoods[current] < 0:
fails because (char)-1 is positive, which will no doubt cause the algorithm to
break completely.
-Willem Jan
Julien Puydt
I added a few "unsigned" keywords here and there and got the test right!
I'll open a ticket with a nice patch as soon as I'll have cleaned things
a little.
Thanks for the help!
Snark on #sagemath
Dima Pasechnik
Nathann Cohen
I'm almost scared right now O_O
Nathann
Julien Puydt
> Wait... It means that on your platform the default "char" are unsigned ? O_o
>
> I'm almost scared right now O_O
You'll be happy to learn (eh, I just learnt it this very afternoon) that
the C standards says that char can be either "unsigned char" or "signed
char"... so if you want to be safe, just use the most precise form.
Here is the ticket with the promised patch and a few remarks :
http://trac.sagemath.org/sage_trac/ticket/12371
Snark on #sagemath
Julien Puydt
> Perhaps some other doctest failures on ARM are also related to unsigned
> char business? E.g. the pickling problem might be also due to this
> messing with bits....
I'll get to this pickling problem sooner or later ; I've known it to be
there ever since my first successful compilation... but never found the
time to dig the matter.
Snark on #sagemath
Nathann Cohen
>
> You'll be happy to learn (eh, I just learnt it this very afternoon) that the
> C standards says that char can be either "unsigned char" or "signed char"...
> so if you want to be safe, just use the most precise form.
Ok now I'm scared O_O;;;
> Here is the ticket with the promised patch and a few remarks :
> http://trac.sagemath.org/sage_trac/ticket/12371
Nice ! Could I *pleaaaaase* ask you to add the "cdef int next_set" I
mentionned in my previous post ? I'd put it secretly in another patch
otherwise but I'm sure I would eventually forget ^^;
Nathann
Julien Puydt
Well, no : this is an independent change and hence needs an independent
patch.
But perhaps a patch to :
1. change those "int" uses where it's known to really be an "unsigned
char" between 0 and the cardinal of the graph
1. add a "cdef unsigned char next_set" as an aside but related fix
in a new ticket will suit you?
Snark on #sagemath
Nathann Cohen
> patch.
Oh. Ok, well, it was juste one line and changed nothing to the code's behaviour.
> between 0 and the cardinal of the graph
> 1. add a "cdef unsigned char next_set" as an aside but related fix
>
> in a new ticket will suit you?
Well, replacing "int" by "unsigned char" will not be a huge memory
saving and will not help make the code easier to read either ^^;
I will add this line in another patch, it is not important :-)
Nathann
Volker Braun
Julien Puydt
> Instead of sprinkling "unsigned" around until it works,
Well, that's not exactly what happened.
Once it was recognized that the problem was that the code was using
"char" thinking it meant "signed char" and that was wrong (surprise!),
then I checked each use of "char" to see if it was meant to be a signed
or unsigned one, and added the appropriate keyword. It's only when I was
finished that I ran the test -- and got a positive result.
That means the test passes on my platform, and certainly on all others,
as a consequence of a deliberate fix, not a series of random changes
with a halting condition as you seem to assume.
I hope these precisions will calm your anxiety on the matter,
Snark on #sagemath