Flint 2.3: ARM and sage

[Julien Puydt]

Hi,

there are two questions I would like to discuss here.

The first is about flint and sage : the recently released sage 5.0 has flint 1.5.2 (with patches), and a separate 'flintqs' for the quadratic sieve program. Can flint 2.3 replace both simultaneously? [ie: is the rewrite good enough, and is it compatible?].

The second is again about flint 2.3, but more precisely about its ARM support : I compiled it successfully this morning on my ARM box (configure&make), but make check gave quite bad results : there are failing tests, and I finally had to kill the 'factor' test because it was so long I considered it stuck. Log is attached.

I hope that helps,

Snark on #sagemath

[Bill Hart]

On 18 May 2012 12:22, Julien Puydt <julien...@laposte.net> wrote:
> Hi,
>
> there are two questions I would like to discuss here.
>
> The first is about flint and sage : the recently released sage 5.0 has flint
> 1.5.2 (with patches), and a separate 'flintqs' for the quadratic sieve
> program. Can flint 2.3 replace both simultaneously? [ie: is the rewrite good
> enough, and is it compatible?].

Just about good enough. We are only waiting on the release to be
finished. Roughly speaking, here are the things that need to be done
for the release:

* Merge all known patches and issue a new alpha
* Put assembly code for Itanium/Itanium2 into longlong.h
* Do build system work to detect itanium machines
* Test flint 2.3 on Skynet
* Fix some reported bugs in the new flint FFT on 32 bit machines
* Do all the release paperwork
* Switch over to the new flint website Fredrik designed
* Release announcement

I actually sent an email off list to the main flint developers
yesterday announcing that all of this was now a priority for me. The
only thing stopping me announcing it on list is that the
flint-2.3-alpha is quite out-of-date.

>
> The second is again about flint 2.3, but more precisely about its ARM
> support : I compiled it successfully this morning on my ARM box
> (configure&make), but make check gave quite bad results : there are failing
> tests, and I finally had to kill the 'factor' test because it was so long I
> considered it stuck. Log is attached.

Thanks. We are aware of some problems with certain architectures. This
should be fixed soon (in fact, some fixes have already made it into
the repo).

>
> I hope that helps,
>
> Snark on #sagemath

I hope to have the new alpha up by about Monday. However, please be
aware that this will not fix all the known issues with flint. That
will take a little longer.

I do expect the release to be not far away now. As of yesterday I have
a clear period of 2-3 months to get some coding/research work done,
and flint-2.3 is the number one priority, followed closely by my FFT
contribution to the MPIR project (which flint will eventually use
instead of its own FFT).

Bill.

[Bill Hart]

By the way, if the ARM code is very slow, we can likely speed it up by
giving it the same assembly treatment in longlong.h as the Itanium.

[Fredrik Johansson]

Hi Julien,

Thanks for testing! I think most of the failures trace back to the
error in add_sssaaaaaa, which probably breaks matrix multiplication
(and thus everything else...).

This function must be using the generic fallback code on ARM. The
problem might be that the variable __x conflicts with the __x variable
in the add_ssaaaa macro. I do think I tested the fallback code on my
computer, but I might have missed this error if the x86 add_ssaaaa was
used.

Do the problems go away if you change __x to __t on lines 161, 162
and 164 in longlong.h? (You would need to make clean and recompile to
make sure the changes propagate.)

It would be even better to add ARM assembly for these functions, of course.

Fredrik

[Bill Hart]

Is that one of the new assembly functions? I thought it was an old
one, in which case it should definitely be correct.

Maybe the fallback code should be given another name and then only
aliased to the proper function name if it hasn't been defined in
assembly yet. Then we should add test code for the fallback code which
always runs.

Bill.

[Fredrik Johansson]

On Fri, May 18, 2012 at 2:09 PM, Bill Hart <goodwi...@googlemail.com> wrote:
> Is that one of the new assembly functions? I thought it was an old
> one, in which case it should definitely be correct.

add_ssaaaa is old, add_sssaaaaaa is new

Fredrik

[Bill Hart]

Ah, I see I misread what you wrote. The bug is that the new macro
possibly conflicts with the old.

[Fredrik Johansson]

