Why do we put GMP allocations on GHC heaps?

newer
Dynamically loading and unloading...

Gergely Risko

22 Oct 2013 22 Oct '13

5:44 p.m.

Dear GHC gurus, I've been looking into how GHC uses GMP (with the hidden agenda of taking the work of replacing it with something that is BSD license compatible and so can be linked in and shipped statically by default). I think I more or less understand how GMP memory is managed and how the GC works together with it. Actually understanding the "how" was not that hard, everything is quite clearly commented. What I couldn't find any reference for is the "why". Why does GHC do this? Would it be possible to just not do this and let GMP malloc and free for itself (obviously we would have to call mpz_free here and there, but that seems doable). I have multiple ideas, but don't know which one (if any) is correct: - performance reasons, - memory defragmentation reasons, - GHC GC moves around stuff and that would somehow break, - the previous one + threads + race conditions. Second question: let's assume for a moment that we don't have any licensing issues with a GMP like library, can be linked statically into GHC, but we decide to go with the same allocation methodology as with GMP. Am I right when I think that linking statically solves the technical issues too. More concretely: openssl BN uses the openssl_malloc function can only be overridden openssl wide. But if we link statically, than this override won't affect external openssl library bindings, because the openssl symbols in our object files won't even be exported, right? Third question: is replacing with openssl bn an acceptable path to you guys? I saw that 6 years ago there were work on getting integer-simple performance wise good enough to be the default and then adding other bignum libraries externally, but none of this happened. I see how sexy project it is computer science wise to write a bignum library in Haskell, but will we really do it? Thanks, Gergely (errge)

Show replies by date

Edward Z. Yang

22 Oct 22 Oct

7:36 p.m.

Hey Gergeley,

...

(obviously we would have to call mpz_free here and there, but that seems doable).

Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector. The alternate strategy is to arrange that some sort of "callback" gets invoked when an object dies. You can achieve this using our finalizer support, but you pay an efficiency penalty and cannot guarantee that the integers will get freed in a timely manner at all.

...

More concretely: openssl BN uses the openssl_malloc function can only be overridden openssl wide. But if we link statically, than this override won't affect external openssl library bindings, because the openssl symbols in our object files won't even be exported, right?

Only if literally two copies of OpenSSL are linked. This seems unlikely to work the way you want it to. Cheers, Edward

Edward Kmett

8:26 p.m.

Not suggesting we actually switch, but there is one strong 'why': You can't link Haskell code with any library that uses GMP internally internally without switching to using integer-simple. I've been trying with very limited success to get good MPFR bindings for Haskell for ~3 years now as a result. The most likely fix actually involves changes to MPFR as their constant cache and our garbage collector don't play nice. On Tue, Oct 22, 2013 at 7:36 PM, Edward Z. Yang wrote:

...

Hey Gergeley,

...
(obviously we would have to call mpz_free here and there, but that seems doable).

Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector.

The alternate strategy is to arrange that some sort of "callback" gets invoked when an object dies. You can achieve this using our finalizer support, but you pay an efficiency penalty and cannot guarantee that the integers will get freed in a timely manner at all.

...
More concretely: openssl BN uses the openssl_malloc function can only be overridden openssl wide. But if we link statically, than this override won't affect external openssl library bindings, because the openssl symbols in our object files won't even be exported, right?

Only if literally two copies of OpenSSL are linked. This seems unlikely to work the way you want it to.

Cheers, Edward _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Carter Schonwald

9:29 p.m.

At some point I'd actually like to explore trying to build a satisfactory "integer-fancy" in Haskell, but there's a few technical challenges I'll be trying to do first before there'll be an engineering story for building a satisfactory Haskell replacement that is performant enough to justify dropping Gmp Basically I think until we can build an alternative with competitive performance in straight ghc Haskell, there's no good argument for dropping Gmp overall. There are a number of great reasons that everyone has mentioned, but it needs to be a net win for everyone before the leap could be justifiable. If I manage to get my target work for 7.10 sorted out with a few months to spare, I may try to spend a few months exploring this, though no promises. Current ghc doesn't have the right primops to do this yet. On Tuesday, October 22, 2013, Edward Kmett wrote:

...

Not suggesting we actually switch, but there is one strong 'why': You can't link Haskell code with any library that uses GMP internally internally without switching to using integer-simple. I've been trying with very limited success to get good MPFR bindings for Haskell for ~3 years now as a result.

