[Sbcl-devel] SB-GMP status

[Stephan Frank]

Hi everybody,

SB-GMP [1] appears now to be stabilized, so that I'd like to request
comments on what should be changed or expanded for an inclusion as a
contrib. There is already a related interface included in Fricas though
it requires an additional C interface and is not as exhaustive.

There were also a couple of corner cases that popped up during random
testing of which I'm not sure whether/how they are handled by the
Fricas-internal version.

The code has been tested with GMP 5.0.5/5.1 (version 4.x is not
supported) and the latest SBCL on Linux (64 and 32 bit variants). The
DLL-loading case for Windows has not been tested, so I'd appreciate some
feedback on that as well.

Regs,
Stephan

[1] https://github.com/sfrank/sb-gmp

------------------------------------------------------------------------------
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Christophe Rhodes]

Stephan Frank <crim...@cs.tu-berlin.de> writes:

> SB-GMP [1] appears now to be stabilized, so that I'd like to request
> comments on what should be changed or expanded for an inclusion as a
> contrib. There is already a related interface included in Fricas though
> it requires an additional C interface and is not as exhaustive.

I can see the value of including this -- there's clearly a need, given
the Fricas case as well as this (is this independently developed? Or
does it related in any way to the older work by Waldek Hebisch?)

In terms of what needs doing before merging, for contribs I'm not
inclined to be too fussy -- they are optional, and can afford to be a
bit more experimental than changes to the main body. Perhaps most
important might be to think about medium-term commitment -- is this
something that you use?

Cheers,

Christophe

------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may

[crim...@cs.tu-berlin.de]

> Stephan Frank <crim...@cs.tu-berlin.de> writes:
>
>> SB-GMP [1] appears now to be stabilized, so that I'd like to request
>> comments on what should be changed or expanded for an inclusion as a
>> contrib. There is already a related interface included in Fricas though
>> it requires an additional C interface and is not as exhaustive.
>
> I can see the value of including this -- there's clearly a need, given
> the Fricas case as well as this (is this independently developed? Or
> does it related in any way to the older work by Waldek Hebisch?)

I had played with the idea for some time and Paul's GSoC idea sparked my
interest anew. It uses the same idea as Waldek's approach though doesn't
need a C shim and provides a more comprehensive coverage both wrt. bignum
operations transparently relayed to GMP and interfaced GMP functionality.
Furthermore, I think that I have covered more corner cases which I think
aren't handled by the version in Fricas (I haven't tried but I did look
for solutions there once I discovered the bugs and didn't find anything).
At the moment I am not aware of any bugs in the core functionality (the
one covered in the test suite) and have run a large number of randomly
generated tests on 32 and (primarily) 64 bit Linux.

>
> In terms of what needs doing before merging, for contribs I'm not
> inclined to be too fussy -- they are optional, and can afford to be a
> bit more experimental than changes to the main body. Perhaps most
> important might be to think about medium-term commitment -- is this
> something that you use?

I will use some of the functionality and am quite certain that Maxima
should see a nice speedup for operations on large bignums and rationals.
There was also interest from another student(?, sorry can't access my mail
archive at the moment) to expand with covering MPFR as well, since there
is quite some overlap. Apparently this would be useful for matlisp as
currently under development.

If you think it is too experimental I can go the Quicklisp route; however,
since it is SBCL specific and can replace/enhance internal functionality I
figured a contrib would be a better fit.

Regs,
Stephan

[Gabriel Dos Reis]

On Fri, May 24, 2013 at 8:59 AM, Christophe Rhodes <cs...@cantab.net> wrote:
> Stephan Frank <crim...@cs.tu-berlin.de> writes:
>
>> SB-GMP [1] appears now to be stabilized, so that I'd like to request
>> comments on what should be changed or expanded for an inclusion as a
>> contrib. There is already a related interface included in Fricas though
>> it requires an additional C interface and is not as exhaustive.
>
> I can see the value of including this -- there's clearly a need, given
> the Fricas case as well as this (is this independently developed? Or
> does it related in any way to the older work by Waldek Hebisch?)

I have not gone through the trouble of duplicating Waldek's work
but if it is made a standard package pf SBCL (which is the default
Lisp for OpenAxiom on many supported platform) it would be
of immense value.

-- Gaby

[Paul Khuong]

