Dear All, Here is my review of the proposed Multiprecision review. First a rant: why have so few people contributed to the discussion or written reviews? I have waited until now before writing this in the hope that others would say something useful, but there has been very little to read. Boost will suffer as a result of this. It has been depressing to see that at the same time the mailing list has been full of other discussions, so the problem is not that people don't have the time to contribute. In particular, the long thread about Boost.Exception makes me want to shout "Why Didn't You Say All This When It Was Reviewed?". My view of the proposed library can be summarised as follows: it doesn't do what I want, but maybe it does enough things that other users would like to justify its acceptance anyway. Except probably it doesn't, because if it did those other users would have said so, which they haven't. In particular, I'd like to be able to implement integers of perhaps 128 or 256 bits that behave like the built-in integers. I can quickly throw together something myself that works OK but: - It's difficult to get the last bit of performance because you need to write asm to use the CPU's carry flag; the work-around probably results in a 2X slowdown. - Writing all the operator overloading etc. is tedious. - It's also error prone, as a mistake in e.g. carry propagation might be detected once in very 2^32 operations. It would have been great if this library could have helped with this. Instead, it has produced something worse than my "quick throw-together". It's worse because it has tried to unify this smallish fixed-size type with very large variable-size types, and the compromises necessary to achieve this have sabotaged the performance. It's also worse because it had a subtle bug - which has since been corrected, but I would still not be confident of getting correct answers without verifying against another implementation. Ideally, there would still be some parts of the library that could be useful to me. If the library had been decomposed into data structures vs. algorithms then perhaps I could have applied the algorithms to my simpler data structures. Unfortunately the library has not been organised in this way, and even if it had done the use of sign-magnitude representation might have scuppered any re-use. As far as I can see, the only part of the library that I could re-use would be the expression template front-end, which doesn't seem to improve performance for types of this size anyway. Here are my answers to the standard review questions: What is your evaluation of the design? Not great for my purposes; see above. What is your evaluation of the implementation? I spent half a day chasing down a bug. My observations are that (a) there are subtle bugs, and (b) the code lacks comments or other clues for people like me to quickly pick up what it's all doing. What is your evaluation of the documentation? Satisfactory. What is your evaluation of the potential usefulness of the library? Not useful for me; see above. Did you try to use the library? With what compiler? Did you have any problems? I spent perhaps a day working on a small but real benchmark which was discussed on the mailing list. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? About a day-and-a-half in all. I've not looked beyond the areas that I've discussed and I'm aware that there is a lot more to the library i.e. non-integer types. Are you knowledgeable about the problem domain? Not especially. Do you think the library should be accepted as a Boost library? No, because (a) I'm not convinced from this discussion that lots of people are waiting for this functionality (see above). (b) Based on previous experience, I'm sceptical about the possibility of the performance of Boost libraries being improved after acceptance. Despite that, I thank John and Chris for their work which is a considerable leap forward from the last "big number" submission, "xint". Regards, Phil.
AMDG On 06/24/2012 10:46 AM, Phil Endecott wrote:
If the library had been decomposed into data structures vs. algorithms then perhaps I could have applied the algorithms to my simpler data structures. Unfortunately the library has not been organised in this way, and even if it had done the use of sign-magnitude representation might have scuppered any re-use.
While this is an oft-repeated request on this list, I believe that it's fundamentally misguided. All algorithms have to be implemented in terms of some set of primitives. I'm not convinced that there's any reasonable way to define requirements for an integer more basic than +-*/ etc. In Christ, Steven Watanabe
Steven Watanabe wrote:
On 06/24/2012 10:46 AM, Phil Endecott wrote:
If the library had been decomposed into data structures vs. algorithms then perhaps I could have applied the algorithms to my simpler data structures. Unfortunately the library has not been organised in this way, and even if it had done the use of sign-magnitude representation might have scuppered any re-use.
While this is an oft-repeated request on this list, I believe that it's fundamentally misguided. All algorithms have to be implemented in terms of some set of primitives. I'm not convinced that there's any reasonable way to define requirements for an integer more basic than +-*/ etc.
As I've said before, I imagine algorithms that operate on sequences of "limbs" (as John calls them), e.g. (PSEUDO-CODE) template <typename ITER, typename OITER> void add(ITER begin1, ITER end1, ITER begin2, ITER end2, OITER result) { bool carry = false; while (begin1!=end1 && begin2!=end2) { (carry,*result++) = add_with_carry(*begin1++,*begin2++); } } Regards, Phil.
As I've said before, I imagine algorithms that operate on sequences of "limbs" (as John calls them), e.g. (PSEUDO-CODE)
template <typename ITER, typename OITER> void add(ITER begin1, ITER end1, ITER begin2, ITER end2, OITER result) { bool carry = false; while (begin1!=end1 && begin2!=end2) { (carry,*result++) = add_with_carry(*begin1++,*begin2++); } }
Without wanting to reignite this discussion too much, I'll merely point out that there are a number of situations where that would break - fixed precision integers being but one. In most cases the fixes are trivial, as long as you don't mind the performance hit - except of course you do :-( Cheers, John.
Thank you for your review, Phil.
Here is my review of the proposed Multiprecision review.
First a rant: why have so few people contributed to the discussion or written reviews?
<snip> The culprit can only be.... the European Soccer Championships quarter finals! Double over-time and eleven meter, going Italy-England with both teams playing exceptional soccer! <snip>
In particular, I'd like to be able to implement integers of perhaps 128 or 256 bits that behave like the built-in integers. I can quickly throw together something myself that works OK but:
- It's difficult to get the last bit of performance because you need to write asm to use the CPU's carry flag; the work-around probably results in a 2X slowdown. - Writing all the operator overloading etc. is tedious. - It's also error prone, as a mistake in e.g. carry propagation might be detected once in very 2^32 operations.
Again, I see the addition of large numeric types as a long game. Consider the following progression of performance and abstraction. 1) The best of both worlds would be to write highly optimized signed and unsigned versions of integers with 128, 256, 512 and 1024 bits. 2) To the integer types, one should add a highly optimized floating-point (software) implementation of quadruple-precision as specified in IEEE-754:2008. 3) Make these (lower-level) primitives inter-changeable among each other. 4) For larger types, then, one would make the transition to multiple-precision and a higher level of abstraction. John's and my work has focused on part 4. There is, however, no reason to discontinue work on parts 1-3. May I comment, again, on your comment above?
- It's difficult to get the last bit of performance because you need to write asm to use the CPU's carry flag; the work-around probably results in a 2X slowdown.
I don't want to disappoint you, but to be blunt, you need to free yourself from assembly programming. The microprocessor will be twice as fast and half again as expensive in three years or less---no later than the silicon manufacturers do another technology shrink. Take it from an "old-hand" micro-controller professional. Providing for assembly hacks will always lead to portability issues, end-user confusion and a general distraction from high-level C++ that is the whole point of boost in the first place. If you get the algorithms right, it will be fast enough in silicon in the C++ language. Believe it or not, I see great potential in your negative review. This is because your review clearly illuminates the transitional points 1-3 that I suggested above. But I stand by my statement that you have to start somewhere and this is on what multiprecision has focused. Thanks again for taking time to review. Best regards, Chris.
From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Christopher Kormanyos
The culprit can only be.... the European Soccer Championships quarter finals! Double over-time and eleven meter, going Italy-England with both teams playing exceptional soccer!
My view is that the library is not very controversial. If people had objections they would be coming out to say so. If people were concerned it might not get accepted they would come out and give a positive review to help it along. I think it is a good library, it has the abstraction in the right place (from my perspective) and it does what I need. It addresses all of the things about xint that made that library unacceptable. In particular it allows the user to specify the back end implementation and is compatible with Boost.Rational. Perhaps if we want specifically 128bit and 256bit 2's complement big integers that emulate builtins of that size then those should be a separate library: boost::int128_t and boost::int256_t.. I welcome Phil to implement it. This library's purpose isn't to provide the building blocks for providing those types. This library's purpose is to provide an abstraction on numerical data types in general so that we can use them in boost and work toward standardization of them, which C++ does need. It is very hard to provide a boost geometry library without access to a boost extended precision numerical data type. Without this library we must implement our own or provide a metafunction to allow the user to specify at compile time a non-boost numerical type (as I have done.) I'd much rather make my library default to boost::mp::number<rational... instead of long double so that it is robust out of the box and then 99.9% of people would never need to use the mechanism to override with gmp because the lazy exact arithmetic I use makes the performance of the high precision numerical data type irrelevant. We are all very busy people. I've been working myself half to death lately. I would have liked to try out the library with mine to make sure that everything hooks together satisfactorily and most importantly works correctly. Testing the correctness of my algorithms using this numerical data type would be somewhat tedious, however, because passing tests is not proof of correctness. I would need to be very thorough to make sure things were correct, and thorough is time consuming. Right now I'm assuming the library will be accepted and planning to do that work later, since I should probably provide support for use of it once it has been released. I've followed the entire review and discussion of the library from the first announcement up to now. Everything I've seen leads me to feel that the library should be accepted, but this is not a review, just an opinion from an interested observer. I'm particularly pleased to see that the library seems to have two motivated maintainers. We know we can trust John, and I really like Christopher's energy. It is a shoe- in for acceptance. Regards, Luke
participants (5)
-
Christopher Kormanyos -
John Maddock -
Phil Endecott -
Simonson, Lucanus J -
Steven Watanabe