The most likely fix actually involves changes to MPFR as their constant cache and our garbage collector don't play nice.

On Tue, Oct 22, 2013 at 7:36 PM, Edward Z. Yang

...
wrote:

...
Hey Gergeley,

...
(obviously we would have to call mpz_free here and there, but that seems doable).

Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector.

The alternate strategy is to arrange that some sort of "callback" gets invoked when an object dies. You can achieve this using our finalizer support, but you pay an efficiency penalty and cannot guarantee that the integers will get freed in a timely manner at all.

...
More concretely: openssl BN uses the openssl_malloc function can only be overridden openssl wide. But if we link statically, than this override won't affect external openssl library bindings, because the openssl symbols in our object files won't even be exported, right?

Only if literally two copies of OpenSSL are linked. This seems unlikely to work the way you want it to.

Cheers, Edward _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Gergely Risko

23 Oct 23 Oct

7:40 a.m.

On Tue, 22 Oct 2013 21:29:48 -0400, Carter Schonwald writes:

...

At some point I'd actually like to explore trying to build a satisfactory "integer-fancy" in Haskell, but there's a few technical challenges I'll be trying to do first before there'll be an engineering story for building a satisfactory Haskell replacement that is performant enough to justify dropping Gmp

Basically I think until we can build an alternative with competitive performance in straight ghc Haskell, there's no good argument for dropping Gmp overall. There are a number of great reasons that everyone has mentioned, but it needs to be a net win for everyone before the leap could be justifiable.

I see how clear and nice would a straight haskell implementation would be. But do we actually have any chance to be close to GMP or other C based bignum libraries? I mean they're in development for years and probably has a lot of knowledge burnt into them, no? I consider the following situation already a net win: - same performance as now, - statically linked, so ldd'ing ghc or a compiled program doesn't show gmp, openssl or any other library. Currently the ldding output of a simple haskell binary contains libc + libgmp. libc is very backwards compatible, but gmp causes issues, getting rid of it is a win for me, - possibility to build Ekmett's MPFR binding. Do you consider the stability benefit of working status quo stronger than the ones above?

...

If I manage to get my target work for 7.10 sorted out with a few months to spare, I may try to spend a few months exploring this, though no promises. Current ghc doesn't have the right primops to do this yet.

Can you please elaborate on this? What primops are needed for a pure haskell solution? Thanks, Gergely

Gergely Risko

9:45 a.m.

On Tue, 22 Oct 2013 20:26:53 -0400, Edward Kmett writes:

...

Not suggesting we actually switch, but there is one strong 'why': You can't link Haskell code with any library that uses GMP internally internally without switching to using integer-simple. I've been trying with very limited success to get good MPFR bindings for Haskell for ~3 years now as a result.

Have you tried going the other-way around? Modifying GMP+MPFR just a little bit to ignore the mem_set_functions that are called by GHC and force them to use malloc. Then writing a wrapper for this patched GMP+MPFR. Gergely

Edward Kmett

10:07 a.m.

What we're doing right now is a little less invasive. It embeds a patched copy of MPFR, but tweaks the way they store their constant cache, so that it doesn't use the allocator and not tell us about it, but instead stores the cache using a secondary allocation path. It works. However, we at last check had some limitations loading it with ghci. I'm hopeful that with 7.8 and the less magic dynamic linker that this will "just work". Before that Dan Peebles took a stab at rehooking the GMP allocator hook for me to introspect on the stack and switch to malloc when called from the constant cache, so we could just link to the host MPFR implementation. That _worked_, but the code was awful, and it wouldn't work from ghci. We couldn't get the allocator rehook to load from ghci because ghci doesn't currently run c++ initialization blocks. This also appears to be fixed in 7.8 so that may be another path forward. This has been a very slow burn project for me. I need it eventually so I can finish a library for working with Taylor models, where I need the result interval to have proper rounding, so I can say definitively that the answer lies within some small region and can use extra leading terms in the Taylor model to make the intervals involved arbitrarily small, so I don't get swamped in the error. When that finally works Haskell should be able to compete with COSY Infinityhttp://www.bt.pa.msu.edu/index_cosy.htm in computing models for things like accelerator lattices, electron microscopes, spectrographs, etc. -Edward On Wed, Oct 23, 2013 at 9:45 AM, Gergely Risko wrote:

...

On Tue, 22 Oct 2013 20:26:53 -0400, Edward Kmett writes:

