Google SoC 2007 Big Integer project
Ok, problably this is the N-th proposal that you read for the big integer project, with N large as you like :), and this isn't an upside for my application, anyway these are my ideas: (1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy; (2) minimize useless object copy: where it's possible we'd have to adopt a move semantic technique as described in "http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html#Library-O... Move Solution" ; (3) use different algorithms according to the size of the numbers involved, the GMP library can be taken as an example and Knuth's TCP Vol 2 as a reference for the algorithms' implementation; (4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance; (5) implement ctors in order to inizialize a big integer from standard arithmetic type and obviously from a number represented by a string; implement conversion functions to arithmetic types and string types; (6) implement common arithmetic, shift, bitwise and comparison operators; using the boost::operator library would be usefull where this doesn't lead to a performance loss; (7) implement io stream operator; (8) basic functions: sign(), odd(), abs(), etc; numeric functions pow, sqrt, etc; algebric and combinatorial functions: factorial, gcd, etc.; there are a lot of functions we could implement : all depend on the avaible time; (9) decide if it's worth creating a specific class unsigned big integer; (10) about fixed size big integer I had tought to something like this: template< unsigned int N > class big_int; where N are the number of bits which have to be used; (11) make all that working on the larger number of architectures; write down library documentation, implement correctness and performance tests; (12) it would be nice to support infinity and indefinite forms, but it could mean performance problems because we'd have to evaluate all possible cases, maybe it will be better realize a specific wrapper/adaptor class for such a goal, moreover this class adaptor could be used also for standard integral type; Question : is it possible to get good performance without implement the basic algorithms in assembler ? Comments and critiques to my ideas are welcome. Thanks Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Marco wrote:
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
I didn't know aborting the program was more efficient than throwing an exception. Why not just invoke undefined behaviour if that allows the best efficiency?
(10) about fixed size big integer I had tought to something like this: template< unsigned int N > class big_int; where N are the number of bits which have to be used;
That could even be used to have portable types with a fixed size, since it can fall back to an existing type. However, the ability to choose the size at runtime would also be needed.
Question : is it possible to get good performance without implement the basic algorithms in assembler ?
I think some implementations don't use assembler and are quite efficient. Assembler is only a bonus.
Mathias Gaunard wrote:
Marco wrote:
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
I didn't know aborting the program was more efficient than throwing an exception.
It's not. Or at least efficiency is irrelevant once the program is dead :-)
Why not just invoke undefined behaviour if that allows the best efficiency?
Why not throw an exception? Any overhead only occurs when an error has actually happened, not on every operation. Or even better: if(error_condition) customisable_error_handler(information_about_error); And give the user a chance to decide what happens. Regards, John.
John Maddock wrote:
Mathias Gaunard wrote:
Marco wrote:
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
I didn't know aborting the program was more efficient than throwing an exception.
It's not. Or at least efficiency is irrelevant once the program is dead :-)
Why not just invoke undefined behaviour if that allows the best efficiency?
Why not throw an exception? Any overhead only occurs when an error has actually happened, not on every operation. Not quite. See below. Or even better:
if(error_condition) That is where the potential for additional overhead occurs. Now, how /serious/ it is, is an /entirely/ different matter. Obviously, it depends how much work it takes to calculate "error_condition", and how tight a loop we are in. customisable_error_handler(information_about_error);
And give the user a chance to decide what happens. -- Martin Bonner
Martin Bonner wrote:
Why not throw an exception? Any overhead only occurs when an error has actually happened, not on every operation. Not quite. See below. Or even better:
if(error_condition) That is where the potential for additional overhead occurs. Now, how /serious/ it is, is an /entirely/ different matter. Obviously, it depends how much work it takes to calculate "error_condition", and how tight a loop we are in.
Absolutely: but unless you propose to have no error handling at all, the test is the same irrespective of whether we abort or throw or whatever, isn't it? What am I missing? Cheers, John.
I could be way off base here, but I assumed the question related to the use of try/catch blocks, which are very expensive compared to unmanaged code. The divide by zero question is easy to answer, because unless one of the values is volatile, then it's more efficient to check the denominator before the division than put the division in a try/catch block. I suppose other examples are more complicated, but as far as I know for a library like this essentially nothing should use try/catch blocks, even if some code should have the capability to throw errors (which is a different matter entirely) -Hugh. On 3/23/07, John Maddock <john@johnmaddock.co.uk> wrote:
Martin Bonner wrote:
Why not throw an exception? Any overhead only occurs when an error has actually happened, not on every operation. Not quite. See below. Or even better:
if(error_condition) That is where the potential for additional overhead occurs. Now, how /serious/ it is, is an /entirely/ different matter. Obviously, it depends how much work it takes to calculate "error_condition", and how tight a loop we are in.
Absolutely: but unless you propose to have no error handling at all, the test is the same irrespective of whether we abort or throw or whatever, isn't it? What am I missing?
Cheers, John.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Hugh Wimberly wrote:
I could be way off base here, but I assumed the question related to the use of try/catch blocks, which are very expensive
What is that claim based on? The old myth saying exceptions are slower than return values, while it's actually the opposite?
compared to unmanaged code.
What is that supposed to mean? C++ has no notion of managed/unmanaged code. Even when considering the Microsoft extensions, I still don't see what exceptions have to do with managed code. (since you compare exceptions to "unmanaged" code that must mean you must consider those "managed")
The divide by zero question is easy to answer, because unless one of the values is volatile, then it's more efficient to check the denominator before the division than put the division in a try/catch block.
I don't understand how not using exceptions allow better efficiency. If you want to detect the error, you have to make a test in both cases. What's different is the way of transmitting the error.
I could be way off base here, but I assumed the question related to the use of try/catch blocks, which are very expensive
What is that claim based on? The old myth saying exceptions are slower than return values, while it's actually the opposite?
Hmm. The last time I cared about efficiency of exception handling, I was programming in C#, which takes a severe performance hit every time it enters a try block. My cursory research backs you up, that the performance hit in C++ is fairly minor unless an exception is actually thrown. Sorry about assuming something unstead of looking it up. What is that supposed to mean?
C++ has no notion of managed/unmanaged code.
Even when considering the Microsoft extensions, I still don't see what
exceptions have to do with managed code. (since you compare exceptions to "unmanaged" code that must mean you must consider those "managed")
I wasn't using managed in the technical sense, only to indicate that there's some additional code laid down on the stack inside a try block that's used to trace exceptions in a way that doesn't happen otherwise. It's obviously not managed in the sense that the code starts to perform boundry checking on arrays or whatnot.
The divide by zero question is easy to answer, because unless one of the
values is volatile, then it's more efficient to check the denominator before the division than put the division in a try/catch block.
I don't understand how not using exceptions allow better efficiency.
If you want to detect the error, you have to make a test in both cases.
I think I was confusing myself. Arithmetic errors aren't handled using exceptions, so code like try { ... } catch (Exception e) {throw DivideByZero} won't work if the try block contains just the division algorithm. I was thinking of comparing the above code to if (d == 0) throw DivdeByZero; else { ... } Which would be less silly and more efficient, but I have seen the former, especially in Java. In this case, I think I'm supposed to be comparing the second example to something that doesn't check for or throw errors at all, which seems like a bad practice to me, but is how ordinary integer operations are handled. Right? Am I still crazy? Regards, Hugh
Hugh Wimberly wrote: ...
I don't understand how not using exceptions allow better efficiency.
If you want to detect the error, you have to make a test in both cases.
I think I was confusing myself. Arithmetic errors aren't handled using exceptions, so code like try { ... } catch (Exception e) {throw DivideByZero} won't work if the try block contains just the division algorithm. I was thinking of comparing the above code to if (d == 0) throw DivdeByZero; else { ... } Which would be less silly and more efficient, but I have seen the former, especially in Java. In this case, I think I'm supposed to be comparing the second example to something that doesn't check for or throw errors at all, which seems like a bad practice to me, but is how ordinary integer operations are handled. Right? Am I still crazy?
In my experience, at least with earlier versions of MSVC under Windows, using a floating point math error handler to generate C++ exceptions improved performance of our RK5 integrator by >40% versus doing the divide by zero check in the inner loop. Also you wouldn't put the try catch block inside that inner loop, it is at the executive level, determining whether the overal operation completed, or failed. This is where the decision is made to decrease step size, or carry out some other operation. Actually that 40% was the overall frame time improvment, the time spent in the integrator was even less. Jeff Flinn
Hugh Wimberly wrote:
I could be way off base here, but I assumed the question related to the use of try/catch blocks, which are very expensive compared to unmanaged code. The divide by zero question is easy to answer, because unless one of the values is volatile, then it's more efficient to check the denominator before the division than put the division in a try/catch block. I suppose other examples are more complicated, but as far as I know for a library like this essentially nothing should use try/catch blocks, even if some code should have the capability to throw errors (which is a different matter entirely)
Right, but the library doesn't need any try...catch blocks, the user would insert those probably around the whole calculation: the overhead would be unnoticable compared to even a single BigInt divide I suspect. John.
On Fri, 23 Mar 2007 19:08:03 +0100, Martin Bonner <Martin.Bonner@pi-shurlok.com> wrote:
John Maddock wrote:
Mathias Gaunard wrote:
Marco wrote:
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
I didn't know aborting the program was more efficient than throwing an exception.
It's not. Or at least efficiency is irrelevant once the program is dead :-)
Why not just invoke undefined behaviour if that allows the best efficiency?
Why not throw an exception? Any overhead only occurs when an error has actually happened, not on every operation. Not quite. See below. Or even better:
if(error_condition) That is where the potential for additional overhead occurs. Now, how /serious/ it is, is an /entirely/ different matter. Obviously, it depends how much work it takes to calculate "error_condition", and how tight a loop we are in. customisable_error_handler(information_about_error);
And give the user a chance to decide what happens.
Sorry, maybe I don't succeed in explaining my ideas in english clearly. What I was asking myself it was if the use of exception handling can imply a possible overhead. After reading all your replies I realize that there is no need to use try/catch blocks but simply if-then instructions. The overhead problem is moved outside of the library; it is the library user to take a decision if he want to catch or not an exception. In this way it's possible for the user implement an ad hoc handle to manage the exception (nevertheless the library could also include a default sensible handle that the user can utilize if he finds that the handle is adequate). The other alternative is no error handling at all (J. Maddock) that is the library has some undefined bahaviours (M. Gaunard). Anyway to check a denominator it's not a serious overhead compared to the complexity of multi precision algorithms, and it seems to me that we can say the same for the other aritmethic exceptions, so the first solution seems better. Regards, Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Mathias Gaunard wrote:
Marco wrote:
The other alternative is no error handling at all (J. Maddock) that is the library has some undefined bahaviours (M. Gaunard).
Well, isn't that how regular integers work? If you divide by zero, it's more of a programming error than an exception.
Some even claim division with zero can be meaningful, at least in a limited sense, see: http://en.wikipedia.org/wiki/James_Anderson_%28computer_scientist%29 http://en.wikipedia.org/wiki/Nullity see the BBC video or read viewers comments here: http://www.bbc.co.uk/berkshire/content/articles/2006/12/06/divide_zero_featu... http://www.bbc.co.uk/berkshire/content/articles/2006/12/06/divide_zero_featu... Have a great week-end. -- Bjørn
On Sat, 24 Mar 2007 00:15:31 +0100, Mathias Gaunard <mathias.gaunard@etu.u-bordeaux1.fr> wrote:
Marco wrote:
The other alternative is no error handling at all (J. Maddock) that is the library has some undefined bahaviours (M. Gaunard).
Well, isn't that how regular integers work?
It is.
If you divide by zero, it's more of a programming error than an exception.
well, this could become a philosophical debate. Regards, Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
(1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy;
Both can be supported easily because you can simulate a realloc via std::allocator functions. So you just need to specialize a struct on the allocator type then either simulate the realloc() or call the real realloc().
(2) minimize useless object copy: where it's possible we'd have to adopt a move semantic technique as described in "http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html#Library-O... Move Solution" ;
Haven't looked at the paper so I can't say anything except that it sounds like a good idea.
(3) use different algorithms according to the size of the numbers involved, the GMP library can be taken as an example and Knuth's TCP Vol 2 as a reference for the algorithms' implementation;
One can make these thresholds user definable at compile time because they may be different for each platform. One could write a simple test which prints suggested thresholds.
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
Not just a matter of performance but also one of interface, usually bigint will be used with data that comes from outside the program so programmer has to be prepared to catch bigint exceptions. This could be parameterized <bool use_exceptions = true/false>. A member variable to hold some state about the bigint will be useful, that way you can check for overflow, divide by zero and encode +inf, -inf, etc.
(5) implement ctors in order to inizialize a big integer from standard arithmetic type and obviously from a number represented by a string; implement conversion functions to arithmetic types and string types;
No objection.
(6) implement common arithmetic, shift, bitwise and comparison operators; using the boost::operator library would be usefull where this doesn't lead to a performance loss;
Same.
(7) implement io stream operator;
Sure.
(8) basic functions: sign(), odd(), abs(), etc; numeric functions pow, sqrt, etc; algebric and combinatorial functions: factorial, gcd, etc.; there are a lot of functions we could implement : all depend on the avaible time;
(9) decide if it's worth creating a specific class unsigned big integer;
Is there a use case? Maybe for fixed size bigint where you would want defined overflow semantics.
(10) about fixed size big integer I had tought to something like this: template< unsigned int N > class big_int; where N are the number of bits which have to be used;
Or template<unsigned int N, typename T = unsigned int> where T is the base type of the value array, i.e. array<T> data_;
(11) make all that working on the larger number of architectures; write down library documentation, implement correctness and performance tests;
Ok.
(12) it would be nice to support infinity and indefinite forms, but it could mean performance problems because we'd have to evaluate all possible cases, maybe it will be better realize a specific wrapper/adaptor class for such a goal, moreover this class adaptor could be used also for standard integral type;
I suggest as above having a state variable, I suspect checking for the states gets lost in the noise especially when the numbers get large.
Question : is it possible to get good performance without implement the basic algorithms in assembler ?
First bigint needs to be portable then one can easily add optimized paths for different architectures (and assemblers). About the question, I don't know - if you do alot of number crunching fast is never fast enough ;) Btw, this paper made big int division much more understandable to me: http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue6/spe... Kevin
On Fri, 23 Mar 2007 20:32:55 +0100, Kevin Sopp <baraclese@googlemail.com> wrote:
(1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy;
Both can be supported easily because you can simulate a realloc via std::allocator functions. So you just need to specialize a struct on the allocator type then either simulate the realloc() or call the real realloc().
Ok, I thought to something like this: template< typename BlockType = block_t, typename Allocator = bigint_allocator<BlockType> > class big_integer; where block_t is architecture dependent (but we can think it as unsigned int) and we have: template< typename T > class bigint_allocator : public std::allocator<T> { public: pointer reallocate( pointer p, size_type n ); }; I've omitted ctors and typedefs.
Both can be supported easily because you can simulate a realloc via std::allocator functions
do you mean that it's possible to use std::allocator methods in order to grow allocated space without the need to initialize it again with old data ? or do you mean only that it's possible to implement both policies: the first with std::realloc and the second using std::allocator ? In the second case the bigint_allocator template signature could become template< typename T, typename policy_tag > where policy_tag could be realloc_policy_tag or destroycreate_policy_tag (two empty structs, but it could be also possible use an enum as template parameter).
(3) use different algorithms according to the size of the numbers involved, the GMP library can be taken as an example and Knuth's TCP Vol 2 as a reference for the algorithms' implementation;
One can make these thresholds user definable at compile time because they may be different for each platform. One could write a simple test which prints suggested thresholds.
it's a good idea :)
(10) about fixed size big integer I had tought to something like this: template< unsigned int N > class big_int; where N are the number of bits which have to be used;
Or template<unsigned int N, typename T = unsigned int> where T is the base type of the value array, i.e. array<T> data_;
oh yes, I actually meant something like that.
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
Not just a matter of performance but also one of interface, usually bigint will be used with data that comes from outside the program so programmer has to be prepared to catch bigint exceptions. This could be parameterized <bool use_exceptions = true/false>. A member variable to hold some state about the bigint will be useful, that way you can check for overflow, divide by zero and encode +inf, -inf, etc.
(12) it would be nice to support infinity and indefinite forms, but it could mean performance problems because we'd have to evaluate all possible cases, maybe it will be better realize a specific wrapper/adaptor class for such a goal, moreover this class adaptor could be used also for standard integral type;
I suggest as above having a state variable, I suspect checking for the states gets lost in the noise especially when the numbers get large.
I don't know if checking for states doesn't matter compared to the complexity of multi precision algorithms. It's possible, I should try. parametrization for infinity, NaN and exception it's ok; anyway what I wanted to point out it's that in the case there is a performance loss, managing infinity and undefined states, then it is better to implement different classes and it's so even using template parameters: for instance classes big_integer<WITH_INF> and big_integer<WITHOUT_INF> ( WITH_INF = true, WITHOUT_INF = false, and I've omitted the other template parameters ) will exdend a common class in such a way to share as much as possible, but they will be two different template specialization of <bool use_inf>.
Question : is it possible to get good performance without implement the basic algorithms in assembler ?
First bigint needs to be portable then one can easily add optimized paths for different architectures (and assemblers). About the question, I don't know - if you do alot of number crunching fast is never fast enough ;)
Btw, this paper made big int division much more understandable to me: http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue6/spe...
Kevin _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Thanks a lot for your comments and for the article link I'll read it as soon as possible :) Regards, Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
do you mean that it's possible to use std::allocator methods in order to grow allocated space without the need to initialize it again with old data ?
No, I meant that you can use the realloc() function throughout the library without having to worry about whether the user passed in an allocator with std::allocator interface or an allocator that supports realloc(). By specializing a struct on the allocator type, it will act as a proxy and you call the struct's realloc() in the library. If the user passes in std::allocator the proxy realloc() function will still do an alloc/copy/destroy.
(4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance;
Not just a matter of performance but also one of interface, usually bigint will be used with data that comes from outside the program so programmer has to be prepared to catch bigint exceptions. This could be parameterized <bool use_exceptions = true/false>. A member variable to hold some state about the bigint will be useful, that way you can check for overflow, divide by zero and encode +inf, -inf, etc.
(12) it would be nice to support infinity and indefinite forms, but it could mean performance problems because we'd have to evaluate all possible cases, maybe it will be better realize a specific wrapper/adaptor class for such a goal, moreover this class adaptor could be used also for standard integral type;
I suggest as above having a state variable, I suspect checking for the states gets lost in the noise especially when the numbers get large.
I don't know if checking for states doesn't matter compared to the complexity of multi precision algorithms. It's possible, I should try.
parametrization for infinity, NaN and exception it's ok; anyway what I wanted to point out it's that in the case there is a performance loss, managing infinity and undefined states, then it is better to implement different classes and it's so even using template parameters: for instance classes big_integer<WITH_INF> and big_integer<WITHOUT_INF> ( WITH_INF = true, WITHOUT_INF = false, and I've omitted the other template parameters ) will exdend a common class in such a way to share as much as possible, but they will be two different template specialization of <bool use_inf>.
It sounds like this will make things more complex than necessary. I just looked at the GMP manual [http://gmplib.org/manual/] and it looks like they don't support infinities etc. in fact they don't handle division by zero either because "This lets a program handle arithmetic exceptions in these functions the same way as for normal C int arithmetic." Kevin
On Sat, 24 Mar 2007 12:31:41 +0100, Kevin Sopp <baraclese@googlemail.com> wrote:
do you mean that it's possible to use std::allocator methods in order to grow allocated space without the need to initialize it again with old data ?
No, I meant that you can use the realloc() function throughout the library without having to worry about whether the user passed in an allocator with std::allocator interface or an allocator that supports realloc(). By specializing a struct on the allocator type, it will act as a proxy and you call the struct's realloc() in the library. If the user passes in std::allocator the proxy realloc() function will still do an alloc/copy/destroy.
Ok, now I understand what you meant.
I don't know if checking for states doesn't matter compared to the complexity of multi precision algorithms. It's possible, I should try.
parametrization for infinity, NaN and exception it's ok; anyway what I wanted to point out it's that in the case there is a performance loss, managing infinity and undefined states, then it is better to implement different classes and it's so even using template parameters: for instance classes big_integer<WITH_INF> and big_integer<WITHOUT_INF> ( WITH_INF = true, WITHOUT_INF = false, and I've omitted the other template parameters ) will exdend a common class in such a way to share as much as possible, but they will be two different template specialization of <bool use_inf>.
It sounds like this will make things more complex than necessary.
I agree with you
I just looked at the GMP manual [http://gmplib.org/manual/] and it looks like they don't support infinities etc. in fact they don't handle division by zero either because "This lets a program handle arithmetic exceptions in these functions the same way as for normal C int arithmetic."
well, anyway even if a division by zero throws an exception, a program could handle it in two way: the classical one checking the denominator argument before passing it to the division operator, and the one offered by the library by sourrounding the division operation with a try/catch block; the two methods are not exclusive. Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Marco wrote:
(1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy;
Ion Gaztañaga has made a proposal to the C++ standard to enhance standard allocators to support in-place growing and shrinking. He calls those "version 2" allocators. Maybe you could simply use that interface.
On Sat, 24 Mar 2007 00:34:29 +0100, Mathias Gaunard <mathias.gaunard@etu.u-bordeaux1.fr> wrote:
Marco wrote:
(1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy;
Ion Gaztañaga has made a proposal to the C++ standard to enhance standard allocators to support in-place growing and shrinking. He calls those "version 2" allocators.
Maybe you could simply use that interface.
Thank you, I'll read the paper. Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
participants (8)
-
Bjørn Roald -
Hugh Wimberly -
Jeff F -
John Maddock -
Kevin Sopp -
Marco -
Martin Bonner -
Mathias Gaunard