A more clever representation of Integer could unbox numbers in big range. But that would require some runtime support, I think. -- Lennart On Jul 31, 2006, at 11:19 , Duncan Coutts wrote:

On Mon, 2006-07-31 at 14:32 +0400, Serge D. Mechveliani wrote:

...

Dear GHC developers,

Long ago you wrote that GHC has made Integer only about 3/2 times slower than Int. I tested this once, and then all this time I have been relying on this. Now, with ghc-6.4.1 compiled for Linux - i386-unknown, running under Debian Linux, Intel Pentium III under ghc -O,

I have an occasion to repeat the test on a certain simple program for processing lists of length 7 over Integer.

And Integer shows 2.55 times slower (11.2 sec against 4.4).

Showld we somehow agree that cost(Integer)/cost(Int) in GHC is about 2.55

or maybe we are missing something?

The cost difference is varies with the context. In the case that the Int/Integer is always boxed then we might expect a constant factor between Int and Integer (at least for numbers that fit in an Int).

However because Int is often unboxable where as Integer is never unboxable there are certainly programs where the factor is much much greater than x2 or x3. If the Int can be unboxed into an Int# then the operations are very quick indeed as they are simple machine primitives.

As an extreme example, I just tried with one of my current simple ByteString benchmarks. If we swap Int for Integer in the inner loop of ByteString.map then the time to evaluate (map f . map g) s increases by 37 times!

So actually that's not to say that Integer is slow, but rather that in many cases GHC is really pretty good at optimising right down to the low level details. The representation of Integer prevents many of these optimisations.

So as I said, the ratio really does depend on what you're doing.

Duncan

_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

If there was an alternative small/big rep, no matter how encoded, it'd still entail conditionals (2 for addition say) to check for that path. And the conditionals also hurt optimisations. But both possibilities would be an interesting thing to try. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] | On Behalf Of John Meacham | Sent: 01 August 2006 02:20 | To: glasgow-haskell-users@haskell.org | Subject: Re: returning to cost of Integer | | > >However because Int is often unboxable where as Integer is never | > >unboxable there are certainly programs where the factor is much much | > >greater than x2 or x3. If the Int can be unboxed into an Int# then the | > >operations are very quick indeed as they are simple machine | > >primitives. | | This has made me wonder whether we are better off getting rid of the | small integer optimization and turning Integer into a straight | unboxable ForeignPtr to a GMP number. this would also mean we could use | the standard GMP that comes with the system since ForeignPtr will take | care of GCing Integers itself. This was my plan with jhc, but at the | moment, Integer is still just intmax_t. | | Another option would be to keep the small integer optimization but make | it CPR | | data Integer = Integer Int# !(Ptr MPZ) | | where if the Ptr is NULL then the Int# contains the value... | | John | | -- | John Meacham - ⑆repetae.net⑆john⑈ | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Lennart Augustsson wrote:

Actually, you can keep it to one test for add/subtract if you use a single word that is either a number or a pointer, the pointer being tagged in lowest bit. Then you can add first and check for tags after. Having tags is rare, so the machine should be told so, if possible. This way you can keep the overhead for bignums really low. But it requires very special handling of bignums and I'm not sure it's worth it.

I like this idea - I remember discussing just such a scheme with John Launchbury recently. It has a lot in common with the semi-tagging scheme we've wanted to implement for some time, where the idea is that you use the low bits of a pointer to store the tag of the constructor it points to, if evaluated. If the contents of the constructor itself can be packed into the other 30 bits, then there's no need for a pointer at all. For enumerated types, you can use all 31 bits for the tag, since only 1 bit is required to indicate evaluated/unevaluated and no pointer is needed. Cheers, Simon

-- Lennart

On Aug 1, 2006, at 03:02 , Simon Peyton-Jones wrote:

...

If there was an alternative small/big rep, no matter how encoded, it'd still entail conditionals (2 for addition say) to check for that path. And the conditionals also hurt optimisations.

But both possibilities would be an interesting thing to try.

Simon

| -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow- haskell-users-bounces@haskell.org] | On Behalf Of John Meacham | Sent: 01 August 2006 02:20 | To: glasgow-haskell-users@haskell.org | Subject: Re: returning to cost of Integer | | > >However because Int is often unboxable where as Integer is never | > >unboxable there are certainly programs where the factor is much much | > >greater than x2 or x3. If the Int can be unboxed into an Int# then the | > >operations are very quick indeed as they are simple machine | > >primitives. | | This has made me wonder whether we are better off getting rid of the | small integer optimization and turning Integer into a straight | unboxable ForeignPtr to a GMP number. this would also mean we could use | the standard GMP that comes with the system since ForeignPtr will take | care of GCing Integers itself. This was my plan with jhc, but at the | moment, Integer is still just intmax_t. | | Another option would be to keep the small integer optimization but make | it CPR | | data Integer = Integer Int# !(Ptr MPZ) | | where if the Ptr is NULL then the Int# contains the value... | | John | | -- | John Meacham - ⑆repetae.net⑆john⑈ | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

On Wed, Aug 02, 2006 at 01:06:48PM +0100, Simon Marlow wrote:

I like this idea - I remember discussing just such a scheme with John Launchbury recently. It has a lot in common with the semi-tagging scheme we've wanted to implement for some time, where the idea is that you use the low bits of a pointer to store the tag of the constructor it points to, if evaluated. If the contents of the constructor itself can be packed into the other 30 bits, then there's no need for a pointer at all. For enumerated types, you can use all 31 bits for the tag, since only 1 bit is required to indicate evaluated/unevaluated and no pointer is needed.

Not just for enumerated types, but for any constructors that don't have any components (independent of other constructors). as in 'Nothing' from Maybe could be represented this way. John -- John Meacham - ⑆repetae.net⑆john⑈

On Thu, Aug 03, 2006 at 02:12:15AM +0400, Bulat Ziganshin wrote:

the main condition is to use some special Int30# type instead of Int# (which we got used to be 32 bits long). i.e. for the type [Char}, where Char= C# Int30# it will be ok, but for [Int] it will be bad (i know about Haskell standard, but how many programs relies on 32-bit Ints?)

Hopefully none, as the standard only guarentees Int to be at least 29 bits to allow tagging implementations of haskell 98 to exist. In any case, it shouldn't matter for Integer, as it would fall over to the bigint representation when you try to put something bigger in there. For the case of representing constructors inside of pointers, it also doesn't make a difference assuming you have a data type with less than 2^30 constructors. :) but then again, it can always fall over into using a pointer. In any case, I don't think it is being proposed that this be used for all Ints, just for a more efficient representation of bigints. though, ideally, I'd hope whatever bigint library we use is smart enough to handle small integers efficiently on its own. John -- John Meacham - ⑆repetae.net⑆john⑈

Hello John, Tuesday, August 1, 2006, 5:19:37 AM, you wrote:

This has made me wonder whether we are better off getting rid of the small integer optimization and turning Integer into a straight unboxable ForeignPtr to a GMP number. this would also mean we could use the standard GMP that comes with the system since ForeignPtr will take care of GCing Integers itself. This was my plan with jhc, but at the moment, Integer is still just intmax_t.

Another option would be to keep the small integer optimization but make it CPR

data Integer = Integer Int# !(Ptr MPZ)

where if the Ptr is NULL then the Int# contains the value...

John, Integer values in many cases used just to keep small numbers which can be larger than 2^32 (2^64) in rare cases. For example, "type FileSize = Integer" used in IO library. so it's important to keep operations on small Integers fast and use minimum amount of memory how about: data Integer = S# Int# | L# !(ForeignPtr MPZ) ? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com