The fallback add_sssaaaaaa is actually completely wrong and can't ever
have worked. My apologies.

I've pushed a version that should work:
https://github.com/fredrik-johansson/flint2/commit/a1835c939b2a9e1452b190be92cab4332f95ae3a

Fredrik

[Julien Puydt]

I'm willing to test again on ARM when the poor box will be finished compiling sage once again (count one or two days from now...) ; but where should I check it out? This github personal repository or the official one (if it answers -- the web view doesn't)?

Snark on #sagemath

[Bill Hart]

On 18 May 2012 17:27, Julien Puydt <julien...@laposte.net> wrote:
> On Friday, May 18, 2012 3:09:40 PM UTC+2, Fredrik Johansson wrote:
>>
>> The fallback add_sssaaaaaa is actually completely wrong and can't ever
>> have worked. My apologies.
>>
>> I've pushed a version that should work:
>>
>> https://github.com/fredrik-johansson/flint2/commit/a1835c939b2a9e1452b190be92cab4332f95ae3a
>
>
> I'm willing to test again on ARM when the poor box will be finished
> compiling sage once again (count one or two days from now...) ;

Thanks. That would be very helpful.

> but where
> should I check it out? This github personal repository or the official one
> (if it answers -- the web view doesn't)?
>

They should be one and the same. I've changed the flint website to
list my github repo as the canonical one.

Bill.

[Julien Puydt]

Hi,

On Friday, May 18, 2012 6:37:14 PM UTC+2, Bill Hart wrote:

On 18 May 2012 17:27, Julien Puydt wrote:
> but where
> should I check it out? This github personal repository or the official one
> (if it answers -- the web view doesn't)?
>

They should be one and the same. I've changed the flint website to
list my github repo as the canonical one.

The day started pretty bad : the checkout line on the homepage was wrong, and
the configure script didn't complain when I made a typo -- it looks like it doesn't
check anything, which is annoying.

Then the compilation went well :-)

Finally, the tests almost all passed -- a single one fails :
setbit....FAIL:
a = -1
b = -1
c = -1
j = 33
Aborted

Does that give enough information to fix that last issue?

Snark on #sagemath

[Bill Hart]

On 19 May 2012 17:59, Julien Puydt <julien...@laposte.net> wrote:
> Hi,
>
>
> On Friday, May 18, 2012 6:37:14 PM UTC+2, Bill Hart wrote:
>>
>> On 18 May 2012 17:27, Julien Puydt wrote:
>> > but where
>> > should I check it out? This github personal repository or the official
>> > one
>> > (if it answers -- the web view doesn't)?
>> >
>>
>> They should be one and the same. I've changed the flint website to
>> list my github repo as the canonical one.
>
>
> The day started pretty bad : the checkout line on the homepage was wrong,

I hope I have fixed that now. Please let me know if it still looks wrong to you.

> and
> the configure script didn't complain when I made a typo -- it looks like it
> doesn't
> check anything, which is annoying.

I will fix this shortly.

>
> Then the compilation went well :-)
>
> Finally, the tests almost all passed -- a single one fails :
> setbit....FAIL:
> a = -1
> b = -1
>
> c = -1
> j = 33
> Aborted
>
> Does that give enough information to fix that last issue?

Damn. This is code that I merged from Thomas, which is not ready to be
merged yet. But I backed out the merge. Somehow git doesn't do the
right thing when you back out a merge. You need to back out all the
individual commits as well, which seems stupid. I'm not even sure how
to fix this....

Anyhow, that code isn't meant to pass yet. I'll try to figure out a
way of backing out the commits properly. The problem is, the only ways
I know to do this mean that Thomas will have his code wiped out if he
merges from trunk.

>
> Snark on #sagemath

Bill.

[Fredrik Johansson]

On Sat, May 19, 2012 at 7:50 PM, Bill Hart <goodwi...@googlemail.com> wrote:
>> Finally, the tests almost all passed -- a single one fails :
>> setbit....FAIL:
>> a = -1
>> b = -1
>>
>> c = -1
>> j = 33
>> Aborted
>>
>> Does that give enough information to fix that last issue?
>
> Damn. This is code that I merged from Thomas, which is not ready to be
> merged yet. But I backed out the merge. Somehow git doesn't do the
> right thing when you back out a merge. You need to back out all the
> individual commits as well, which seems stupid. I'm not even sure how
> to fix this....
>
> Anyhow, that code isn't meant to pass yet. I'll try to figure out a
> way of backing out the commits properly. The problem is, the only ways
> I know to do this mean that Thomas will have his code wiped out if he
> merges from trunk.

Actually, fmpz_setbit is an old function (written by Sebastian).

Fredrik

[Bill Hart]

Ah thanks, I just discovered this. The new stuff from Thomas didn't go
in after all. So we will be able to fix this ok without affecting
Thomas' development.

Bill.

[Fredrik Johansson]

On Sat, May 19, 2012 at 8:02 PM, Bill Hart <goodwi...@googlemail.com> wrote:
> Ah thanks, I just discovered this. The new stuff from Thomas didn't go
> in after all. So we will be able to fix this ok without affecting
> Thomas' development.

Note that I've merged Thomas' code in my repository. There is just one
remaining problem: the config script to detect the popcnt instruction
doesn't quite work (at least on my laptop, it claims success even
though the popcnt is not available).

