A bunch of people have been asking for benchmarks of LibTommath for comparison. I've ported this benchmark to tommath at https://gist.github.com/zhemao/8204404.
Here are the runs on my machine
BSDNT
digits = 100: 2.43242e-05 s
digits = 1000: 0.000143717 s
digits = 10000: 0.0016644 s
digits = 100000: 0.0378964 s
digits = 1000000: 1.20317 s
digits = 10000000: 40.1549 s
GMP
digits = 100: 1.64086e-05 s
digits = 1000: 0.000117272 s
digits = 10000: 0.00113377 s
digits = 100000: 0.0175584 s
digits = 1000000: 0.284023 s
digits = 10000000: 4.96335 s
TOMMATH
digits = 100: 4.90092e-05 s
digits = 1000: 0.000302586 s
digits = 10000: 0.00548351 s
digits = 100000: 0.368923 s
digits = 1000000: 36.7576 s
digits = 10000000: longer than I was willing to wait
I have no idea why libtommath gets so slow for larger numbers. Would anyone care to comment? I think something must be wrong in the way I ported the benchmark.
Any chance we can see results for 10 digits as well?
The reason I ask is I'm guessing that a lot of work will actually be with smaller numbers of digits.
Is it possible to design a math lib that uses native ints/floats for stuff that fits and switches in the big num stuff on overflow? I believe ruby does this, do any of the libs do it?
I think the ruby approach is to cast the 32 bit items to 64 bit, do the operation into a 64 bit, see if any of the top 32 bits are set, if so, switch to bignum, if not, use the result. If tommath or any of the others do that, then I don't really care that much (for my purpose which is scripting langs that use tommath) about the big num perf. Faster is better but the high order bit for me, at least, is perf on the smaller numbers.
Yes, for example the fmpz type in flint (http://flintlib.org/) implements this optimization, and also caches bignum objects for quick allocation/deallocation. Here is the benchmark with the mpir mpz type vs the flint fmpz type:
mpz fmpz
digits = 10: 4.24e-06 s 1.2e-06 s
digits = 100: 1.28e-05 s 3.3e-06 s
digits = 1000: 8e-05 s 2.7e-05 s
digits = 10000: 0.001 s 0.0006 s
digits = 100000: 0.017 s 0.013 s
digits = 1000000: 0.25 s 0.23 s
digits = 10000000: 4.32 s 4.08 s
In fact, the benchmark is a bit biased against the mpz type because it spends a lot of time allocating and deallocating temporary mpz's. It would be much faster to replace the recursion by a loop with in-place operations when b - a < 20, say. (On the other hand, unoptimized code of this kind is probably quite common in practice...)
I tried that. It's an improvement, but libtommath is still much slower than the other two.
digits = 100: 4.31597e-05 s
digits = 1000: 0.000249898 s
digits = 10000: 0.00252304 s
digits = 100000: 0.0618554 s
digits = 1000000: 5.24447 s
digits = 10000000: 703.01 s
Certainly he has only basecase division, which explains the original benchmark timings.
I'm not very familiar with libtommath, though I had a passing experience with it back in about 2004-2005. However, looking through the code, he does seem to have toom3 (I have both toom3 and toom32, which may or may not be relevant here -- the latter is for unbalanced multiplication).
But more obvious is that libtommath seems to check for errors after every operation, even internally. I think this is some kind of exception mechanism.
I also recall there being a libtomcrypt at some point. Maybe it still exists. That suggests that Tom is possibly focusing on the much more difficult area of crypto, where your code needs to much, much more defensive.
Also, libtommath claims to be 100% C, which bsdnt is not. We use some assembly language, which gives us 5-30% speedup (we could get about another factor of 2 if we unrolled the loops like the C compiler we are comparing against).
Those are a few of the things I can see.
But performance isn't everything. It has never been my intention to be compared with GMP performance-wise for example. You simply cannot beat GMP without being as technical as GMP. The focus here is simplicity and reliability (not to the extremes required for crypto though), and it always will be.
Roughly, my goals with this project were to eventually be much faster than say Python bignums, maybe within a factor of 2 or so of GMP on generic problems, but with code that could be maintained by language designers themselves, without being bignum experts.
Thanks for the clear explanation. And great job on writing a high-performing Bignum library. From these benchmarks, it looks like the go-to for a high-performing, permissively licensed Bignum library.
I noticed your gists used time.h. Coincidentally I have just been fooling around with sys/time.h because I find the former to be unreliable. From what I have read on the web many other hackers share the same sentiment. I'm surprised to see you using it in code like this, or have I missed something?
I just copied the profile code from bsdnt. I guess the reason it uses it is that it simpler and/or more portable. In this case, it does not matter much. I use the functions from sys/time.h when I do more serious profiling.
> I guess the reason it uses it is that it simpler and/or more portable.
After more fooling around I see what you mean. The Open Group has one version of it, my Linux man pages serve me another. I skimmed over the GNU C website, they say that the struct timezone type is obsolete and should be avoided. Happy days.
It's really annoying that any non-LGPL haskell project you release needs to be dynamically linked to libgmp instead of statically linked because of the LGPL restrictionss.
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.
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.)
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.
> It's really annoying that any non-LGPL haskell project you release needs to be dynamically linked to libgmp instead of statically linked because of the LGPL restrictionss.
You should note that the FSF's opinion is that statically or dynamically linking does not alter the status of the result being derivative work or not.
> You should note that the FSF's opinion is that statically or dynamically linking does not alter the status of the result being derivative work or not.
Dynamic linking may or may not create a derivative work on applicable copyright law (on which matter the FSF's opinion is merely the FSF's opinion), but static linking involves directly embedding the libraries code into the final product, which is unmistakably within the exclusive rights of copyright.
In any case, the FSF's opinion on this issue actually makes the GPL more problematic than the alternative would make it.
Yes, but if you statically link, the LGPL requires providing a way for a user to switch to a modified version of the library (e.g. a .a of the rest of the application), which is more hassle than just using dynamic linking.
By definition, dynamic linking will be less of an hassle (and give better performance) than statically linking. After all, this is the original purpose of dynamic linking.
It is also more secure for the user of an computer system.
For each of these projects that herald the BSD license as a feature, I ask myself - what's wrong with GPL? In fact, if it wasn't for GNU and GPL, the world would be a very different place than it is now. I would claim that there would be no such abundance of free software that we find today.
> For each of these projects that herald the BSD license as a feature, I ask myself - what's wrong with GPL?
Using the GPL restricts licensees more in the ideological interest of the licensor. If, as a licensor, I'm not interested in restricting licensees to serve my ideological interests (or if my ideological interests don't align with those in the GPL), why would I use it?
> In fact, if it wasn't for GNU and GPL, the world would be a very different place than it is now. I would claim that there would be no such abundance of free software that we find today.
So? That GNU and the GPL were influential in spreading the idea of FOSS, and even that there might have been a time when the GPLs restrictions were necessary to establish critical mindshare for FOSS, does not mean that the GPL -- whether the same version that existed then or the current version, or anything in between -- is the right license for any particular project now.
This confirms my suspicion that GPL does not cater to proprietary products and that the root issue comes from ideology.
Is it possible that GNU ideology was necessary just for booting? Can we bootstrap from GPL into something that does not care as much about the user's freedoms?
> Can we bootstrap from GPL into something that does not care as much about the user's freedoms?
IF by "does not care as much about the user's freedoms" you mean "imposes fewer ideologically-based requirements on those using licensed software", then we already largely have -- while the GPL and its relatives (LGPL, AGPL, etc.) are still around -- there are lots of major FOSS projects with active communities around non-GPL, more permissively-licensed software. (And even many projects that use the GPL -- such as Perl and Linux -- advertise a less-restrictive interpretation of its terms than the FSF states.)
I think the trend in the FOSS community in general is to prefer to less restrictive terms, which is exactly the opposite of the FSF's direction.
GPL was designed to create a legal protection against people who want to take software offered for free and then go and sue their users if the user dare to modify or share the newer version of the program.
There is little chance that GPL can be made into anything that would allow such behavior. I for once would ask what the point would be. If you do not want that legal protection, then you don't have to. There is no helmet law for software developers.
You can't fork a BSD project and relicense it as GPL unless you are the copyright owner.
"Route around GPL" is the tendency to avoid GPL license on new projects (or to change the license on existing projects - see VLC and jquery). Since project owners are free to do that anyway, the question is why is the BSD license trumpeted as a feature of the product?
Let's take the example of LLVM: there is no problem using GCC on MACs since GCC itself can be used to build proprietary systems. However, LLVM is promoted as "this is your dream compiler - fast, feature full and free from GPL restrictions".
I don't understand the comment about forking. Sure, you can't take my files and change the license on them. But you can take any and all of my files as is, incorporate them into your own GPL project. That's effective the same thing as now the project itself must be distributed under the terms of the GPL. So long as you don't violate the terms of the BSD license, you are free to do what you want. Going the other way is not possible. (Of course when I say BSD license I mean modified-BSD, not the original 4-term license. We don't use that of course.)
There is a difference between the license under which a project is distributed and the license of individual contributions. Any GPL project can use BSD contributions. The overall license of the project remains GPL. The opposite is not true. A BSD licensed project cannot incorporate GPL code, otherwise the project becomes a GPL project, not a BSD one.
A mixed project's source files are BSD & GPL, it has to obey both. The BSD requirements[1] have to be honored as well as the GPL and any other licensed used.
1) such as "Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution."
Because the GPL has a set of restrictions and political baggage that can act as a hindrance to a lot of applications. GPL-encumbered software, for example, cannot be linked to software written under the Eclipse license, so creating a static analysis plugin that links to GCC is not possible. A more open license allows much greater freedom to use a work in the greater Free software community.
Making a Eclipse plug-ins does not make it a derivative of Eclipse. As such, you can have any license on the plug-in. Any. Only derivative works of eclipse will have to be under the Eclipse license, and only in those cases will the work license be incompatible with GPL (since both licenses has their unique requirements).
A less protective license such as BSD might allow for different use cases than GPL, but some users of that BSD work will be faced with the fact that they are going to get sued if they try to modify or share the program. Be that because of the person who happened to distribute it, or patents, or DRM. The greater freedom you are talking about is then the "freedom" to get sued for doing hacker-worthy programming.
My mistake regarding the Eclipse License, and I stand corrected.
However, I stand behind my statement regarding BSD. Because of the restrictive nature of the GPL, one cannot take open code with it, and combine it with code written under other Free licenses, such as the CDDL. One risks being sued, etc, for that. Look at the problems that arose over cdrtools, for example. There are much less restrictive ways to solve what the GPL purports to fix, such as the Apache license.
If a author want to license their software to be explicit incompatible for any developer out there who uses GPL, then that is within the power of that author. This is what some seem to claim happened with cdrtools. If the author tomorrow wanted to make it a BSD incompatible software, it is also within the authors right.
If a company or person takes apache licensed code and distribute it under new terms, they are in legal right to sue their users if any dare to do modification, run modifications, or share the program. If you license a program under a permissive license, one have to accept that some people might end up in jail for wanting to do changes to your code. The GPL protection is there if you want it, but no author is forced to use it. As I said in a above comment, there is no helmet law for developers.
I used mostly NTL (which can use GMP) http://www.shoup.net/ntl/ and it provides some good resources, maybe it's too high level for the goals of this project, but you can always take some idea.
Nicely spotted. Though to be fair MPIR's assembly was improved using a superoptimiser and many more complex algorithms have assembly versions. It could take days for an inexperienced person to understand them. I hope to avoid that complexity (at the obvious loss of some performance) in bsdnt.
I am completely unqualified to comment on these so feel free to correct me, but isn't libtommath a liberally licensed (WTFPL) that also provides efficient bignums?
Simplicity and code size are important. With a large complex project like MPIR (which, being derived from GMP is certainly faster) it is very difficult for newcomers to make contributions. This typically means you are already contributing to GMP (or MPIR) or not at all. So we might hope to develop a larger community around bsdnt because of the lower barrier to entry.
On a more technical level, the divide-and-conquer integer division algorithm in BSDNT is brand new, as is the basecase division. There are also technical improvements in the mullo, mulmid and mulhi interfaces, with 2 words overflows. The FFT I hope to include in the next version also represents significant improvements from only a couple of years ago (though it is already in MPIR).
There are lots of other innovations, such as a dramatically simplified build system, on account of the inline assembly. The zz0 interface is a new idea; it allows one to use light weight signed multiprecision integers in the low level multiprecision natural number interface (nn). And we also test that our pseudorandom generator yields the same values on all systems by taking the sha1 hash of a long stream of output.
Yes, but for crypto you only need to optimise for small "bignums". So performance is not satisfactory for larger stuff, at least not last time I looked. Which was a while ago.
I should add that crypto is a whole 'nuther ballgame. You often need your algorithms to not leak information. That often means going to pretty insane lengths to ensure that.
The standard in good crypto software is also so much more exacting. You don't want to be 99.9% sure it has no exploitable bugs. You want to be 99.999% sure.
I'm absolutely no kind of crypto expert. I'm a number theorist. In no way would bsdnt be suitable for use in crypto applications!
Edit: python's built-in bignums for reference: