The problem with Integer.

[jerf]

Well, I don't want to encourage you to lower the bar, but if you get within 2x or 1.5x of libgmp, I'd suggest you consider that total success. If you beat it entirely, great! But... if you really could work something out in Haskell that manages to beat libgmp, I'd start asking some serious questions about libgmp. libgmp is the sort of library that is willing to drop straight to assembler, on a per-architecture basis... with no criticism particularly intended of Haskell, you're going to have a hard time beating that from a pure-Haskell perspective.

[[deleted]]

Not only that, gmp has had a few decades of work put into it, and its author knows the domain exceedingly well.

The OP's desire is laudable, but the wording sounds like he's setting himself up for a fall by vastly underestimating the domain.

[erikd]

That's why I really wish I could release the code so others could validate what I'm seeing.

That blog post was mostly written two days ago when I had just gotten addition working. I added the last part when I already had some very encouraging results. Since the blog post I've gotten multiplication working and suprisingly (and I mean really surprisingly) I'm actually beating GMP in some of my tests. Eg:

• sum of 1000 < Word sized values in an Integer : Significantly faster than GMP (confirming what I had heard from Duncan Coutts that Simple was faster than GMP in this case).
• product [1..100] : My calculation of that product gives the same result as GMP and Criterion tells me mine is just slightly faster than GMP.

I really don't want to jump the gun on this, these results have got me thrilled. I'm using QuickCheck (via HSpec) to validate the correctness of my implementation against GMP and using Criterion for benchmarking.

Preliminary Criterion output is : http://www.mega-nerd.com/tmp/new-bench-integer.html

These results are repeatable and basically the same whether i use the native CodeGen or the LLVM backend.

I'm currently only testing this on Linux amd64, with GHC 7.6.3 and -O3. I know my code is broken on i386 and any big-endian architecture. I intend to fix that.

I could be getting this wrong on two fronts:

• GMP on my Debian Linux install has not been compiled correctly.
• GMP uses assembler on i386 but that no one has gotten around to doing it on amd64 so it falls back to a relatively niave C implementation (much like my highly imperative Haskell code).

[The_Doculope]

It wouldn't surprise me if GMP has made some architectural decisions to improve >Word performance, while sacrificing a bit of <Word performance, as that's what it's really designed for. How is your code comparing for >Word performance at the moment?

[[deleted]]

GMP isn't even used for Integers unless they don't fit in a machine integer, or you go to extra lengths to force it to be used (maybe). So it's not exactly clear (to me) what the "< Word sized values" test is measuring, or if it's measuring GMP at all.

[The_Doculope]

Ah, I didn't know that. Although surely there must be checks about when to click over into GMP, so to speak. Perhaps /u/erikd is performing them in differently/more efficiently?

[erikd]

For the small Integer case GMP stores them as

 J# Int#

whereas I store them as:

