Opened 7 years ago

Closed 7 years ago

#17819 closed enhancement (fixed)

Use unsigned long for Integer.divisors

Reported by: jdemeyer Owned by:
Priority: minor Milestone: sage-6.6
Component: c_lib Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers: François Bissey
Report Upstream: N/A Work issues:
Branch: 1194cb7 (Commits, GitHub, GitLab) Commit: 1194cb75acb96340b16f9a256aa55e0a3c2eb38c
Dependencies: #17794, #10257 Stopgaps:

Status badges

Description (last modified by jdemeyer)

The divisors method of Integer is implemented using long long if possible. However, it would be better to use unsigned long for this. One advantage is that we no longer need the mpz_set_longlong() functions from c_lib. This will also be faster for small inputs on 32-bit systems. On 64-bit systems, there should be no speed difference (except perhaps a small speed-up due to skipping the mpz_longlong overhead and the fact that we use 64 instead of 63 bits).

Change History (28)

comment:1 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 7 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/17819

comment:3 Changed 7 years ago by jdemeyer

  • Commit set to fae8cecadc86555f7962a903bb686f2727ff2f58
  • Status changed from new to needs_review

New commits:

fae8cecUse uintmax_t for Integer.divisors

comment:4 Changed 7 years ago by git

  • Commit changed from fae8cecadc86555f7962a903bb686f2727ff2f58 to 6f851b9eb96f73930aa265673679434eecfac6a6

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

6ba47f0Merge remote-tracking branch 'origin/develop' into ticket/10257
307e526Revert raise MemoryError changes from #12212
cd8407bMerge branch 'ticket/12212_revert_raise' into ticket/10257
fa0612dMerge remote-tracking branch 'origin/develop' into ticket/10257
c561e2eFix check_allocarray() failure doctest on OS X
6650ca7Add csage dependencies in Makefile
c37e933Merge ticket/17794 into ticket/10257
352ffb8Remove check for -1
5e3901dMerge ticket/10257 into ticket/17819
6f851b9Use check_allocarray() to allocate array

comment:5 Changed 7 years ago by jdemeyer

  • Dependencies set to #17794, #10257

comment:6 Changed 7 years ago by git

  • Commit changed from 6f851b9eb96f73930aa265673679434eecfac6a6 to 3bc79b71b49aa37b7307174f29e228a6c2bc81f6

Branch pushed to git repo; I updated commit sha1. New commits:

3bc79b7Merge remote-tracking branch 'origin/develop' into ticket/17819_

comment:7 Changed 7 years ago by fbissey

That sucks. mpz_set_ux isn't in gmp - at least gmp 5.1.3, if you know it is in 6.0.0+ I at least can force an upgrade in sage-on-gentoo. But right now it is a major headache for sage-on-distro (much more so than pari git master).

comment:8 Changed 7 years ago by jdemeyer

Indeed, those functions seem MPIR-specific. For me personally, that's not an issue (we do use MPIR after all in Sage).

comment:9 Changed 7 years ago by fbissey

I know it would be less of an issue if other gmp using code had moved to using mpir directly one way or another (flint being the only one) rather than just saying "you can do that if mpir is installed with gmp-compat". I think I can do an ugly hack for that one.

comment:10 follow-up: Changed 7 years ago by jdemeyer

You mean there would be less an issue if more code relied on MPIR?

comment:11 in reply to: ↑ 10 Changed 7 years ago by fbissey

Replying to jdemeyer:

You mean there would be less an issue if more code relied on MPIR?

Well that would force the hand.

What I mean is take pari. You can compile it with mpir by using the gmp compatibility layer. You cannot tell pari to compile directly against mpir, using mpir headers and libmpir.

If all the packages in the sage stack could do that. It would be easy, install mpir and build everything against it. Reality is everything apart from flint is using gmp and expect gmp. And only use mpir if it is masquerading itself as gmp.

In a distro where gmp is already installed because of gcc it won't happen unless you can convince the toolchain team of the distro to switch to mpir. Tough job.

Last edited 7 years ago by fbissey (previous) (diff)

comment:12 follow-up: Changed 7 years ago by jdemeyer

We could also replace uintmax_t by unsigned long which is usually the same on 64-bit systems and which doesn't have portability issues.

comment:13 in reply to: ↑ 12 ; follow-up: Changed 7 years ago by fbissey

Replying to jdemeyer:

We could also replace uintmax_t by unsigned long which is usually the same on 64-bit systems and which doesn't have portability issues.

I guess that would be handy but what happens on 32 bits systems? We are still dealing with them for the foreseeable future.

I am trying a hack where integer.pyx and mpz.pxd explicitly use mpir. But not anything else.