...
Not suggesting we actually switch, but there is one strong 'why': You can't link Haskell code with any library that uses GMP internally internally without switching to using integer-simple. I've been trying with very limited success to get good MPFR bindings for Haskell for ~3 years now as a result.

Have you tried going the other-way around? Modifying GMP+MPFR just a little bit to ignore the mem_set_functions that are called by GHC and force them to use malloc. Then writing a wrapper for this patched GMP+MPFR.

Gergely

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Gergely Risko

11:44 a.m.

On Wed, 23 Oct 2013 10:07:27 -0400, Edward Kmett writes:

...

Before that Dan Peebles took a stab at rehooking the GMP allocator hook for me to introspect on the stack and switch to malloc when called from the constant cache, so we could just link to the host MPFR implementation. That _worked_, but the code was awful, and it wouldn't

Wait, this sounds like a big hack, but isn't this a quite good interim solution to this whole issue? Not to the licensing, but to the technical? The functions in ./libraries/integer-gmp/cbits/alloc.c could just read some thread-local global variable to know whether they're being called "from GHC Integer", and GHC would write to this before calling the GMP functions. Or instead of a TL global variable, mark the stack somehow. This sounds hackish, but not so bad in my opinion. The GHC+GMP integration is already hacky memory management wise. Also, the current situation is kind of a deadlock: - we should write integer-gmp packages to test their performance, - but they would only work with a special GHC compiled with integer-simple, - when we have a perfect one, we can remove integer-gmp from GHC itself, so they work. It's hard to develop and test a library with any reasonable number of test subjects if it needs a special GHC... Gergely

Gergely Risko

7:31 a.m.

On Tue, 22 Oct 2013 16:36:45 -0700, "Edward Z. Yang" writes:

...

Hey Gergeley,

...
(obviously we would have to call mpz_free here and there, but that seems doable).

Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector.

The alternate strategy is to arrange that some sort of "callback" gets invoked when an object dies. You can achieve this using our finalizer support, but you pay an efficiency penalty and cannot guarantee that the integers will get freed in a timely manner at all.

Yes, I was thinking of this alternative strategy. I can understand that this may be slower in CPU, but can you please elaborate why would it be worse in memory, how the frees wouldn't happen in a "timely manner"? I thought finalisers are called when the referencee is GCd, so if we free the mpz in the callback, then where are we going wrong?

...

...
More concretely: openssl BN uses the openssl_malloc function can only be overridden openssl wide. But if we link statically, than this override won't affect external openssl library bindings, because the openssl symbols in our object files won't even be exported, right?

Only if literally two copies of OpenSSL are linked. This seems unlikely to work the way you want it to.

So we certainly don't want to replace the impossibility of wrapping libgmp in a hackage library with the impossibility of linking openssl :) Thanks for the input, if I go BN, I'll prioritize this to one of the first issues I tackle, because everyone is telling me that this is hard and I want to fail fast. Gergely

Bryan O'Sullivan

12:08 p.m.

On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko wrote:

...

I can understand that this may be slower in CPU, but can you please elaborate why would it be worse in memory, how the frees wouldn't happen in a "timely manner"? I thought finalisers are called when the referencee is GCd, so if we free the mpz in the callback, then where are we going wrong?

There is no guarantee that finalizers will be called at all, much less that they will be called in a timely manner. This is a general and well-known property of all garbage collectors, not something unique to GHC.

Austin Seipp

12:49 p.m.

