Re: integer-simple by default
Hello, Yet another data point would be my current use of Haskell in various integer factorization activities where I would consider the performance, even for relatively large integers (say, 100-1000 decimal digits) very important. However, I wouldn't complain if some simple and manageable implementation were introduced, as long as the re-introduction of the efficient use of some well-tuned library (like GMP) were not hampered needlessly. Best regards Thorkil - Original meddelelse - Fra: Yitzchak Gale g...@sefer.org Til: Greg Fitzgerald gari...@gmail.com Cc: glasgow-haskell-users@haskell.org Dato: Tir, 23. feb 2010 00:04 Emne: Re: integer-simple by default I wrote: As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it Greg Fitzgerald wrote: Looks like they swapped out their integer implementation for Python3 Interesting! This will be new in Python 3.2 - the first changes in many years. It's not exactly swapped out, but there are many changes. At first glance, it looks like better 64-bit support, a new division algorithm via floating-point, a new exponentiation algorithm using a 5-bits-at-a-time trick in some cases, optimized Read and Show instances (pardon the expression), a few other things. A lot of the new stuff seems to be from HAC. As before, everything is fully explained in expository comments inside the code, with references; a worthwhile read. Multiplication is still the same basic idea though - naive up to about 2000 bits, followed by just Karatsuba and nothing more. Thanks, Yitz ___ 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
Re: integer-simple by default
Isaac Dupree: We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out). Daniel Fischer wrote: Just as a data-point, my code rarely exceeds 128 bits (at least, beyond that performance isn't so important anymore). And Daniel, who is part of the Project Euler team, uses large integers far more than most people. As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it. Furthermore, they currently use naive multiplication and don't even bother with Karatsuba for less than about 2000 bits on most recent platforms. Regards, Yitz ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it Thanks for the data point. Looks like they swapped out their integer implementation for Python3: http://gmplib.org/list-archives/gmp-discuss/2008-November/003434.html Here's the code from January 30, 2010: http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup More data points: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic -Greg ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
I think it would be great to have a benchmark, to test Integer performance at various implementations. Perhaps it could test speed of Int, Int64, Int32 as well (for computations that fit within them). I suppose tight numeric loops are key to measuring performance in a useful way (except for incredibly larger Integers). Are there existing benchmarks? (If not, is there a good benchmarking library that I ought to use if I try to write a benchmark?) On 02/22/10 15:15, Greg Fitzgerald wrote: ... More data points: ... Thanks! Code re-use is nice (if we can use one of those BSD-licensed versions) ; although it may turn out useful to write our Integer implementation in Haskell if it helps the optimizer out with small-valued Integers. -Isaac ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
I wrote: As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it Greg Fitzgerald wrote: Looks like they swapped out their integer implementation for Python3 Interesting! This will be new in Python 3.2 - the first changes in many years. It's not exactly swapped out, but there are many changes. At first glance, it looks like better 64-bit support, a new division algorithm via floating-point, a new exponentiation algorithm using a 5-bits-at-a-time trick in some cases, optimized Read and Show instances (pardon the expression), a few other things. A lot of the new stuff seems to be from HAC. As before, everything is fully explained in expository comments inside the code, with references; a worthwhile read. Multiplication is still the same basic idea though - naive up to about 2000 bits, followed by just Karatsuba and nothing more. Thanks, Yitz ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
On 02/21/10 13:14, Ian Lynagh wrote: On Sat, Feb 20, 2010 at 02:56:53PM -0500, Isaac Dupree wrote: -what am I trying to accomplish (at least, performance-wise)? I think opinions are divided on this. Performance with word-sized Integer's is definitely important. This is true. We could start a discussion on the Libraries list -- although I'm sure it would also not reach a clear conclusion. We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out). We could make sure there's a good non-builtin-to-ghc GMP-binding library (Is there one? Is it even possible yet, in a way that doesn't conflict with GHC's builtin GMP?). Then people would have a place to turn if they need GMP's performance for something particular. -what might be a good low-level format? (And is it important to strew unboxed ints all over the place, or is it fine to skip this and count on the optimizer?) I think relying on the optimiser is OK, but don't forget that you don't have the standard (+) etc. oh okay, interesting. I think I'd best start by finding out where integer-simple lies in the dependency tree. -Isaac ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
Am Sonntag 21 Februar 2010 19:56:54 schrieb Isaac Dupree: We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out). Just as a data-point, my code rarely exceeds 128 bits (at least, beyond that performance isn't so important anymore). ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
On 02/21/10 14:18, Daniel Fischer wrote: Am Sonntag 21 Februar 2010 19:56:54 schrieb Isaac Dupree: We could try to find out how large Integers get, in practice, in existing Haskell code (this may be difficult to find out). I suspect (just guessing...) that a more reliable way to find out is to instrument integer-simple to report the sizes of integers it handles. For example, if you use Rational, (even toRational/fromRational), you might be handling Integers somewhat larger than you thought you were. And this could also report on how often the integers get that large. (Also it's probably only tough operations like multiplication and division that we need to worry about for large numbers. It's easy to get linear-time addition, etc. Incidentally, for operations like Large Number plus or minus Small Number, it's possible to use a representation that has laziness and sharing to achieve amortized O(min(m,n)) time. Which is a nice property... which I believe I implemented in HIntegerByInt... but there are probably disadvantages to doing it this way too.) -Isaac ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
You can dynamically link libgmp on windows. That might be easier: Do you know if the dynamic link escape hatch has ever held up in court? Last time I looked into it, the free software community had mixed opinions. In any case, giving GMP the boot alleviates any licensing concerns, makes the GHC build a little simpler, and allows users to create standalone executables. Is there any reason we shouldn't attempt to make integer-simple the default? -Greg ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
On Sat, Feb 20, 2010 at 11:11:15AM -0800, Greg Fitzgerald wrote: In any case, giving GMP the boot alleviates any licensing concerns, makes the GHC build a little simpler, and allows users to create standalone executables. Is there any reason we shouldn't attempt to make integer-simple the default? I think defaulting to a Haskell Integer would be good if we can achieve it (i.e. if we can get a library that performs well enough, whatever that means). The algorithms in integer-simple may be too simple, although I don't think I've done any timings since http://hackage.haskell.org/trac/ghc/ticket/601#comment:14 There's also HIntegerByInt: http://www.haskell.org/pipermail/libraries/2007-August/007909.html although it would need to be changed to user lower level types etc. Thanks Ian ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
On 02/20/10 14:11, Greg Fitzgerald wrote: You can dynamically link libgmp on windows. That might be easier: Do you know if the dynamic link escape hatch has ever held up in court? Last time I looked into it, the free software community had mixed opinions. GMP is under LGPL, which is designed for this very purpose: to allow proprietary code to link to it as long as it is easy to replace the Free code with a different version of Free code (for example, by replacing a dynamic library). Is there any reason to doubt the FSF's efforts? (Note that LGPL doesn't work as well for Haskell code as for C code because Haskell compilers tend to do a lot more inlining; but GMP is C code.) In any case, giving GMP the boot alleviates any licensing concerns, makes the GHC build a little simpler, and allows users to create standalone executables. However the 3-clause BSD license is obviously at least somewhat simpler for lawyers. Is there any reason we shouldn't attempt to make integer-simple the default? If you know that none of your code or libraries are using any particularly large integers [how would you know, though?], then it should perform alright. GMP, however, is the result of years of work making operations on integers large and small be reasonably performant -- work that Haskell would be foolhardy to duplicate, I'm guessing. (Depending what our standards are... Is reasonable performance for multiplying integers less than 320 bits long, say, good enough? What happens when someone wants state-of-the-art performance? Is a nonstandard-Integer-type GMP-binding sufficient for these uses?) -Isaac ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
On 02/20/10 14:37, Ian Lynagh wrote: There's also HIntegerByInt: http://www.haskell.org/pipermail/libraries/2007-August/007909.html although it would need to be changed to user lower level types etc. that's true, (I wrote it), the current form uses a list-based implementation with a lot of recursion and I'd have to see how well that converts to some sort of array [at least I assume arrays are the only reasonable storage layout...]. I used a couple algorithms to make operations faster (at least multiplication -- I don't remember the details) so it might be useful code to pick up again. I have a bit of time now, if anyone's seriously interested, I could work on haskell integer code. As long as I had certain standards -what am I trying to accomplish (at least, performance-wise)? -what might be a good low-level format? (And is it important to strew unboxed ints all over the place, or is it fine to skip this and count on the optimizer?) -Isaac ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: integer-simple by default
garious: Static linking to GMP on Windows is sending me towards a bunch of red tape at work. What can I do to make integer-simple the default integer library for GHC? Need anything more than test suite and performance metrics? Any date planned for the 6.12.2 release? You can dynamically link libgmp on windows. That might be easier: http://haskell.forkio.com/gmpwindows ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