I am guessing if mpir is a complete superset of gmp I could switch the whole sage library to explicit mpir. A bit of linking madness but it would work.

comment:14 in reply to: ↑ 13 Changed 7 years ago by jdemeyer

Replying to fbissey:

Replying to jdemeyer:

We could also replace uintmax_t by unsigned long which is usually the same on 64-bit systems and which doesn't have portability issues.

I guess that would be handy but what happens on 32 bits systems?

When using unsigned long, stuff would become slower for 32-bit systems. It's really a matter of what do you prefer? It's a classical pick 2 out of 3: clean code, fast code, portable code.

comment:15 Changed 7 years ago by fbissey

New hurdle, my hack didn't work because I have mpir 2.6.0 installed, I am guessing the symbol is in 2.7.0. I would have to update mpir as well to make it work.

Yes classic! And it would be nice if it was completed by 6.6 release. Portable gets sage-on-distro out of the hole for this time but it may not go on forever. At some point mpir and gmp may diverge enough that flint or sage will want to do something that is mpir only. That day I think the best thing to do will be to make mpir explicit, at least where it is needed, rather than faking gmp. And pray that linker do their job properly.

comment:16 Changed 7 years ago by fbissey

Upgraded mpir but it still fails. Inspecting libmpir with

nm -D /usr/lib64/libmpir.so.16 | grep mpz_set_ux
000000000002ea6e T __gmpz_set_ux

And I get the same thing with mpir built in vanilla sage (and the gmp in sage) everything seems to be prefixed with __g. Do you have an idea what is going on?

comment:17 Changed 7 years ago by fbissey

got it working by replacing every instances of gmp.h by mpir.h in sage/libs/gmp and replacing all gmp/gmpxx by mpir/mpirxx in module_list.py. Because c_lib, pari, ntl and friends are still linked to gmp I have linking to both gmp and mpir when inspecting with ldd, but readelf on the extension will only show mpir since it is the only one it is directly linked against.

Changing the headers in sage/libs/gmp wasn't enough in that it spread symbol problems in other places.

Now to run full doctest on the monster.

comment:18 follow-up: Changed 7 years ago by fbissey

doctest run as normally as expected for sage-on-gentoo on my machine. I was more or less expecting failures in the places where there are gmp(xx) headers outside of sage/libs/gmp but those seem to be more robust.

I would favor portability but that may be a discussion we need to have on sage-devel.

comment:19 in reply to: ↑ 18 ; follow-up: Changed 7 years ago by jdemeyer

Replying to fbissey:

I would favor portability but that may be a discussion we need to have on sage-devel.

What do you think of my proposal to use unsigned long? That would be portable and clean. On 64-bit there would be no difference.

For small inputs, using unsigned long will even be faster on 32-bit systems, since the compiler wouldn't need to emulate 64-bit long long operations. For larger inputs, there might be a slow-down but it might not be so bad given that there are no native 64-bit operations anyway.

comment:20 in reply to: ↑ 19 Changed 7 years ago by fbissey

Replying to jdemeyer:

Replying to fbissey:

I would favor portability but that may be a discussion we need to have on sage-devel.

What do you think of my proposal to use unsigned long? That would be portable and clean. On 64-bit there would be no difference.

For small inputs, using unsigned long will even be faster on 32-bit systems, since the compiler wouldn't need to emulate 64-bit long long operations. For larger inputs, there might be a slow-down but it might not be so bad given that there are no native 64-bit operations anyway.

I am OK with using unsigned long but it all gave me food for thought.

comment:21 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from needs_review to needs_work
  • Summary changed from Use uintmax_t for Integer.divisors to Use unsigned long for Integer.divisors

comment:22 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:23 Changed 7 years ago by git

  • Commit changed from 3bc79b71b49aa37b7307174f29e228a6c2bc81f6 to 1194cb75acb96340b16f9a256aa55e0a3c2eb38c

Branch pushed to git repo; I updated commit sha1. New commits:

1194cb7Use unsigned long instead of uintmax_t for divisors()

comment:24 Changed 7 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:25 follow-up: Changed 7 years ago by fbissey

mpz_set_ux is still in that patch but it looks like it links ok ok against gmp. Rebuilding and testing, but it should be good.

comment:26 in reply to: ↑ 25 Changed 7 years ago by jdemeyer

Replying to fbissey:

mpz_set_ux is still in that patch but it looks like it links ok ok against gmp. Rebuilding and testing, but it should be good.

I left the declaration indeed, but it doesn't hurt...

comment:27 Changed 7 years ago by fbissey

  • Reviewers set to François Bissey
  • Status changed from needs_review to positive_review

Definitely doesn't, good to go.

comment:28 Changed 7 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17819 to 1194cb75acb96340b16f9a256aa55e0a3c2eb38c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.