3 ms·

I took a look at that discussion. It looks to me like he might be comparing the mpz interface in GMP against a lower level interface. Of course GMP has the latt

by wbhart 13y ago

I took a look at that discussion. It looks to me like he might be comparing the mpz interface in GMP against a lower level interface. Of course GMP has the latter too, and it's likely much faster than the one he is writing. It sounds like he switches to single word arithmetic when he can. We do that in flint, and it is faster. But it's more like a factor of two, which makes me very suspicious of the benchmarking there. There was a Scheme implementation which once beat GMP for very large integer multiplication, and Magma was also once faster. But those days are long gone. GMP beats what a compiler can do by a factor of 4-12 depending on the compiler version and their high level algorithms are insanely technical. I simply don't believe someone can beat 20 years of GMP development in a few days with a Haskell compiler.

jerf 13y ago
If you look through that thread, you'll find much of the community is pretty skeptical too (including me, same name). Even my citing of 1.5x - 2x was intended to be quite conservative; I'd be happy with rough-factor-of-magnitude. Being willing to add primops is a bit of a wildcard, though; since that means changing what the compiler outputs it means that with enough work, you could juts theoretically convince the compiler to emit the same code an optimized library does. It's not just "Haskell of today" that you're looking at (which I think we'd all trivially agree could not come close in performance on this particular task), it's "Haskell of tomorrow with newly-added features for this task" that we're looking at, and that's harder to guess what its performance could be. (That's nothing to do with Haskell, of course; any language implementation that went that route would see hard-to-predict performance jumps.)
- wbhart 13y ago
  Yes, I understand. I did a quick benchmark to get a ballpark figure for his 10 large integer multiplications, and using GMP's basecase code (which is much slower than the asymptotically faster algorithms it provides) I get about 2ms on my machine. Assuming his machine is a similar speed to mine, that puts him only a factor of about 4 behind GMP. That's actually pretty good. You need a pretty modern GCC to do that in C. So I will be interested in seeing what he finally releases. The addition timings don't seem realistic. GMP can add 1000 small integers in 10 uS without even getting out the assembly primitives.

by wbhart 13y ago

jerf 13y ago

If you look through that thread, you'll find much of the community is pretty skeptical too (including me, same name). Even my citing of 1.5x - 2x was intended to be quite conservative; I'd be happy with rough-factor-of-magnitude. Being willing to add primops is a bit of a wildcard, though; since that means changing what the compiler outputs it means that with enough work, you could juts theoretically convince the compiler to emit the same code an optimized library does. It's not just "Haskell of today" that you're looking at (which I think we'd all trivially agree could not come close in performance on this particular task), it's "Haskell of tomorrow with newly-added features for this task" that we're looking at, and that's harder to guess what its performance could be. (That's nothing to do with Haskell, of course; any language implementation that went that route would see hard-to-predict performance jumps.)

wbhart 13y ago
Yes, I understand. I did a quick benchmark to get a ballpark figure for his 10 large integer multiplications, and using GMP's basecase code (which is much slower than the asymptotically faster algorithms it provides) I get about 2ms on my machine. Assuming his machine is a similar speed to mine, that puts him only a factor of about 4 behind GMP. That's actually pretty good. You need a pretty modern GCC to do that in C. So I will be interested in seeing what he finally releases. The addition timings don't seem realistic. GMP can add 1000 small integers in 10 uS without even getting out the assembly primitives.