At 19:06 +0200 2001/05/04, Marcin 'Qrczak' Kowalczyk wrote:
Let's focus on integers.
ghc doesn't use other gmp types.
GMP has a very interesting multi-precision floating number type as well, but it has the same problem as the integers: It does not use the native double's for small float, so it probably becomes slow.
One problems though is the GC (Garbage Collector):
Indeed. ghc solves it by using gmp format only temporarily to perform operations, and keeping numbers in its own structures.
Does that mean that you are getting extra memory allocations, or are you simply handling over a suitable mpz, and then picking up the _mp_d pointer in you own format? The latter sounds interesting, perhaps one can use it in a C++ wrap.
Then, in order to avoid a dynamic allocation for the ref count as well, one wants the object pointed to by _mp_d above contain all data,
Attaching data to _mp_d can be done without changing gmp, but also without the ability to mix other library using gmp in the same program: by providing appropriate allocation functions, which allocate more, fill the header and return a shifted pointer to gmp. This is what ghc does.
Yes, this is the approach I suggested, but then as a C library the one with the different allocation function will become binary incompatible with the regular library. Perhaps I though in too simplistic patterns; if I put the pointer shifting in the C++ library, I might automate it. But then the C++ library becomes incompatible with the C library. Perhaps it does not matter.
I think you would have to be careful to not use gmp functions which change numbers in place. In Haskell there is no problem because the interface is functional anyway, but a C++ user might want to have ++z performed in place. When the number can be shared, it doesn't work. So either do it functionally or copy by value. In either case sometimes you lose. Leaving gmp memory management to the programmer would make using it awful.
I do not think that standard C++ library containers give such guarantees (say for std::string); one merely builds an interface. (As for the ref count, I use a function detach() which removes any object to be mutated from the reference cluster before mutation.) So it should not be a problem. But it could be interesting for optimization to have GMP functions that are performed in place. One can use some interesting mixtures, say only put the information about the pointer, but copying the sign, in order to make sign changes fast.
So here comes the question in, if now GMP should serve say the implementation of compilers such as GHC, what kind of low number representations should one use?
I don't know how to do it better than currently: that it lets the program/library which uses gmp manage gmp's memory.
So this suggest that it might be a disadvantage for GHC to have a GMP mergeing the two number representations.
It would be an unnecessary complication, but manageable. Since ghc creates mpz objects for each operation, it could use only the big representation of gmp on inputs, handling small numbers itself as currently. But it must be prepared to receive small result. It would be silly to wrap it in an allocated memory if gmp produced a small answer, so primops (implemented in C or assembler) should return either representation.
Perhaps GMP should provide small number arithmetic, with a fast way to determine if the answer fits in a small number representation. For example mpz_si_si, taking two (long) int's, but with the result in a pointer. If one hands over at least two limbs long allocation, this function does not need to make an allocation, but the idea is that one should be able to look at the result to quickly determine if it fits into one int then.
It would be a bit ugly. Ghc's primops use a restriced set of types and rarely allocate memory themselves. For example plusInteger# has the type Int# -> ByteArr# -> Int# -> ByteArr# -> (# Int#, ByteArr# #) where (# x, y #) means to return both values on the stack. It is wrapped for integer addition thus:
plusInteger :: Integer -> Integer -> Integer plusInteger i1@(S# i) i2@(S# j) = case addIntC# i j of { (# r, c #) -> if c ==# 0# then S# r else toBig i1 + toBig i2 } plusInteger i1@(J# _ _) i2@(S# _) = i1 + toBig i2 plusInteger i1@(S# _) i2@(J# _ _) = toBig i1 + i2 plusInteger (J# s1 d1) (J# s2 d2) = case plusInteger# s1 d1 s2 d2 of (# s, d #) -> J# s d
Returning one of two variants from a primop requires expressing it similarly to a C struct, without type punning. So it could be this: plusInteger# :: Int# -> ByteArr# -> Int# -> ByteArr# -> (# Int#, Int#, ByteArr# #) plusInteger (J# s1 d1) (J# s2 d2) = case plusInteger# s1 d1 s2 d2 of (# 0#, i, _ #) -> S# i (# _, s, d #) -> J# s d
The third component in the S# case is ignored, but the primop must pass something - a pointer to a dummy Haskell object (this technique is used in some other primops).
All this checking probably slows down the small format as well.
This assumes that the condition for having an alternative representation is the same in ghc and gmp: fitting into a single signed integer of the limb size (i.e. pointer size).
So you are not using GMP as an interface. One should really try to get a better GMP interface so that program like GHC can use that instead.
Note that the J# representation currently relies on the fact that mpz can be reconstructed from an integer + an array of words of an explicit size. It's not possible to change the representation of mpz and keep the J# representation in ghc.
Or is it so that the dispatch code can only be generated if the input data is sufficiently static, in which it would be great advantage with it in GMP in the case the data is dynamic?
It's dynamic too. An advantage of making the variants visible to the compiler is that a function returning an Integer is compiled to a code which takes an address of two continuations as an argument, and enters the continuation corresponding to the constructor returned, passing it constructor arguments as arguments. It doesn't necessarily allocate S# or J# node on the heap if it's to be evaluated right away. This happens to all algebraic types in general (perhaps there are size constraints, I don't know). So I guess that dispatching is best done by using an algebraic type.
But I'm not sure. The ghc documentation says that ghc loves single-constructor types. It was written a long time ago, but perhaps it's still true. So how to distinguish representations in another way? Well, perhaps data Integer = J# Int# Int# ByteArray# with a dummy object for the ByteArray# in the short case would work. I don't know how well: it's ugly but maybe fast, and it seems easier to integrate with a variant representation in gmp.
In any case better judging of performance of ghc for various representations should be done by somebody with more knowledge than me. I don't know what are exact the overheads in various cases.
You shouldn't worry that anything going on in GMP would not respect upwards compatibility.
ghc abuses gmp by using its internals directly. When the representation of mpz changes, ghc must be changed, even if the C interface remains compatible.
Even renaming some gmp functions and providing old names as macros (or something like this) in gmp3 caused compatibility problem for ghc, and ghc-4.08 requires gmp2, because assembler code calls C functions directly and cpp couldn't translate the names.
So this, in the end, suggests that one perhaps should get a better GMP interface for perhaps both small and large number representations. But it should then be so that GHC could use that interface, rather than abusing its internals.
The GMP developers have so far judged that the effort does not outweigh the advantage of having a type which is faster for small numbers. Do you think that the speed-up for smaller numbers would be significant for such a rewrite?
It is significant. I don't know any numbers, but ghc's handling Integers was told to get a big speedup after introducing the separate representation for small integers.
But this might be partially because calling gmp functions has a lot of indirections, construction of mpz objects etc., so the speedup could result from avoiding calling gmp at all. Allocation in ghc is fast.
What I am was told a long time ago is that as soon as one leaves the simple builtin types, one must perform a lot of checks: CPU's are simply not built for handling multiprecision. Those checks steal a lot of cycles, in addition to memory allocation.
Perhaps in your C++ wrappers you can distinguish the variant above gmp, and use gmp at all only for large numbers? C++ doesn't have such indirections, you would surely keep original mpz objects, but it might be easier than changing gmp.
There is a C++ GMP wrap library already using small number representations and a ref count for large numbers, on top of the _mp_d allocation. But the overflow checks are slow on a C/C++ language level, and better moved into assembler where available.
Note that I'm not against changing gmp. It's not obvious how the consequences would be...
One must have a good idea of how to get about it, before starting to write on something like that. It is an interesting question though. Hans Aberg