First, I took some time a year or two ago to give a go at writing an integer-openssl implementation. I don't have the code anymore (it was more of a fun exercise,) sorry. :( However, the real problem with the whole integer situation IMO, is that the choice of integer implementation is completely non-modular, everything else aside. In a theoretically ideal world, it would be a link-time option, e.g. $ ghc foo.hs $ ghc -threaded foo.hs will relink `foo` with the -threaded runtime. Similarly we would like to say: $ ghc foo.hs $ ghc -integer-type=gmp foo.hs $ ghc -integer-type=openssl foo.hs $ ghc -integer-type=simple foo.hs and so on. This is besides all of the talk of "we need to tell the GC that a root is here, so it doesn't free things, etc." as in the case with MPFR. The current scheme is non-modular because it depends on a package-level interface which the compiler cannot hide. Furthermore, it depends on a specific build of GHC to choose, and various people end up needing this but do not want to recompile (for the standard - valid - typical deployment reasons: you want a stable version of your compiler, not a home-grown one.) Unfortunately the current situation with a package-level interface has various ramifications making this theory quite difficult in practice. A) Because it's an exposed-package, people actually do, sometimes, depend on it or the API in various ways. This means swapping implementations becomes more difficult (OTOH, such low-level-ness is a rare occurrence for most users, so perhaps this wouldn't hurt too many people.) B) The bigger problem related to A) is that because it's an exposed-package, GHC will inline the hell out of unfoldings for integer-gmp primitives at call sites. That means a compiled module may get an inlined copy of some integer-gmp primitive for example (a library could use Integer internally,) making re-linking later basically impossible. C) Probably other things I can't think of off the top of my head. In particular I don't know how to do this and reconcile A and B without destroying the efficiency of the GMP-related primitives, or highly restricting the Integer implemenation API and specializing it further in the compiler to handle stuff like this. Or something. The idea is that we inline all the unfoldings to minimize the overhead at call sites, but I'm not sure the best way to do this at the linker level - in particular we might need to stub things out per-way, because relinking requires the same symbols both ways, and we want an interface that does not cost us much. It doesn't cost too much for the RTS because the bits to relink are fairly minimal and don't hurt the fast path very much, AFAIK. If half of the problem is actually integration issues, can I ask why we don't just pick a small C library and offer that up? It is highly likely we will *never* beat GMP unfortunately. Beating it in some specific cases might work, but it has been ruthlessly optimized for years by many skilled people, and I highly doubt we can beat it on average without a very, very substantial amount of work. It would be interesting work - but I'm not convinced we can't have an acceptable solution in the mean time (and by all means, should we get something faster, it can just replace integer-simple.) As an example, libtomcrypt is damn fast, BSD3 licensed, very small, and well-respected. Why don't we: 1) Take libtomcrypt, modify the symbol names to be private to GHC (e.g. prefix everything with `ghc_integer_`) - this means the symbol names will be internal to GHC, so this also doesn't affect relinks against other copies of libtomcrypt (many projects include their own copy.) It is so small it basically comes under our control completely. 2) We can then offer people a integer-tomcrypt which does not have compatibility issues, and does not cause as much pain as the integration of widely deployed libraries like GMP/OpenSSL, which are in various use by many Haskell packages already. This should give us the flexibility of integer-simple without compromising so much on the efficiency aspect. This is also a very half-baked idea, but just a suggestion. I'd love a more modular solution to Integer as well, as I know many other people would. On Wed, Oct 23, 2013 at 11:08 AM, Bryan O'Sullivan wrote:

...

On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko wrote:

...
I can understand that this may be slower in CPU, but can you please elaborate why would it be worse in memory, how the frees wouldn't happen in a "timely manner"? I thought finalisers are called when the referencee is GCd, so if we free the mpz in the callback, then where are we going wrong?

There is no guarantee that finalizers will be called at all, much less that they will be called in a timely manner. This is a general and well-known property of all garbage collectors, not something unique to GHC.

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

-- Regards, Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

Austin Seipp

12:53 p.m.

Apologies for the quick double-take, minor amendments: We actually want libtommath. Also it is not BSD3 - it is public domain (it's also 100% portable ISO C and builds anywhere.) On Wed, Oct 23, 2013 at 11:49 AM, Austin Seipp wrote:

...

First, I took some time a year or two ago to give a go at writing an integer-openssl implementation. I don't have the code anymore (it was more of a fun exercise,) sorry. :(

However, the real problem with the whole integer situation IMO, is that the choice of integer implementation is completely non-modular, everything else aside. In a theoretically ideal world, it would be a link-time option, e.g.

$ ghc foo.hs $ ghc -threaded foo.hs

will relink `foo` with the -threaded runtime. Similarly we would like to say:

$ ghc foo.hs $ ghc -integer-type=gmp foo.hs $ ghc -integer-type=openssl foo.hs $ ghc -integer-type=simple foo.hs

and so on. This is besides all of the talk of "we need to tell the GC that a root is here, so it doesn't free things, etc." as in the case with MPFR.

The current scheme is non-modular because it depends on a package-level interface which the compiler cannot hide. Furthermore, it depends on a specific build of GHC to choose, and various people end up needing this but do not want to recompile (for the standard - valid - typical deployment reasons: you want a stable version of your compiler, not a home-grown one.)

Unfortunately the current situation with a package-level interface has various ramifications making this theory quite difficult in practice.

A) Because it's an exposed-package, people actually do, sometimes, depend on it or the API in various ways. This means swapping implementations becomes more difficult (OTOH, such low-level-ness is a rare occurrence for most users, so perhaps this wouldn't hurt too many people.) B) The bigger problem related to A) is that because it's an exposed-package, GHC will inline the hell out of unfoldings for integer-gmp primitives at call sites. That means a compiled module may get an inlined copy of some integer-gmp primitive for example (a library could use Integer internally,) making re-linking later basically impossible. C) Probably other things I can't think of off the top of my head.