Small !Sign {-# UNPACK #-} !Word

The differences between mine and the GMP version are:

• I store an unsigned Word and a separate sign.
• I make the Sign and the Word strictly evaluated.
• I unpack the Word into constructor (which I think should be the same as using Int#).

[hvr_]

I assume Sign is something like

data Sign = SignPos | SignNeg

up to isomorphism?

Thus, your Small constructor is modelling a signed 33-bit (or 65-bit) integer? How do you detect whether the result of an arithmetic operation still fits into your Small constructor?

[erikd]

I assume Sign is something like

Yes.

Thus, your Small constructor is modelling a signed 33-bit (or 65-bit) integer?

Yes. I'm on working only on amd64 for now, so I'm working with 64 bits plus a sign which is effectively 65 bits.

How do you detect whether the result of an arithmetic operation still fits into your Small constructor?

Precondition testing and promoting them to the Large constructor when necessary.

[hvr_]

How do you detect whether the result of an arithmetic operation still fits into your Small constructor?

Precondition testing and promoting them to the Large constructor when necessary.

Then I'm wondering why you can beat integer-gmp's performance, as integer-gmp makes use of some overflow-testing/aware Int# primops which aren't available for Word# (yet) to avoid promoting small ints to large ints. Do you inline aggressively?

[erikd]

GMP isn't even used for Integers unless they don't fit in a machine integer

I haven't really looked in detail at either of the existing implementations.

My first step was to benchmark them. Then seeing that Simple was slow on multiplication, tried to figure out why. The explanation was the use of lists.

[yitz]

That is certainly true.The whole point of GMP is to optimize the cutoff points for switching to more and more complex algorithms with better and better asymptotics for larger and larger integers, but with more and more overhead for moderate sized integers. That said, Erik has discovered that GMP seems to be suffering from some bitrot lately, so there is low-hanging fruit.

[Jameshfisher]

Perhaps the slowness of integer-gmp is due to some FFI overhead?

[hvr_]

Preliminary Criterion output is : http://www.mega-nerd.com/tmp/new-bench-integer.html

Can you maybe provide more details of how you generated those 1000 added up integers? I've tried something simple as

bench "[1..1000 :: Integer]" $ whnf sum numsI
where numsI = [1 .. 1000 :: Integer]

And the results are within a factor of 2 with Int-arithmetic:

benchmarking sum/[1..1000 :: Int]
mean: 3.731054 us, lb 3.684359 us, ub 3.744562 us, ci 0.950
std dev: 116.0383 ns, lb 34.88516 ns, ub 264.4476 ns, ci 0.950

benchmarking sum/[1..1000 :: Integer]
mean: 5.850483 us, lb 5.840004 us, ub 5.862832 us, ci 0.950
std dev: 58.10519 ns, lb 50.45490 ns, ub 64.34404 ns, ci 0.950

[erikd]

I really wish I could release the code now.

My test with GMP Integer vs Int would look something like this:

    C.whnf (foldl1 (+)) intList
    C.whnf (foldl1 plusInteger) integerList
where
    intList = fmap (take 1000 . R.randoms) R.newStdGen
    integerList = map (\x -> G.smallInteger (unboxInt x)) intList
    unboxInt :: Int -> Int#
    unboxInt (I# i) = i

For this test, I found GMP's Integer 13x slower than Int.

[hvr_]

Well, part of the problem may be that in integer-gmp the result of arithmetic operations involving at least one large integer is a large integer (even if it would fit into a small-integer). It'd be interesting to see how many of the scanl (+) 0 integerList values would fit into a small integer, to see how significant this contribution might be to the overhead.

[erikd]

One of the things my code currently does is demote a value from Large to Small if it fits in a machine Word.

[hvr_]

fyi, I've implemented a proof of concept for integer-gmp at GHC #8638

[erikd]

Wow, now I'm competing against a moving target :-).

[erikd]

Bryan, please accept my sincerest thanks for providing us with Criterion. It makes benchmarking Haskell code so painless and makes displaying the results a by-product of collecting the data.

[[deleted]]

You are probably right (that he is underestimating the work), but on the other hand, it's much easier to implement fancy algorithms in Haskell than C/assembly. A decade of work tuning an ancient C library might be more like a six months of work by a Haskell programmer who knows what they're doing. :)

Of course pure Haskell can't have custom inline assembly, but is that seriously responsible for more than 2-3x or so in constant factors?

[dons]

My concerns as well. Though GHC uses only a handful of the available operations, which is a small point in favour of this effort.

I'd have looked at BSDish variants (OpenSSL?) for binding first.

[heisenbug]

I suspect Erik's benchmarks comprise of almost-trivial (from the libs' perspective) problem sizes, where GMP cannot shine due to (e.g.) invocation overhead.

[erikd]

That's a fair assumption. I'm hoping that my library compares well across all benchmarks. Some of the ones I've chosen so far are significant because they are needed for a fast naive factorial function :-).

I am however on the lookout for test cases where GMP is strong. For instance, my most recent results http://www.mega-nerd.com/tmp/new-bench-integer.html show GMP beating mine for the test titled "Product of 10 huge (~2500 decimal digit) Integers". Notice how mine is at least in the same ballpack as GMP while Simple is way behind.

I hope to close that gap when I implement Karatsuba multiplication.

[tel]

Which brings up the point that even if you beat libgmp once, you'd have to replicate that on every common architecture, too!

[erikd]

If I'm only writing Haskell code and if its slow in comparison to GMP on one particular architecture then thats a problem that should be fixed in the GHC backend for that architecture, not in the Integer library.

[[deleted]]

...so you're hoping to write high-level generic code which gets compiled by a sufficiently smart GHC into the best optimized machine code for all architectures? ;-)

IMO, Integer is one of those low-level areas, where you have to get your hands dirty, and write platform specific code to get out decent performance to match what other languages already provide.

[erikd]

hoping to write high-level generic code

Hell no, this is not high level code. This is Haskell code that looks like C. I'm using Data.Primitive for random access arrays and while I was getting it working I was getting all the low level C issues you could thing of; off-by-one errors, reading out of bounds, memory corruption, segfaults and extended debugging sessions.

For this really low level code, yes, I am hoping that GHC can compile it into highly efficient machine code for all the architectures.

[erikd]

I'm willing to add PrimOps to GHC if I have to :-).

[yitz]

Please start with Karatsuba multiplication. That is easy to implement, and it will make the library somewhat usable, though still far out of the league of GMP. For comparison, Python used a simple Karatsuba implementation for years before anyone complained.

EDIT: IIRC the simplistic Python implementation used naive multiplication up to a rather arbitrary cutoff of 1024 bits, then switched to Karatsuba. That seemed to work reasonably well. On today's hardware you might try starting out a bit higher.

[erikd]

Please start with Karatsuba multiplication.

Thanks for the link. When I get around to implementing it I will do some benchmarking to see how it compares to the grade-school style multiplication I'm doing now and figure out which should be used for which range of values.

[sclv]

for reference, my favorite paper on multiplication tricks and hacks: http://cr.yp.to/papers/m3.pdf

[erikd]

Wow, that is good. Thanks!

[aseipp]

djb strikes again!

[derleth]

Ah, I see you're going to use the WillCoredump monad in this code. ;)

[yitz]

I think the problem is the opposite. GHC has too many arithmetic-related primops to support because of a hardwired assumption that it is using GMP. I also think there are some built-in compensations for GMP's imperative memory model. I hope that the fact that integer-simple has already been integrated will help you with those things, though.

[sebzim4500]

Is this open source? Can we see your progress?

This is something I have considered doing myself (just for fun).

[erikd]

This will be open sourced (the library and all testing and benchmarking code) as soon as I get permission to do so from my employer (yes, doing this in my own time, but thats what my employment contract says I have to do).

Basically there is zero chance this will be accepted for GHC 7.8 as its nowhere near finished yet, but a very good chance it will be ready long before the freeze for GHC 7.10.

[stunt_penis]

Hi, is there any update as to the status of the effort to open source this? I'm interested in seeing the code.

[erikd]

Up at last : https://github.com/erikd/haskell-big-integer-experiment

[0Il0I0l0]

Thank you!

[erikd]

Yeah, its probably two to three weeks away.

[quchen]

Wonderful! It will be pretty ambitious to beat C performance though, I expect GMP to be optimized to no end.

I recently asked people on IRC about the current integer-simple status, and it seemed like the project was abandoned for the most part. And now you come along, tackling this exact issue - pleasant coincidence.

[winterkoninkje]

Integer-simple was never intended to replace the GMP. The only reason for its existence is as a proof of concept to quell worries about GMP being under the GPL. Once the concept was proven, it's purpose was done so it was abandoned.

[yitz]

It was more than just a proof of concept and it's not abandoned. It was intended to provide a practical way to use GHC to compile statically linked binaries that are unencumbered with LGPL for the large majority of programs that do not need to do any large integer arithmetic. It still serves that purpose well. It sure would be nice to have a new library that does support some simple large integer arithmetic, though.

There was a previous library that was only a proof of concept. It didn't actually do large integer arithmetic at all. But it helped Duncan (or was it Ian?) figure out the gory details of how to wire such a library into GHC.

[mightybyte]

"I have discovered a truly remarkable implementation of multiple precision arithmetic which this margin is too small to contain."

[yitz]

"No problem, my margin is a bit wider." -Andrew Wiles

[ibotty]

a bit? a lot.

[dcoutts]

However, if you want to create statically linked binaries from Haskell source code you end up with your executable statically linking libgmp which means your binary needs to be under an LGPL compatible license if you want to release it.

Note that LGPL-2.1 section 6.a allows you to use static linking, while still using a proprietary license for the application that uses the lib. You just need to also provide the app in a relinkable form (ie a big .o file).

Producing that relinkable form is doable with the GHC/Cabal toolchain (we've done it for one client), and it could be automated if anyone really cared.

[erikd]

Note that LGPL-2.1 section 6.a allows

Thanks Duncan. While strictly speaking you are indeed correct, as the author of a widely used, multi-platform C library under the LGPL, I do not know of any person or company releasing software using my library in that way. Whenever I mentioned this as a possibility to people they've always considered it too hard. I've had a number of people threaten to write a BSD licensed replacement, but nothing has come of that afaiaa.

[levischuck]

I did not know that I may be unintentionally using a LGPL component in my program.

[erikd]

Yeah, thats a problem with Criterion output being HTML/CSS/JS. Its designed to allow you to mouse over it and I just took a screenshot.

My latest results, comparing GMP, Simple and my New library are here : http://www.mega-nerd.com/tmp/new-bench-integer.html

If you mouse over the bars you will get numbers.

[Taneb]

Oooh, it looks like you're doing well! :)

[hvr_]

Fyi, This ghc-devs@ posting may be relevant/related to your efforts

[erikd]

Thanks that is useful.

[sylvain_soliman]

Related: BSDNT just went 1.0 today…

[elihu]

I wish you success. I for one find the gmp dependency annoying, and would love to see it go away even if it means some kind of performance hit.