[xint] Some preliminary review notes
Folks, I've promised to post initial summary of Boost.Xint this Monday, but real life has interferred. I apologise. I've made a pass over review emails, and it seems that a few high-level points were raised: - Whether COW is good idea or not, and whether current COW is truly thread-safe. - Whether ET should be used - Whether data copy in "a + b + c" should be eliminated - Whether the library is "fast", in particular: - Do algorithms have best big-O complexity? - Are fixed-size integers fast enough - Whether it would be better to separate algorithms and data represetation - Whether it's possible to optimize specific cases (addition of 128-bit integers, ln+gamma, etc), by some template specializations, or other mechanism. I might have missed something, and I'd appreciate if I was set straight. Please note that we're talking about high-level issues. The number of specific comments is already too high for me to even try tracking them all. At the same time, Chad, I'd appreciate some input from you. - Could you express your current world view of those issues. Whether they are real, important, and what plan do you have about them, if any. Note that you are not required by any means to address every raised concern, but some coherent plan of action will be very important both for further development of your library and for review result. - Do you keep track of technical issues raised? Could you share that list? Thanks, -- Vladimir Prus Mentor Graphics +7 (812) 677-68-40
On Fri, 25 Mar 2011 12:06:35 +0300 Vladimir Prus <vladimir@codesourcery.com> wrote:
I've promised to post initial summary of Boost.Xint this Monday, but real life has interferred. I apologise.
Amazing how that happens, eh? ;-)
[...] At the same time, Chad, I'd appreciate some input from you.
- Could you express your current world view of those issues. Whether they are real, important, and what plan do you have about them, if any. Note that you are not required by any means to address every raised concern, but some coherent plan of action will be very important both for further development of your library and for review result.
Certainly. I've rearranged the quoted message to address them in a logical order:
- Whether it would be better to separate algorithms and data represetation
It would, and I intend to redesign the internals to accommodate this, as outlined in this message: <http://permalink.gmane.org/gmane.comp.lib.boost.devel/215984>. (I'll refer to this as "the redesign" below, as it directly affects several later answers.)
- Whether COW is good idea or not,
It's not a good idea in general, and quite possibly not a good idea for XInt either. I can't prove it either way as yet. However, I believe the point will become moot. The redesign mentioned above will allow for different data structures, and since I'll need to write one with and one without CoW to see whether it's truly an improvement, I'll provide both if it proves that it is.
and whether current COW is truly thread-safe.
Steven Watanabe discovered an implementation bug in the copy constructor, which I've since corrected. (Steven, you looked at the "postreview1" version for my CoW timings, I assume that correction looks okay?) No one else has mentioned any specific problem with it, or provided any scenario where my design wouldn't be thread-safe when used as I outlined.
- Whether ET should be used
I'm not sure whether it would be worthwhile or not. I'd like to explore it in the future, but I believe it is not the way to go at present.
- Whether it's possible to optimize specific cases (addition of 128-bit integers, ln+gamma, etc), by some template specializations, or other mechanism.
It would probably be possible with ET. I don't yet see a way to provide many of them without it. In any case, I would prefer to concentrate on optimizing the general case before worrying about specific cases.
- Whether data copy in "a + b + c" should be eliminated
If I recall the specific code that prompted that comment, there was at least one unnecessary copy there, which I will eliminate.
- Whether the library is "fast", in particular: - Do algorithms have best big-O complexity?
Two specific algorithms (multiplication of larger numbers, and likely the square-root algorithm) can be improved, and I will do so. No other algorithms were mentioned, so I assume that they are at least sufficient for the first version. I'll be happy to improve the speed of any algorithm as I find ways to do so.
- Are fixed-size integers fast enough
Fast enough for...? :-) They obviously aren't as fast as they could be at present. The redesign mentioned earlier may allow for a stack-allocated structure for fixed-size integers, which could presumably provide a large speed increase for smaller numbers. At present, that's all I can promise, as fixed-size integers are not the primary purpose of the library.
- Do you keep track of technical issues raised? Could you share that list?
The ones in my issue-tracker that I haven't yet addressed are, in (very roughly) descending order of priority: * Add CRTP * Redesign storage system * Improve efficiency of addition * Eliminate on_exception, use BOOST_THROW_EXCEPTION instead * Move or typedef xint::detail::digit_t to the xint namespace * Fix 'secure' operation * Improve policy-based design * Improve multiplication algorithm * Simplify SFINAE code for operators * Fix Linux strong_random_generator * Rename integer_t to basic_integer * Rename "secure" option * Add a sign_with_signed_zero function * Conversions to/from floating-point types * Convenience function for creating bit-masks * Add more tests * Move the random generator types to the xint namespace * Eliminate base_random_generator * Split up include files * Change pow2, factorial, nan to free functions with template parameters * Separate the random generators, let client code include them if desired * Move is_even, is_odd, and hex_digits out of the class; maybe sign too * Improve square-root efficiency * New functions or examples requested * Conversion to/from dynamic_bitset * Conversion to/from bitset * Add a throw-on-overflow option for fixed-size integers * Add is_definitely_prime I've removed documentation-only improvements from the list. Note that these are the titles of the issues only, and were intended solely as reminders to myself, so they may be cryptic. If you want more details on any particular item, please ask. -- Chad Nelson Oak Circle Software, Inc. * * *
participants (2)
-
Chad Nelson -
Vladimir Prus