In particular I don't know how to do this and reconcile A and B without destroying the efficiency of the GMP-related primitives, or highly restricting the Integer implemenation API and specializing it further in the compiler to handle stuff like this. Or something. The idea is that we inline all the unfoldings to minimize the overhead at call sites, but I'm not sure the best way to do this at the linker level - in particular we might need to stub things out per-way, because relinking requires the same symbols both ways, and we want an interface that does not cost us much. It doesn't cost too much for the RTS because the bits to relink are fairly minimal and don't hurt the fast path very much, AFAIK.

If half of the problem is actually integration issues, can I ask why we don't just pick a small C library and offer that up? It is highly likely we will *never* beat GMP unfortunately. Beating it in some specific cases might work, but it has been ruthlessly optimized for years by many skilled people, and I highly doubt we can beat it on average without a very, very substantial amount of work. It would be interesting work - but I'm not convinced we can't have an acceptable solution in the mean time (and by all means, should we get something faster, it can just replace integer-simple.)

As an example, libtomcrypt is damn fast, BSD3 licensed, very small, and well-respected. Why don't we:

1) Take libtomcrypt, modify the symbol names to be private to GHC (e.g. prefix everything with `ghc_integer_`) - this means the symbol names will be internal to GHC, so this also doesn't affect relinks against other copies of libtomcrypt (many projects include their own copy.) It is so small it basically comes under our control completely.

2) We can then offer people a integer-tomcrypt which does not have compatibility issues, and does not cause as much pain as the integration of widely deployed libraries like GMP/OpenSSL, which are in various use by many Haskell packages already.

This should give us the flexibility of integer-simple without compromising so much on the efficiency aspect.

This is also a very half-baked idea, but just a suggestion. I'd love a more modular solution to Integer as well, as I know many other people would.

On Wed, Oct 23, 2013 at 11:08 AM, Bryan O'Sullivan wrote:

...
On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko wrote:

...
I can understand that this may be slower in CPU, but can you please elaborate why would it be worse in memory, how the frees wouldn't happen in a "timely manner"? I thought finalisers are called when the referencee is GCd, so if we free the mpz in the callback, then where are we going wrong?

There is no guarantee that finalizers will be called at all, much less that they will be called in a timely manner. This is a general and well-known property of all garbage collectors, not something unique to GHC.

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

-- Regards,

Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

-- Regards, Austin Seipp, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

Gergely Risko

1:06 p.m.

On Wed, 23 Oct 2013 11:49:00 -0500, Austin Seipp writes:

...

$ ghc foo.hs $ ghc -integer-type=gmp foo.hs $ ghc -integer-type=openssl foo.hs $ ghc -integer-type=simple foo.hs

Well, I didn't think of this. This would indeed be very cool, unfortunately it's quite hard if I understood you correctly.

...

As an example, libtomcrypt is damn fast, BSD3 licensed, very small, and well-respected. Why don't we:

1) Take libtomcrypt, modify the symbol names to be private to GHC (e.g. prefix everything with `ghc_integer_`) - this means the symbol names will be internal to GHC, so this also doesn't affect relinks against other copies of libtomcrypt (many projects include their own copy.) It is so small it basically comes under our control completely.

2) We can then offer people a integer-tomcrypt which does not have compatibility issues, and does not cause as much pain as the integration of widely deployed libraries like GMP/OpenSSL, which are in various use by many Haskell packages already.

This should give us the flexibility of integer-simple without compromising so much on the efficiency aspect.

This is also a very half-baked idea, but just a suggestion. I'd love a more modular solution to Integer as well, as I know many other people would.

Just to be sure I understand the idea: do you mean linking this ghc_integer_ prefix libtommath statically into ghc and every resulting haskell binary, right? It makes no sense to link dynamically if the user can't replace it with a standard libtommath anyways because of the prefix. And do you mean shipping this libtommath GHC by default (instead of integer-simple) and starting to develop an integer-gmp or package on hackage? Gergely

Simon Marlow