Fredrik

[Bill Hart]

OK. I'll wait until you are happy before merging from you again.

[Bill Hart]

On 19 May 2012 17:59, Julien Puydt <julien...@laposte.net> wrote:

Hmm. I think I need another pair of eyes on this:

* from the implementation in fmpz/setbit.c it seems that this function
sets the i-th bit (j in the test code) of the twos complement
representation of f to 1

* the test output (which corresponds to fmpz/test/t-testbit.c) seems
to start with a value _a_ which is eventually set to -1 (so the twos
complement representation is infinitely many 1s)

* if it started with the value -1, setting the 33rd bit would have no
effect, and following the code through, I think it should give the
right answer

* if it started with the 33rd bit set to 0 and all other bits set to 1
(and it is a 32 bit machine), then it should take two limbs to store
the initial value, but only 1 small fmpz to store the -1 result. But
following the code through, it seems that it never demotes the 1 limb
mpz to an fmpz small.

Thus I think adding _fmpz_demote_val(f); in the final branch of the
testbit function should fix this error.

I'll commit that now, and perhaps Julien can tell us if this fixes the problem.

Bill.

[Sebastian Pancratz]

>> Finally, the tests almost all passed -- a single one fails :
>> setbit....FAIL:
>> a = -1
>> b = -1
>>
>> c = -1
>> j = 33
>> Aborted
>>
>> Does that give enough information to fix that last issue?
>
> Hmm. I think I need another pair of eyes on this:

I was just looking at it now, too. I have pushed a minor modification
to my github repository, which may or may not fix the issue.
Essentially, the problem could be that a call to setbit might actually
decrease the value for large negative values on input. It is not clear
here what the original input was in this case, so I've also modified the
test code to change this.

> * from the implementation in fmpz/setbit.c it seems that this function
> sets the i-th bit (j in the test code) of the twos complement
> representation of f to 1
>
> * the test output (which corresponds to fmpz/test/t-testbit.c) seems
> to start with a value _a_ which is eventually set to -1 (so the twos
> complement representation is infinitely many 1s)
>
> * if it started with the value -1, setting the 33rd bit would have no
> effect, and following the code through, I think it should give the
> right answer
>
> * if it started with the 33rd bit set to 0 and all other bits set to 1
> (and it is a 32 bit machine), then it should take two limbs to store
> the initial value, but only 1 small fmpz to store the -1 result. But
> following the code through, it seems that it never demotes the 1 limb
> mpz to an fmpz small.
>
> Thus I think adding _fmpz_demote_val(f); in the final branch of the
> testbit function should fix this error.

Ah, yes, the same thought.

Sebastian

[Bill Hart]

OK. I pushed and pulled your repo because I didn't have your test code
fix. So if you pull from me again you'll get the merge.

Bill.

On 19 May 2012 19:36, Sebastian Pancratz

[Bill Hart]

On 19 May 2012 17:59, Julien Puydt <julien...@laposte.net> wrote:

> Hi,
>
>
> On Friday, May 18, 2012 6:37:14 PM UTC+2, Bill Hart wrote:
>>
>> On 18 May 2012 17:27, Julien Puydt wrote:
>> > but where
>> > should I check it out? This github personal repository or the official
>> > one
>> > (if it answers -- the web view doesn't)?
>> >
>>
>> They should be one and the same. I've changed the flint website to
>> list my github repo as the canonical one.
>
>
> The day started pretty bad : the checkout line on the homepage was wrong,
> and
> the configure script didn't complain when I made a typo -- it looks like it
> doesn't
> check anything, which is annoying.

Could you be more explicit about this. It rejects invalid directories
for me. Was it some other kind of typo?

[Fredrik Johansson]

On Sat, May 19, 2012 at 8:06 PM, Bill Hart <goodwi...@googlemail.com> wrote:
> OK. I'll wait until you are happy before merging from you again.

I've pushed a possible fix. The test program tried to execute
__builtin_popcountl(0x0), which somehow succeeded. Might be that GCC
constant-folded it. So I changed it to compute the popcount of argc
instead. Needs checking on other machines.

Fredrik

[Julien Puydt]

On Saturday, May 19, 2012 8:45:22 PM UTC+2, Bill Hart wrote:

On 19 May 2012 17:59, Julien Puydt wrote:
> the configure script didn't complain when I made a typo -- it looks like it
> doesn't
> check anything, which is annoying.

Could you be more explicit about this. It rejects invalid directories
for me. Was it some other kind of typo?

The kind of typo where I sent it into another directory entirely (I was thinking
about something else...) : the configure script checks the existence and the fact
that it's a directory, it doesn't check that it actually contains what you want.

So it was invalid, but not so trivially so.

Snark on #sagemath

[Bill Hart]

I think I can trivially fix this by looking for libflint.dylib,
libflint.so or libflint.a, one of which must be present for it to be a
valid directory. Same for mpfr.

I've got to go out now, but I've added this to my todo list and will
fix it for the release, I think.

Bill.

[Bill Hart]

Ahem, I mean libmpir.dylib, etc, not libflint.dylib.

Bill.

[Julien Puydt]

On Friday, May 18, 2012 1:22:55 PM UTC+2, Julien Puydt wrote:

The first is about flint and sage : the recently released sage 5.0 has flint 1.5.2 (with patches), and a separate 'flintqs' for the quadratic sieve program. Can flint 2.3 replace both simultaneously? [ie: is the rewrite good enough, and is it compatible?].

I just compiled flint2's git on my X86_64 box -- where is the quadratic sieve program? I had understood from this sage bug report  that it was included in flint directly, but peeking in the Makefiles, I only find the library...

Snark on #sagemath

[Bill Hart]

The flint-1.6 that ships with sage currently does have a much more
recent quadratic sieve.

The more recent version in flint-1.6 has a small and a large quadratic sieve.

The small quadratic sieve has been ported to flint2 for 64 bit
machines, but I still need to make some adjustments to make it work on
32 bit machines, and the large quadratic sieve remains unported. It is
on my todo list for the near to medium term though. So it will be
available soon.

It's not trivial to port, because I am completely rewriting it to work
around some limitations that the version in flint 1.6 has. The code is
also not up to flint2 standard. So hopefully it will be worth the
wait. :-)

Oddly enough, I found the oldest version of my quadratic sieve (called
SIMPQS, basically the same as the one in sage: see
http://www.friedspace.com/QS/ ) mentioned in a book on Number Theory I
was reading the other day.

Bill.

[Julien Puydt]

On Saturday, May 19, 2012 6:59:46 PM UTC+2, Julien Puydt wrote:

Finally, the tests almost all passed -- a single one fails :
setbit....FAIL:
a = -1
b = -1
c = -1
j = 33
Aborted

All checks pass :-)

Snark on #sagemath

[Bill Hart]

I have added some ARM assembly code (though not add_ssssaaaaaa). I
haven't been able to test it, as all the ARM machines I have access to
are down at the moment.

If you get a chance a test of the latest trunk would be great. You'll
need to run configure again and make -B, but only the first few sets
of tests from make check need be run, as that will tell us immediately
if the code is correct.

Bill.