crim...@cs.tu-berlin.de wrote:
>> Stephan Frank<crim...@cs.tu-berlin.de> writes:
>>
>>> SB-GMP [1] appears now to be stabilized, so that I'd like to request
>>> comments on what should be changed or expanded for an inclusion as a
>>> contrib. There is already a related interface included in Fricas though
>>> it requires an additional C interface and is not as exhaustive.

[...]

> At the moment I am not aware of any bugs in the core functionality (the
> one covered in the test suite) and have run a large number of randomly
> generated tests on 32 and (primarily) 64 bit Linux.

Sounds good enough to me, for an experimental contrib. An independent
desk check would be good, but I wouldn't want to see something like this
held up by a collective lack of free time.

>> In terms of what needs doing before merging, for contribs I'm not
>> inclined to be too fussy -- they are optional, and can afford to be a
>> bit more experimental than changes to the main body. Perhaps most
>> important might be to think about medium-term commitment -- is this
>> something that you use?
>
> I will use some of the functionality and am quite certain that Maxima
> should see a nice speedup for operations on large bignums and rationals.

OK. And we can bug you if something goes horribly wrong in the coming
couple months? (:

So, it's been a couple weeks since I looked at your repository, but
here's the list I last had of issues/things to look at before merging:

1. Enable GMP automatically when the contrib is loaded;
2. Make sure the enable/disable GMP functions work when used multiple
times in a row or concurrently (re-entrancy isn't a big deal for me);
3. Make sure the contrib is safe to be loaded multiple times in the same
image;
4. (Not sure) toggle the use of GMP via a special variable. This could
be useful to improve performance, look for bugs, and eventually expose
multiple switch-over policies... and a special binding is thread-safe,
unlike global redefinitions;
5. What happens after a core is saved? Can it degrade gracefully in the
absence of libgmp when it's thawed?

1, 2 and 3 would be blocking issues for me. 4 and 5 are nice to have,
but could be addressed in a later release. I'll try to take a second
look and send some pull requests later this week, but no promise.

> There was also interest from another student(?, sorry can't access my mail
> archive at the moment) to expand with covering MPFR as well, since there
> is quite some overlap. Apparently this would be useful for matlisp as
> currently under development.

MPFR would be something else altogether. Extending the meaning of
standard CL types would be an interesting journey through both the spec
and Python.

Paul Khuong

------------------------------------------------------------------------------
This SF.net email is sponsored by Windows:

Build for Windows Store.

http://p.sf.net/sfu/windows-dev2dev

[crim...@cs.tu-berlin.de]

OK, can be done easily.

> 2. Make sure the enable/disable GMP functions work when used multiple
> times in a row or concurrently (re-entrancy isn't a big deal for me);

According to the documentation GMP is reentrant safe, if not explicitly
configured with --enable-alloca=malloc-notreentrant. The older, deprecated
and non-safe, functions are not part of SB-GMP interface. Since the
interface functions allocate new bignums I think we should be fine. The
only problem is the use of the same random state in different threads,
though this is the same problem one has in a pure Lisp context as well.

> 3. Make sure the contrib is safe to be loaded multiple times in the same
> image;

OK.

> 4. (Not sure) toggle the use of GMP via a special variable. This could
> be useful to improve performance, look for bugs, and eventually expose
> multiple switch-over policies... and a special binding is thread-safe,
> unlike global redefinitions;

This would be an additional if in the call functions, i.e. all the gmp-...
functions at the end of gmp.lisp. Do we really want that? On can uninstall
the transparent integration via (uninstall-gmp-funs) though I admit that
is not as comfortable and elegant as binding a special variable.

> 5. What happens after a core is saved? Can it degrade gracefully in the
> absence of libgmp when it's thawed?

OK, will have to think about that. Are there any standard solutions to
this problem?

>
> 1, 2 and 3 would be blocking issues for me. 4 and 5 are nice to have,
> but could be addressed in a later release. I'll try to take a second
> look and send some pull requests later this week, but no promise.
>
>> There was also interest from another student(?, sorry can't access my
>> mail
>> archive at the moment) to expand with covering MPFR as well, since there
>> is quite some overlap. Apparently this would be useful for matlisp as
>> currently under development.
>
> MPFR would be something else altogether. Extending the meaning of
> standard CL types would be an interesting journey through both the spec
> and Python.

I have continued on this road though have not pushed anything yet. I will
probably wait until the first version with bignum-only support is merged.
For the moment there is no transparent integration with the standard CL
functions or floating-point types.

Regs,
Stephan

[Paul Khuong]

crim...@cs.tu-berlin.de wrote:
[...]

>> So, it's been a couple weeks since I looked at your repository, but
>> here's the list I last had of issues/things to look at before merging:
>>

[...]

>> 2. Make sure the enable/disable GMP functions work when used multiple
>> times in a row or concurrently (re-entrancy isn't a big deal for me);
>
> According to the documentation GMP is reentrant safe, if not explicitly
> configured with --enable-alloca=malloc-notreentrant. The older, deprecated
> and non-safe, functions are not part of SB-GMP interface. Since the
> interface functions allocate new bignums I think we should be fine. The
> only problem is the use of the same random state in different threads,
> though this is the same problem one has in a pure Lisp context as well.

I was thinking of install-gmp-funs/uninstall-gmp-funs, actually. The
lock/unlock package logic looks like it wants a mutex on threaded builds.

I also worry about two libraries installing and uninstalling gmp-funs.
That's why I think the contrib should enable by itself, and offer a
local way to disable/re-enable. If that's around, install-gmp-fun and
uninstall-gmp-funs can be %-prefixed and only exposed for people who
*really* know what they're doing.

I trust GMP itself to be thread-safe ;) As for the random state, it
seems to me the interface works with an explicit state argument. That's
good enough for me.

>> 4. (Not sure) toggle the use of GMP via a special variable. This could
>> be useful to improve performance, look for bugs, and eventually expose
>> multiple switch-over policies... and a special binding is thread-safe,
>> unlike global redefinitions;
>
> This would be an additional if in the call functions, i.e. all the gmp-...
> functions at the end of gmp.lisp. Do we really want that? On can uninstall
> the transparent integration via (uninstall-gmp-funs) though I admit that
> is not as comfortable and elegant as binding a special variable.

(Actually, the special variable lookup is likely to have more of an
impact than a branch ;) If we only perform a special lookup before
calling out to C, I'm pretty sure the difference will be noise. It's
just that I don't see any other way to enable the changes in a single
thread, and extremely well-behaved libraries might want to do that.

>> 5. What happens after a core is saved? Can it degrade gracefully in the
>> absence of libgmp when it's thawed?
>
> OK, will have to think about that. Are there any standard solutions to
> this problem?

I think sb-alien automatically reloads libraries on restart, but that
doesn't work very well if the paths have changed (e.g. we're running on
a different machine). We have sb-ext:*save-hooks* and
sb-ext:*init-hooks*; they would be useful to disable GMP before saving,
and to try and re-enable it during reinitialisation.

>> MPFR would be something else altogether. Extending the meaning of
>> standard CL types would be an interesting journey through both the spec
>> and Python.
>
> I have continued on this road though have not pushed anything yet. I will
> probably wait until the first version with bignum-only support is merged.
> For the moment there is no transparent integration with the standard CL
> functions or floating-point types.

This would easily be useful. I'm not sure that transparent magic is a
win here, but I can easily see something like sb-mpfr:+ that downgrades
to cl:+ at compile-time depending on derived argument types.

Paul Khuong

[Stephan Frank]

Hi Paul,

I think items 1-4 are taken care of now (though I'll run some further
tests). However, I'm still unsure about item 5. Resolving an absent
libgmp.so gracefully will mostly reimplement functionality of
SB-ALIEN::TRY-REOPEN-SHARED-OBJECT by disabling an automatic reload
during saved core startup.

One can make it more gracefully wrt. the path of the shared lib with the
patch at
http://sshrkv.tumblr.com/post/15166254306/reloading-dynamic-libraries-from-saved-sbcl-cores

>From your POV shall I proceed in this direction or can we live with an
error when no libgmp.so can be found during loading of the saved core.

Regs,
Stephan

PS: I also accidentally pushed the current state of mpfr.lisp and didn't
bother to roll back. Though it is not loaded by the ASDF system file and
only has very low-level functionality at the moment.

[Stephan Frank]

Hi James,

congratulations on being the first user! I have added one of your
failing test cases to the test suite as mpq-lmj, however I cannot
reproduce it here (32 and 64 bit environment). Since all failures are
within the rational code I had a look at the GMP release notes. For GMP
5.0.3 there is this:

* A bug in division code possibly causing incorrect computation was fixed.

Could please you try again with GMP >= 5.0.3 ?

Regards,
Stephan

On 06/12/2013 11:39 PM, James M. Lawrence wrote:
> Hi,
>
> diff --git a/gmp.lisp b/gmp.lisp
> index 8ce2900..c8a5c6a 100644
> --- a/gmp.lisp
> +++ b/gmp.lisp
> @@ -838,7 +838,7 @@ be (1+ COUNT)."
> "Mutex for installation from different threads.")
>
> (defun install-gmp-funs ()
> - (sb-thread:with-mutex (*gmp-mutex*)
> + (sb-thread:with-recursive-lock (*gmp-mutex*)
> (when *gmp-installed*
> (uninstall-gmp-funs))
> (sb-ext:unlock-package "SB-BIGNUM")
> @@ -859,7 +859,7 @@ be (1+ COUNT)."
> (sb-ext:lock-package "COMMON-LISP")))
>
> (defun uninstall-gmp-funs ()
> - (sb-thread:with-mutex (*gmp-mutex*)
> + (sb-thread:with-recursive-lock (*gmp-mutex*)
> (setf *gmp-installed* nil)
> (sb-ext:unlock-package "SB-BIGNUM")
> (setf (symbol-function 'sb-bignum::multiply-bignums)
> (symbol-function 'orig-mul))
>
> (I tend to avoid recursive locks, but this is a simple case.)
>
> Attached is the test output for sbcl-1.1.8 Linux xi
> 3.2.0-24-generic-pae #39-Ubuntu SMP Mon May 21 18:54:21 UTC 2012 i686
> i686 i386 GNU/Linux
>
> sb-gmp:*gmp-version* => "5.0.2"
>
> Best,
> lmj

>


------------------------------------------------------------------------------
This SF.net email is sponsored by Windows:

Build for Windows Store.

http://p.sf.net/sfu/windows-dev2dev

[Paul Khuong]

Stephan Frank wrote:
> Hi James,
>
> congratulations on being the first user! I have added one of your
> failing test cases to the test suite as mpq-lmj, however I cannot
> reproduce it here (32 and 64 bit environment). Since all failures are
> within the rational code I had a look at the GMP release notes.

I sent a fairly hefty (sorry) pull request on github. Of the 20 commits,
https://github.com/pkhuong/sb-gmp/commit/eec6b2ad710dd337365cec75c9dc6eaf0963e61d
fixes a bug in all rational arithmetic operations involving negative values.

If tests fail on small values,
https://github.com/pkhuong/sb-gmp/commit/bccdbf5a6d7bcb7cbe2ad1fb303d5b2a98051637
fixed a ton of such failures for me.

Paul Khuong

[James M. Lawrence]

I didn't see a change after upgrading to gmp-5.1.2. pkhuong's branch
worked with the old and new gmp (his sb-gmp-test.asd needs updating:
"test" -> "tests", remove fiveam, add sb-rt).

[Paul Khuong]

James M. Lawrence wrote:
> I didn't see a change after upgrading to gmp-5.1.2. pkhuong's branch
> worked with the old and new gmp (his sb-gmp-test.asd needs updating:
> "test" -> "tests", remove fiveam, add sb-rt).

Good! (and I forgot to remove that file)

Paul Khuong

[Paul Khuong]

Stephan Frank wrote:
> I think items 1-4 are taken care of now (though I'll run some further
> tests). However, I'm still unsure about item 5. Resolving an absent
> libgmp.so gracefully will mostly reimplement functionality of
> SB-ALIEN::TRY-REOPEN-SHARED-OBJECT by disabling an automatic reload
> during saved core startup.

Some questions that popped up while I made some changes to SB-GMP
(nothing blocking for a commit from my POV, simply things to think about
for later):

1. In two places, you wrote "positive"; is that strictly positive, or
non-negative? Clearly, GMP-Z-TO-BIGNUM is the latter, but I'm not sure
for RAND-SEED.

2. What happens if we mistakenly allocate too little space for the
result? I seem to observe silent "success."

3. How does GMP handle error? Does it still just printf to stderr and
abort? (I see that it seems to signal a division by zero correctly, at
least)

4. mpz_mod ignores the divisor's sign. AFAICT, it's the only functions
that does so; is that right?

[crim...@cs.tu-berlin.de]

> Stephan Frank wrote:
>> I think items 1-4 are taken care of now (though I'll run some further
>> tests). However, I'm still unsure about item 5. Resolving an absent
>> libgmp.so gracefully will mostly reimplement functionality of
>> SB-ALIEN::TRY-REOPEN-SHARED-OBJECT by disabling an automatic reload
>> during saved core startup.
>
> Some questions that popped up while I made some changes to SB-GMP
> (nothing blocking for a commit from my POV, simply things to think about
> for later):
>
> 1. In two places, you wrote "positive"; is that strictly positive, or
> non-negative? Clearly, GMP-Z-TO-BIGNUM is the latter, but I'm not sure
> for RAND-SEED.

>= 0 is allowed (though 0 wouldn't really make sense)

> 2. What happens if we mistakenly allocate too little space for the
> result? I seem to observe silent "success."

You either get the wrong result (in very rare cases) or mostly land in ldb
where you likely (at least on Ubutnu) see the backtrace to the GMP
allocation function. Currently, all function were the max. required space
can be predetermined use SBCL-side allocation (this popped up frequently
in the beginning when I simply copied the buffer sized from Waldek; since
then I have looked at the GMP sources and have adjusted the SB-GMP buffer
allocation sizes), the others copy from a GMP allocated bignum (though
this is about factor 3 slower).

> 3. How does GMP handle error? Does it still just printf to stderr and
> abort? (I see that it seems to signal a division by zero correctly, at
> least)

Frankly, that is also one of the mysteries I have on my TODO to explore. I
checked for div-by-zero as well :-) and decided to check parameters on the
Lisp side to avoid things such as negative SQRT etc.

> 4. mpz_mod ignores the divisor's sign. AFAICT, it's the only functions
> that does so; is that right?

As far as I remember, this was the only function that I interfaced which
does this (according to the GMP manual).

Thanks for your bug fixing work, though I am quite puzzled why the bugs
didn't pop up with the three systems I tested on. I can only merge your
pull request tonight since there appear to be some conflicts and the web
interface can't handle this, so I need my development machine.

Regs,
Stephan

[crim...@cs.tu-berlin.de]

> Stephan Frank wrote:
>> I think items 1-4 are taken care of now (though I'll run some further
>> tests). However, I'm still unsure about item 5. Resolving an absent
>> libgmp.so gracefully will mostly reimplement functionality of
>> SB-ALIEN::TRY-REOPEN-SHARED-OBJECT by disabling an automatic reload
>> during saved core startup.
>
> Some questions that popped up while I made some changes to SB-GMP
> (nothing blocking for a commit from my POV, simply things to think about
> for later):
>
> 1. In two places, you wrote "positive"; is that strictly positive, or
> non-negative? Clearly, GMP-Z-TO-BIGNUM is the latter, but I'm not sure
> for RAND-SEED.
>
> 2. What happens if we mistakenly allocate too little space for the
> result? I seem to observe silent "success."

Previous answer was wrong; I remembered I related case: the second part
from the previous answer is correct; realloc is acalled with a pointer
into the SBCL heap for the bignum buffer, this barfs and lands in ldb.

[Stephan Frank]

Hi Paul,

On 06/14/2013 03:21 AM, Paul Khuong wrote:

And now, to answer your last remaining question:

> 3. How does GMP handle error? Does it still just printf to stderr and
> abort? (I see that it seems to signal a division by zero correctly, at
> least)

GMP either signals a SIGFPE for invalid operations such a SQRT on a
negative or SIGABORT when a memory allocation error occurs (i.e. for out
of memory situations). The former can be seen in the GMP-file invalid.c
(unfortunately this information is not explained in the manual and has
to be extracted from mailing list posts, sigh).

Regs,
Stephan

[Paul Khuong]

Stephan Frank wrote:
> I think items 1-4 are taken care of now (though I'll run some further
> tests). However, I'm still unsure about item 5. Resolving an absent
> libgmp.so gracefully will mostly reimplement functionality of
> SB-ALIEN::TRY-REOPEN-SHARED-OBJECT by disabling an automatic reload
> during saved core startup.

I merged the current state of your SB-GMP tree, with a couple local
tweaks (I renamed the features :sb-gmp[-5.0,-5.1], mostly), in 1656e54
(New contrib: SB-GMP).

Thank you very much! I'm sure there's lots more interesting work left ;)