24 Oct 24 Oct

4:24 a.m.

On 23/10/13 17:08, Bryan O'Sullivan wrote:

...

On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko mailto:gergely@risko.hu> wrote:

I can understand that this may be slower in CPU, but can you please elaborate why would it be worse in memory, how the frees wouldn't happen in a "timely manner"? I thought finalisers are called when the referencee is GCd, so if we free the mpz in the callback, then where are we going wrong?

There is no guarantee that finalizers will be called at all, much less that they will be called in a timely manner. This is a general and well-known property of all garbage collectors, not something unique to GHC.

This is true, but I would add that C finalizers are rather more prompt and reliable than Haskell finalizers, since we added special support for them a couple of versions ago. C finalizers are run directly by the GC rather than in separate threads, and we run all the outstanding ones before the program terminates. Cheers, Simon

Simon Peyton-Jones

4:41 a.m.

| This is true, but I would add that C finalizers are rather more prompt | and reliable than Haskell finalizers, since we added special support for | them a couple of versions ago. C finalizers are run directly by the GC | rather than in separate threads, and we run all the outstanding ones | before the program terminates. Great. Is this difference documented? I couldn't find my way to this info. I tried Hoogling for "final", and got this link http://hackage.haskell.org/package/base-4.6.0.1/docs/Foreign-ForeignPtr.html... but it is dead. I wonder if it would be worth summarising in the user manual the main facilities offered, with pointers to the Haddock docs that describe them? Simon | -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Simon | Marlow | Sent: 24 October 2013 09:24 | To: Bryan O'Sullivan; Gergely Risko | Cc: ghc-devs@haskell.org | Subject: Re: Why do we put GMP allocations on GHC heaps? | | On 23/10/13 17:08, Bryan O'Sullivan wrote: | > | > On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko mailto:gergely@risko.hu> wrote: | > | > I can understand that this may be slower in CPU, but can you | please | > elaborate why would it be worse in memory, how the frees wouldn't | happen | > in a "timely manner"? I thought finalisers are called when the | > referencee is GCd, so if we free the mpz in the callback, then | where are | > we going wrong? | > | > | > There is no guarantee that finalizers will be called at all, much less | > that they will be called in a timely manner. This is a general and | > well-known property of all garbage collectors, not something unique to | GHC. | | This is true, but I would add that C finalizers are rather more prompt | and reliable than Haskell finalizers, since we added special support for | them a couple of versions ago. C finalizers are run directly by the GC | rather than in separate threads, and we run all the outstanding ones | before the program terminates. | | Cheers, | Simon | | | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs

Simon Marlow

5:26 a.m.

On 24/10/13 09:41, Simon Peyton-Jones wrote:

...

| This is true, but I would add that C finalizers are rather more prompt | and reliable than Haskell finalizers, since we added special support for | them a couple of versions ago. C finalizers are run directly by the GC | rather than in separate threads, and we run all the outstanding ones | before the program terminates.

Great. Is this difference documented? I couldn't find my way to this info.

I tried Hoogling for "final", and got this link http://hackage.haskell.org/package/base-4.6.0.1/docs/Foreign-ForeignPtr.html... but it is dead.

This seems to be a problem caused by the fact that Foreign.ForeignPtr is in both base and haskell2010. Ticket: http://ghc.haskell.org/trac/ghc/ticket/8475

...

I wonder if it would be worth summarising in the user manual the main facilities offered, with pointers to the Haddock docs that describe them?

http://www.haskell.org/ghc/docs/latest/html/libraries/haskell2010-1.1.1.0/Fo... We probably ought to have a bit more there, yes. Cheers, Simon

...

Simon

| -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of Simon | Marlow | Sent: 24 October 2013 09:24 | To: Bryan O'Sullivan; Gergely Risko | Cc: ghc-devs@haskell.org | Subject: Re: Why do we put GMP allocations on GHC heaps? | | On 23/10/13 17:08, Bryan O'Sullivan wrote: | > | > On Wed, Oct 23, 2013 at 4:31 AM, Gergely Risko mailto:gergely@risko.hu> wrote: | > | > I can understand that this may be slower in CPU, but can you | please | > elaborate why would it be worse in memory, how the frees wouldn't | happen | > in a "timely manner"? I thought finalisers are called when the | > referencee is GCd, so if we free the mpz in the callback, then | where are | > we going wrong? | > | > | > There is no guarantee that finalizers will be called at all, much less | > that they will be called in a timely manner. This is a general and | > well-known property of all garbage collectors, not something unique to | GHC. | | This is true, but I would add that C finalizers are rather more prompt | and reliable than Haskell finalizers, since we added special support for | them a couple of versions ago. C finalizers are run directly by the GC | rather than in separate threads, and we run all the outstanding ones | before the program terminates. | | Cheers, | Simon | | | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs

