[xint] Performance of fixed-size large integers
Dear All, I've never needed to use arbitrary-precision integers, but I have sometimes wanted large fixed-size integers like uint128_t, and so I've had a quick look at that aspect of the proposed Xint. The docs' front page has a link under "Detailed Usage Information" to "Fixed-Length Integers" - which is not really very detailed, and has examples in the notes like "integer_t<8>" that don't work. I established quickly enough that the correct syntax is integer_t<fixedlength<8>>. Also I noted that the conventions here don't match the built-in (u)intN_t types, i.e. int64_t vs. int63_t and the "wrap-around" behaviour. Perhaps there is some rationale for this, but I would be happier to see it consistent with the built-in types. (It might also be appropriate to think about how this could work with the existing Boost.Integer.) I have done a quick test of the performance of a 96-bit type as follows: typedef boost::xint::integer_t< boost::xint::options::fixedlength<96>
uint96_t;
uint96_t a = 0; uint96_t b = 0; for (int i=1; i<loops; ++i) { a = a + a + (a & b) + i; b = b + i; } This is an entirely contrived example, but the point is to minimise the work that I have to do to create something to compare it with; by using only operator+ and operator&, I can quickly hack together this: struct uint96_t { uint32_t top; uint32_t mid; uint32_t bottom; uint96_t() {} uint96_t(uint32_t val): top(0), mid(0), bottom(val) {} }; uint96_t operator&(uint96_t a, uint96_t b) { uint96_t r; r.top = a.top & b.top; r.mid = a.mid & b.mid; r.bottom = a.bottom & b.bottom; return r; } uint96_t operator+(uint96_t a, uint96_t b) { uint96_t r; __asm__( "adds %0, %3, %6\n" // Add and set carry flag "adcs %1, %4, %7\n" // Add with carry-in and set carry flag "adc %2, %5, %8\n" // Add with carry-in. : "=r" (r.bottom), // %0 "=r" (r.mid), // %1 "=r" (r.top) // %2 : "r" (a.bottom), // %3 "r" (a.mid), // %4 "r" (a.top), // %5 "r" (b.bottom), // %6 "r" (b.mid), // %7 "r" (b.top) // %8 : "cc" ); return r; } It seems to me that that is several hundred times faster than the Xint code (on my 1.2 GHz ARM test system). Yes, it requires assembler in order to do multi-word addition with carry, but we can write a less efficient portable version of that: uint96_t operator+(uint96_t a, uint96_t b) { uint96_t r; r.bottom = a.bottom + b.bottom; int carry0 = r.bottom < a.bottom ? 1 : 0; r.mid = a.mid + b.mid + carry0; int carry1 = r.mid < a.mid ? 1 : 0; // hmm, not totally sure about that... r.top = a.top + b.top + carry1; return r; } This is about half the speed of the assembler, but still hundreds of times faster than the Xint code. Based on that, I think the claim that the library is "fast" on its front page needs substantiating. I encourage anyone with experience of arbitrary-precision variable-length numbers to run some quick benchmarks. (Or, maybe I'm doing something horribly wrong here. I haven't even checked that I get the right answer.) Other reviews have reported that in this fixed-length case the library still stores some overhead in addition to the actual data. That's unfortunate as I would like to be able to, for example, store values in a memory-mapped file, or to use them in e.g. Beman's proposed b-tree library. I don't want to write a review that says "This library doesn't do what I want, therefore it should be rejected". No doubt others will find applications where it will be useful. But I think the performance when used for fixed-size integers should be investigated. Regards, Phil.
On Thu, 03 Mar 2011 19:04:44 +0000 "Phil Endecott" <spam_from_boost_dev@chezphil.org> wrote:
[...] The docs' front page has a link under "Detailed Usage Information" to "Fixed-Length Integers" - which is not really very detailed, and has examples in the notes like "integer_t<8>" that don't work. I established quickly enough that the correct syntax is integer_t<fixedlength<8>>.
Apologies, that was left over from an earlier iteration of the library and has now been corrected.
Also I noted that the conventions here don't match the built-in (u)intN_t types, i.e. int64_t vs. int63_t and the "wrap-around" behaviour. Perhaps there is some rationale for this, but I would be happier to see it consistent with the built-in types. [...]
Sorry, but the library doesn't use two's complement representation (there's no high-bit on arbitrary-length integers, so it can't), so that would only be possible with code specifically written for fixed-length integers.
[...] It seems to me that that is several hundred times faster than the Xint code (on my 1.2 GHz ARM test system). [...] This is about half the speed of the assembler, but still hundreds of times faster than the Xint code. [...]
I'll be happy to accept patches.
I don't want to write a review that says "This library doesn't do what I want, therefore it should be rejected". No doubt others will find applications where it will be useful. But I think the performance when used for fixed-size integers should be investigated.
Fixed-size integers are definitely second-class citizens right now, simply due to time and manpower constraints. As the library matures, I think you'll see serious efficiency improvements. -- Chad Nelson Oak Circle Software, Inc. * * *
Le vendredi 04 mars 2011 à 02:10 -0500, Chad Nelson a écrit :
On Thu, 03 Mar 2011 19:04:44 +0000 "Phil Endecott" <spam_from_boost_dev@chezphil.org> wrote:
[...] The docs' front page has a link under "Detailed Usage Information" to "Fixed-Length Integers" - which is not really very detailed, and has examples in the notes like "integer_t<8>" that don't work. I established quickly enough that the correct syntax is integer_t<fixedlength<8>>.
Apologies, that was left over from an earlier iteration of the library and has now been corrected.
Also I noted that the conventions here don't match the built-in (u)intN_t types, i.e. int64_t vs. int63_t and the "wrap-around" behaviour. Perhaps there is some rationale for this, but I would be happier to see it consistent with the built-in types. [...]
Sorry, but the library doesn't use two's complement representation (there's no high-bit on arbitrary-length integers, so it can't), so that would only be possible with code specifically written for fixed-length integers.
[...] It seems to me that that is several hundred times faster than the Xint code (on my 1.2 GHz ARM test system). [...] This is about half the speed of the assembler, but still hundreds of times faster than the Xint code. [...]
I'll be happy to accept patches.
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem? Ivan
On Fri, 04 Mar 2011 09:03:16 +0100 Ivan Le Lann <ivan.lelann@free.fr> wrote:
I'll be happy to accept patches.
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem?
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/205549> -- Chad Nelson Oak Circle Software, Inc. * * *
On 04/03/2011 14:28, Chad Nelson wrote:
On Fri, 04 Mar 2011 09:03:16 +0100 Ivan Le Lann<ivan.lelann@free.fr> wrote:
I'll be happy to accept patches.
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem?
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/205549>
Just drop the whole copying everywhere and COW idea, it's just making your code more complex and preventing many simple optimizations.
On Fri, 04 Mar 2011 17:36:15 +0100 Mathias Gaunard <mathias.gaunard@ens-lyon.org> wrote:
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem?
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/205549>
Just drop the whole copying everywhere and COW idea, it's just making your code more complex and preventing many simple optimizations.
My, you're good. I've never before met anyone who can profile code in his head and come up with the optimal solution without even touching a compiler. My hat is off to you, sir. If, after fixing the pass-by-reference stuff, testing proves that the COW code isn't an improvement, I'll certainly remove it. If not, you're welcome to pound salt. -- Chad Nelson Oak Circle Software, Inc. * * *
On 04/03/2011 17:53, Chad Nelson wrote:
On Fri, 04 Mar 2011 17:36:15 +0100 Mathias Gaunard<mathias.gaunard@ens-lyon.org> wrote:
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem?
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/205549>
Just drop the whole copying everywhere and COW idea, it's just making your code more complex and preventing many simple optimizations.
My, you're good. I've never before met anyone who can profile code in his head and come up with the optimal solution without even touching a compiler. My hat is off to you, sir.
If, after fixing the pass-by-reference stuff, testing proves that the COW code isn't an improvement, I'll certainly remove it. If not, you're welcome to pound salt.
It's not a matter of profiling, it's a matter of logic. The point of COW is that if you copy but you don't really want to copy (i.e. you're not going to write to your copy), then you don't have to perform a deep copy, only a shallow copy. But if you copy only if you really *need* to copy, then there is no use whatsoever for COW, since every shallow copy will end up doing a write and invoking the real deep copy. Because if you didn't need to write to it and not affect the original, you wouldn't copy it in the first place. The point of move semantics is to allow you to not have to copy something when you don't really need to, making COW completely obsolete for scenarios that do not involve partial sharing. This is a fact and a reality, not something you can disprove with benchmarks.
On 4 Mar 2011, at 17:46, Mathias Gaunard wrote:
On 04/03/2011 17:53, Chad Nelson wrote:
On Fri, 04 Mar 2011 17:36:15 +0100 Mathias Gaunard<mathias.gaunard@ens-lyon.org> wrote:
I ran no benchmarks but delving through magnitude_manager_t seems enough to understand the problem. Do you think specializing this class on Bits parameter to be stack based for non zero values could solve this performance problem?
<http://permalink.gmane.org/gmane.comp.lib.boost.devel/205549>
Just drop the whole copying everywhere and COW idea, it's just making your code more complex and preventing many simple optimizations.
My, you're good. I've never before met anyone who can profile code in his head and come up with the optimal solution without even touching a compiler. My hat is off to you, sir.
If, after fixing the pass-by-reference stuff, testing proves that the COW code isn't an improvement, I'll certainly remove it. If not, you're welcome to pound salt.
It's not a matter of profiling, it's a matter of logic.
The point of COW is that if you copy but you don't really want to copy (i.e. you're not going to write to your copy), then you don't have to perform a deep copy, only a shallow copy.
But if you copy only if you really *need* to copy, then there is no use whatsoever for COW, since every shallow copy will end up doing a write and invoking the real deep copy. Because if you didn't need to write to it and not affect the original, you wouldn't copy it in the first place.
The point of move semantics is to allow you to not have to copy something when you don't really need to, making COW completely obsolete for scenarios that do not involve partial sharing.
This is a fact and a reality, not something you can disprove with benchmarks.
There are still cases where COW can beat move semantics. For example, I have need of the same integer in multiple places. I have found immutable COW strings (without thread safety) still beat copying, move semantic aware strings on projects I work on, although the move semantics has massively closed the gap. Also my fellow developers often don't "std::move" things as often as they could. I'm not sure in practice if there is likely to be much call for producing copies of integers, as opposed to moving them, or accepting them to functions by reference, but I wouldn't discard COW completely without benchmarks. I do agree however that in general functions should be changed to accept by reference, unless in those functions the integer itself would be changed of course.
On 04/03/2011 19:01, Christopher Jefferson wrote:
There are still cases where COW can beat move semantics. For example, I have need of the same integer in multiple places.
Then you should have all those places refer to the same integer, not make all those places hold a copy of it.
On 04/03/2011 19:36, Mathias Gaunard wrote:
On 04/03/2011 19:01, Christopher Jefferson wrote:
There are still cases where COW can beat move semantics. For example, I have need of the same integer in multiple places.
Then you should have all those places refer to the same integer, not make all those places hold a copy of it.
You could use boost::flyweight to achieve this. In any case it's somewhat you build on top of an object for a specific application, not a property of the object itself.
From: Mathias Gaunard <mathias.gaunard@ens-lyon.org> To: boost@lists.boost.org Sent: Fri, March 4, 2011 8:36:05 PM Subject: Re: [boost] [xint] Performance of fixed-size large integers
On 04/03/2011 19:01, Christopher Jefferson wrote:
There are still cases where COW can beat move semantics. For example, I have need of the same integer in multiple places.
Then you should have all those places refer to the same integer, not make all those places hold a copy of it.
We can all argue that move is sometimes better then COW and we can argue that COW is in past as move semantics is the future. I just want to remind few things: 1. Most of compiles that use Boost today and will use it for many years do not support rvalue reference and real move semantics. 2. As long as it is not in the main stream (and it is not) most of qualified programmers are not going to use std::move as it is not portable and makes the software to depend on very recent compilers versions and on the standard that was not even released yet(!) 3. COW is widely used technique. What is very important, is that it is in use in common practice in many libraries and places. It is well understood by good C++ programmers. Yes, it is probably good to have support of move semantics but do not expect it to me the mainstream in near future. So you need to ask yourself: 1. Who benefits from COW semantics? 2. Who benefits from move semantics? I personally think that COW approach would be very useful for most of users while move is "nice-to-have". And to clarify it: I'm talking about real world and real programmers who deal and maintain real code. I think that COW approach is the correct approach at this point in the real world applications. My $0.02 Artyom
At Fri, 4 Mar 2011 13:58:36 -0800 (PST), Artyom wrote:
I personally think that COW approach would be very useful for most of users while move is "nice-to-have".
That's interesting, but it doesn't help me form my own opinion. Maybe if you told us on what basis you came to that conclusion, it would be more helpful. Have you done any tests to see how easily/quickly a type implemented with move emulation works as compared to one implemented with COW? Have you got concrete examples? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
----- Original Message ----
From: Dave Abrahams <dave@boostpro.com> To: boost@lists.boost.org Sent: Sat, March 5, 2011 12:21:50 AM Subject: Re: [boost] [xint] Performance of fixed-size large integers
At Fri, 4 Mar 2011 13:58:36 -0800 (PST), Artyom wrote:
I personally think that COW approach would be very useful for most of users while move is "nice-to-have".
That's interesting, but it doesn't help me form my own opinion. Maybe if you told us on what basis you came to that conclusion, it would be more helpful. Have you done any tests to see how easily/quickly a type implemented with move emulation works as compared to one implemented with COW? Have you got concrete examples?
I'm not talking about performance I'm talking about what users would do. How many developers would write: { ... foo.set_value(boost::move(some_big_int)); // some big int goes out of scope } Over { ... foo.set_value(some_big_int); // some big int goes out of scope } In case you really need a copy of the value and not reference/const reference. We should remember that not all Boost audience is familiar with "movable" concept. Even good C++ programmers do not really live on the edge and use the-state-of-the-art tools. And this is the vast majority of good C++ programmers. Now if we take a look on thous who are actually going to use Xint - algorithms developers, mathematicians and cryptographers who actually use and know C++ but do not live at the edge. So I can say that COW would give an immediate benefit while MOVE would give some benefit to some users. I'm telling let's look on the wider picture and not the narrow one. Finally we write our libraries to be useful for much less competent programmers. And unfortunately this is the reality. I think it is likely smart users would rather use the old school move set_value(int_type &integer) { integer_.swap(integer); } Then boost::move. And BTW it would be more clear for vast majority of code maintainers that are even less competent then the mathematicians who had written the code at the begging. It is sad but this is the reality, because I see at daily basis what kind of code the real programmers write, and Boost.Move is far beyond their capabilities. That is why COW would be much better for real programmers at least in near 5 years till boost::move or std::move would become mainstream. Artyom
Le samedi 05 mars 2011 à 01:43 -0800, Artyom a écrit :
----- Original Message ----
From: Dave Abrahams <dave@boostpro.com> To: boost@lists.boost.org Sent: Sat, March 5, 2011 12:21:50 AM Subject: Re: [boost] [xint] Performance of fixed-size large integers
At Fri, 4 Mar 2011 13:58:36 -0800 (PST), Artyom wrote:
I personally think that COW approach would be very useful for most of users while move is "nice-to-have".
That's interesting, but it doesn't help me form my own opinion. Maybe if you told us on what basis you came to that conclusion, it would be more helpful. Have you done any tests to see how easily/quickly a type implemented with move emulation works as compared to one implemented with COW? Have you got concrete examples?
I'm not talking about performance I'm talking about what users would do.
How many developers would write:
{ ... foo.set_value(boost::move(some_big_int)); // some big int goes out of scope }
Over
{ ... foo.set_value(some_big_int); // some big int goes out of scope }
In case you really need a copy of the value and not reference/const reference.
We should remember that not all Boost audience is familiar with "movable" concept. Even good C++ programmers do not really live on the edge and use the-state-of-the-art tools.
The opposite view also stands: Move will benefit to most C++ classes/functions while only those who have designed their classes to use COW can afford not to use Move. Designing a COW class is more complex than a Move enabled one. My KISS understanding of move is that it's telling me: use functional programming style, so that you don't need std::move. Of course, this is not always possible, but I think that this limits the scope of your (valid) point. Ivan
On 5 Mar 2011, at 12:04, Ivan Le Lann wrote:
The opposite view also stands: Move will benefit to most C++ classes/functions while only those who have designed their classes to use COW can afford not to use Move. Designing a COW class is more complex than a Move enabled one.
My KISS understanding of move is that it's telling me: use functional programming style, so that you don't need std::move. Of course, this is not always possible, but I think that this limits the scope of your (valid) point.
You seem to be saying that COW makes things harder on the implementor, but easier on the user (as they do not have to use either std::move, or carefully designed coding methods) Chris
Le samedi 05 mars 2011 à 12:07 +0000, Christopher Jefferson a écrit :
On 5 Mar 2011, at 12:04, Ivan Le Lann wrote:
The opposite view also stands: Move will benefit to most C++ classes/functions while only those who have designed their classes to use COW can afford not to use Move. Designing a COW class is more complex than a Move enabled one.
My KISS understanding of move is that it's telling me: use functional programming style, so that you don't need std::move. Of course, this is not always possible, but I think that this limits the scope of your (valid) point.
You seem to be saying that COW makes things harder on the implementor, but easier on the user (as they do not have to use either std::move, or carefully designed coding methods)
I only considered coding style here and from that point of view, yes, though I would not have said easier but more lenient. Unless using auto&& which can break your code just like auto_ptr did, just naming a variable prevents move. Many people use named variables for documentation and code readability. Thus I dare to say that move is "coding style touchy". Going further, the user also has to consider delivered service in terms of performance and thread safety. It seems there is a concensus against COW. I have no idea on this. I trust benchmarks and smart guys, and my intuition that simpler things are better. As I said, I consider move simpler. Having said that, we (and me first) should stop opposing COW and Move. Move is here and works at a different level. It even minimizes COW flaws. So it's not about "COW or Move?". It's about "To copy or not to copy?". I guess some people here want a C++ where you have to call std::copy to invoke a copy constructor. :-) Ivan
on 05.03.2011 at 15:04 Ivan Le Lann wrote :
The opposite view also stands: Move will benefit to most C++ classes/functions while only those who have designed their classes to use COW can afford not to use Move. Designing a COW class is more complex than a Move enabled one.
My KISS understanding of move is that it's telling me: use functional programming style, so that you don't need std::move. Of course, this is not always possible, but I think that this limits the scope of your (valid) point.
so would it be sufficient for you (and other developers) if there were a library which makes using cow for your class easier (if not trivial)? in fact i think it's not too hard to write such a library policy based, templated, with blackjack and hoockers... -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
Le samedi 05 mars 2011 à 23:22 +0300, DE a écrit :
on 05.03.2011 at 15:04 Ivan Le Lann wrote :
The opposite view also stands: Move will benefit to most C++ classes/functions while only those who have designed their classes to use COW can afford not to use Move. Designing a COW class is more complex than a Move enabled one.
My KISS understanding of move is that it's telling me: use functional programming style, so that you don't need std::move. Of course, this is not always possible, but I think that this limits the scope of your (valid) point.
so would it be sufficient for you (and other developers) if there were a library which makes using cow for your class easier (if not trivial)?
No. I might have failed to express what I meant with "complex". Even struct foo : cow <foo> {}; can be seen as complex, if you consider implications for foo. Ivan
Artyom wrote:
From: Mathias Gaunard <mathias.gaunard@ens-lyon.org> To: boost@lists.boost.org Sent: Fri, March 4, 2011 8:36:05 PM Subject: Re: [boost] [xint] Performance of fixed-size large integers
On 04/03/2011 19:01, Christopher Jefferson wrote:
There are still cases where COW can beat move semantics. For example, I have need of the same integer in multiple places.
Then you should have all those places refer to the same integer, not make all those places hold a copy of it.
We can all argue that move is sometimes better then COW and we can argue that COW is in past as move semantics is the future.
I just want to remind few things:
1. Most of compiles that use Boost today and will use it for many years do not support rvalue reference and real move semantics.
2. As long as it is not in the main stream (and it is not) most of qualified programmers are not going to use std::move as it is not portable and makes the software to depend on very recent compilers versions and on the standard that was not even released yet(!)
3. COW is widely used technique. What is very important, is that it is in use in common practice in many libraries and places. It is well understood by good C++ programmers.
Yes, it is probably good to have support of move semantics but do not expect it to me the mainstream in near future.
So you need to ask yourself:
1. Who benefits from COW semantics? 2. Who benefits from move semantics?
I personally think that COW approach would be very useful for most of users while move is "nice-to-have".
And to clarify it: I'm talking about real world and real programmers who deal and maintain real code.
I think that COW approach is the correct approach at this point in the real world applications.
My $0.02
Pass by reference is what real programmers who deal and maintain real code do. Rather that the false dicotomy between between COW and move lets answer the more fundamental question, why either? Just use expression templates. Don't bother to use proto for your expression templates, by the way, it is very easy to do yourself in this simple case. This whole argument misses the point of optimizing code that uses a bigint class. You want to reuse the memory allocated in a bigint variable over and over instead of reallocating every time. Whether you make one unneeded allocation or two is a less important consideration than whether you make one or zero since 2/1 is a lot smaller than 1/0. If a temporary is generated by the user's code they have already pessimized their code. I am sorry, but you cannot avoid allocation with a return by value semantic, only expression templates allows you to reuse the storage on the left hand side of the assignment operator. Return by value is broken whether you use COW or MOVE so how about we focus on fixing it with a nice expression template based operator syntax using pass by reference and documentation that tells the user to avoid generating temporaries if they want to write code that will run as fast as possible. If they want to write expressions that generate temporaries it will be *no slower* than the current proposal, but at least they will have the option of writing code that is fast. Right now it looks like the library needs revision before it can be accepted, and a second review is probably in order. I hope the author will rise the the challenge and overcome his defensiveness to produce something really worthwhile. As Beman said, this is the sort of thing that could become part of the standard and then compiler writers would give us really good implementation of that spec, so the focus should be on the interface and we shouldn't be in a hurry. If the best is the enemy of the good, then what is haste the enemy of? Regards, Luke
On 05/03/11 02:10, Simonson, Lucanus J wrote:
Pass by reference is what real programmers who deal and maintain real code do. Rather that the false dicotomy between between COW and move lets answer the more fundamental question, why either? Just use expression templates. +1 on this Don't bother to use proto for your expression templates, by the way, it is very easy to do yourself in this simple case. -1 on this, it is all a matter of quick hack on the living room table and extensible design. After writting tons of ET based code, i wont go back writing them by hands.
Hi Chad, Chad Nelson wrote:
"Phil Endecott" <spam_from_boost_dev@chezphil.org> wrote:
Also I noted that the conventions here don't match the built-in (u)intN_t types, i.e. int64_t vs. int63_t and the "wrap-around" behaviour. Perhaps there is some rationale for this, but I would be happier to see it consistent with the built-in types. [...]
Sorry, but the library doesn't use two's complement representation (there's no high-bit on arbitrary-length integers, so it can't), so that would only be possible with code specifically written for fixed-length integers.
Is it not possible to use the most significant bit of the current most significant word as the sign bit? (What do other implementations do?) Surely this would be much more efficient - unless there is some disadvantage that I've not spotted...
[...] It seems to me that that is several hundred times faster than the Xint code (on my 1.2 GHz ARM test system). [...] This is about half the speed of the assembler, but still hundreds of times faster than the Xint code. [...]
I'll be happy to accept patches.
Fixed-size integers are definitely second-class citizens right now, simply due to time and manpower constraints. As the library matures, I think you'll see serious efficiency improvements.
Well, is the current design of the library one that is suited to patching to make this sort of improvement? Specifically, say I want to add this as a specialisation for fixed-size storage (PSEUDO-CODE): template <int N> class integer< fixedlength<N> > { uint32_t data [ N/4 ]; }; If your implementation had a generic algorithm for addition, i.e. (PSEUDO-CODE): template <typenmame INT_ITER> void add(INT_ITER a_begin, INT_ITER a_end, INT_ITER b_begin, INT_ITER b_end) { int carry = 0; for (INT_ITER i = a_begin, j = b_begin; i != a_end; ++i, ++j) { (carry, *i) = add_with_carry( *i, *j, carry); } } then that could work with this new storage, with some extra glue to enable operator-overloading etc. (maybe using Boost.Operators). Similarly, the add_with_carry function in there could also be something that I could overload with my asm version. Based mainly on other peoples' reviews, I get the impression that it would not be so easy to make these changes - and certainly, they could not be applied by a user from the outside using the public API of the library. Regards, Phil.
On Fri, 04 Mar 2011 16:35:14 +0000 "Phil Endecott" <spam_from_boost_dev@chezphil.org> wrote:
Chad Nelson wrote:
Sorry, but the library doesn't use two's complement representation (there's no high-bit on arbitrary-length integers, so it can't), so that would only be possible with code specifically written for fixed-length integers.
Is it not possible to use the most significant bit of the current most significant word as the sign bit? (What do other implementations do?) Surely this would be much more efficient - unless there is some disadvantage that I've not spotted...
It's certainly possible, I tried it in early iterations of the library. But almost all operations other than addition and subtraction are more naturally broken down into magnitude and sign, and to get a magnitude from that representation requires extra steps to remove the sign bit and add it back later. Or, if using two's complement, to change negative numbers to positive ones and back.
[...] It seems to me that that is several hundred times faster than the Xint code (on my 1.2 GHz ARM test system). [...] This is about half the speed of the assembler, but still hundreds of times faster than the Xint code. [...]
I'll be happy to accept patches.
Fixed-size integers are definitely second-class citizens right now, simply due to time and manpower constraints. As the library matures, I think you'll see serious efficiency improvements.
Well, is the current design of the library one that is suited to patching to make this sort of improvement?
Sorry, but no. There are a number of improvements on the to-do list from the review. But as soon as those are done, it should be stable enough to accept patches.
Specifically, say I want to add this as a specialisation for fixed-size storage (PSEUDO-CODE): [...] then that could work with this new storage, with some extra glue to enable operator-overloading etc. (maybe using Boost.Operators). Similarly, the add_with_carry function in there could also be something that I could overload with my asm version. Based mainly on other peoples' reviews, I get the impression that it would not be so easy to make these changes - and certainly, they could not be applied by a user from the outside using the public API of the library.
No, they couldn't. It's not part of the library's design parameters, and I don't think it should be at present, for the reasons I've outlined in other messages. A future iteration, after the internals are stable, is another story. -- Chad Nelson Oak Circle Software, Inc. * * *
participants (10)
-
Artyom -
Chad Nelson -
Christopher Jefferson -
Dave Abrahams -
DE -
Ivan Le Lann -
Joel Falcou -
Mathias Gaunard -
Phil Endecott -
Simonson, Lucanus J