Florian Weimer

31 Oct 31 Oct

3:39 a.m.

* Edward Z. Yang:

...

Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector.

The real problem here is that GHC uses the mpz_* functions and not the lower-level mpn_* functions, where the caller is responsible for memory management and which would play well with garbage collection (or any other memory management scheme).

Edward Kmett

3:49 a.m.

That actually would be a pretty reasonable way forward, that could maintain the performance of the current approach without crippling GMP for other consumers. It'd probably be a fair bit of work, as you wind up up to your eyeballs in the guts of the library, limbs everywhere, colorful body part metaphors flying every which way. It doesn't make accessing libraries like MPFR from Haskell in the most high performance way all that much easier, but it does mean that if you linked to a library that used them you wouldn't just start randomly segfaulting like you do today. If someone else doesn't get around to it first, I'll probably give it a shot eventually. -Edward On Thu, Oct 31, 2013 at 3:39 AM, Florian Weimer wrote:

...

* Edward Z. Yang:

...
Actually, this is precisely the problem. When is a GMP integer freed? It can have pointers to it from objects on the heap, so this free should only occur when the integer is dead, with no references from the heap. How can that be arranged? Well, the garbage collector is responsible for figuring this out. So why shouldn't they just live on the heap, and then smoothly integrate with the existing garbage collector.

The real problem here is that GHC uses the mpz_* functions and not the lower-level mpn_* functions, where the caller is responsible for memory management and which would play well with garbage collection (or any other memory management scheme). _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Simon Marlow

4 Nov 4 Nov

5:18 a.m.

On 31/10/2013 07:49, Edward Kmett wrote:

...

That actually would be a pretty reasonable way forward, that could maintain the performance of the current approach without crippling GMP for other consumers.

It'd probably be a fair bit of work, as you wind up up to your eyeballs in the guts of the library, limbs everywhere, colorful body part metaphors flying every which way.

It doesn't make accessing libraries like MPFR from Haskell in the most high performance way all that much easier, but it does mean that if you linked to a library that used them you wouldn't just start randomly segfaulting like you do today.

If someone else doesn't get around to it first, I'll probably give it a shot eventually.

We did originally look at targetting the mpn API, but decided against it for the reasons alluded to above - the mpz layer has quite a lot of stuff in it that you would need to replicate. For instance, when you start doing an operation some calculation has to be done to figure out how much memory to allocate for the result. And be extra careful, because the GMP code is GPL, so our replacement for the mpz bits would probably end up being GPL too. Historical tidbit: hbc targets the mpn layer, IIRC. Cheers, Simon

...

-Edward

On Thu, Oct 31, 2013 at 3:39 AM, Florian Weimer mailto:fw@deneb.enyo.de> wrote:

* Edward Z. Yang:

> Actually, this is precisely the problem. When is a GMP integer freed? > It can have pointers to it from objects on the heap, so this free should > only occur when the integer is dead, with no references from the heap. > How can that be arranged? Well, the garbage collector is responsible > for figuring this out. So why shouldn't they just live on the heap, and > then smoothly integrate with the existing garbage collector.

The real problem here is that GHC uses the mpz_* functions and not the lower-level mpn_* functions, where the caller is responsible for memory management and which would play well with garbage collection (or any other memory management scheme). _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org mailto:ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://www.haskell.org/mailman/listinfo/ghc-devs

Florian Weimer

3:36 p.m.

* Simon Marlow:

...

We did originally look at targetting the mpn API, but decided against it for the reasons alluded to above - the mpz layer has quite a lot of stuff in it that you would need to replicate. For instance, when you start doing an operation some calculation has to be done to figure out how much memory to allocate for the result.

Sure, and you have to do sign handling. The advantage is that you could use a convenient encoding for length and sign, or deal with carry/borrow in a flexible manner (i.e., stealing another word from the allocation buffer). It's not exactly trivial, but the effort may be worth it.

...

And be extra careful, because the GMP code is GPL, so our replacement for the mpz bits would probably end up being GPL too.

Actually, it's LGPL, and interesting bits are part of libc under an even more permissive license.

Simon Peyton-Jones

23 Oct 23 Oct

4:57 a.m.

Gergely Edward has it right. Functional programs allocate a lot of intermediate stuff. ((a+b)*c-d) allocates two intermediate Integers and discards them pretty soon afterwards. GHC's code generator and garbage collector are good at both allocation and gc of young dead objects. Using malloc/free would require a finaliser-style interface, which is significantly less efficient. That might matter a lot for an arithmetic-intensive program, and not at all for one where Integer arithmetic was incidental. However, you could perfectly well imagine a third package (alongside integer-gmp and integer-simpl), let's call it integer-gmp-malloc. This would use the malloc/free interface, with finalisers to free space when no longer referenced from the GHC heap. It might be faster than integer-simple, and more inter-operable than integer-gmp. Also, freeing us from the GPL constraints of GMP, while offering better performance than integer-simple, would be great. See also http://ghc.haskell.org/trac/ghc/wiki/ReplacingGMPNotes Please do record the information or insights you get on a GHC wiki page! Simon | -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | Gergely Risko | Sent: 22 October 2013 22:45 | To: ghc-devs@haskell.org | Subject: Why do we put GMP allocations on GHC heaps? | | Dear GHC gurus, | | I've been looking into how GHC uses GMP (with the hidden agenda of | taking the work of replacing it with something that is BSD license | compatible and so can be linked in and shipped statically by default). | | I think I more or less understand how GMP memory is managed and how the | GC works together with it. Actually understanding the "how" was not | that hard, everything is quite clearly commented. | | What I couldn't find any reference for is the "why". Why does GHC do | this? Would it be possible to just not do this and let GMP malloc and | free for itself (obviously we would have to call mpz_free here and | there, but that seems doable). | | I have multiple ideas, but don't know which one (if any) is correct: | - performance reasons, | - memory defragmentation reasons, | - GHC GC moves around stuff and that would somehow break, | - the previous one + threads + race conditions. | | Second question: let's assume for a moment that we don't have any | licensing issues with a GMP like library, can be linked statically into | GHC, but we decide to go with the same allocation methodology as with | GMP. Am I right when I think that linking statically solves the | technical issues too. | | More concretely: openssl BN uses the openssl_malloc function can only be | overridden openssl wide. But if we link statically, than this override | won't affect external openssl library bindings, because the openssl | symbols in our object files won't even be exported, right? | | Third question: is replacing with openssl bn an acceptable path to | you guys? I saw that 6 years ago there were work on getting | integer-simple performance wise good enough to be the default and then | adding other bignum libraries externally, but none of this happened. | I see how sexy project it is computer science wise to write a bignum | library in Haskell, but will we really do it? | | Thanks, | Gergely | (errge) | | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-devs

Gergely Risko

7:44 a.m.

On Wed, 23 Oct 2013 08:57:55 +0000, Simon Peyton-Jones writes:

...

Gergely

Edward has it right. Functional programs allocate a lot of intermediate stuff. ((a+b)*c-d) allocates two intermediate Integers and discards them pretty soon afterwards. GHC's code generator and garbage collector are good at both allocation and gc of young dead objects.

Thanks for the confirmation.

...

Using malloc/free would require a finaliser-style interface, which is significantly less efficient. That might matter a lot for an arithmetic-intensive program, and not at all for one where Integer arithmetic was incidental.

Do we have benchmarks for this in nofib? If I do some mockups, can I believe what (specific tests from) nofib says? Or does researching for a replacement first includes the task of writing a benchmark suite?

...

However, you could perfectly well imagine a third package (alongside integer-gmp and integer-simpl), let's call it integer-gmp-malloc.

Actually it's not clear to me, how would you implement the non-malloc integer-gmp as a package? Can haskell packages integrate with the GC that deep?

...

See also http://ghc.haskell.org/trac/ghc/wiki/ReplacingGMPNotes

Please do record the information or insights you get on a GHC wiki page!

Yes, I've definitely read through those kind of wiki articles. I try to only ask stuff that is not documented there. If I figure out anything in addition, I'll document, thanks. Gergely

4215

Age (days ago)

4228

Last active (days ago)

List overview

Download

21 comments

9 participants

participants (9)

Austin Seipp
Bryan O'Sullivan
Carter Schonwald
Edward Kmett
Edward Z. Yang
Florian Weimer
Gergely Risko
Simon Marlow
Simon Peyton-Jones