[boost] [XInt] review

Subject: [boost] [XInt] review
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2011-03-07 20:15:58

AMDG

*I vote to accept XInt into Boost*

Overall:

* The basic interface of the library is solid.
* All thread-safety issues *must* be addressed.

General: It should be possible to #include any header by itself.
I don't like the fact that you split up the library into
separate headers all of which can only be included from
the main header.

I don't have a problem with providing an
option to enable COW, however:
* It should not be used by default
* If it is off, it should be off completely.
 Currently, the threadsafe option doesn't
 seem to have any effect on COW.  boost::xint::integer
 is totally not thread-safe, because of the
 race on the reference count.  Not only that,
 constructing an integer references a global
 variable in magnitude_manager_t::zerodata.
 This means that the library currently cannot
 safely be used with multiple threads at all,
 regardless of whether I try to prevent sharing
 or not.

Thoughts on expression templates:
Expression templates are a powerfull tool.
However, I'm not convinced that they're appropriate
for this library.  Although they allow some
clever optimizations, the extra complexity
can cause confusion.  This is a fairly basic
library which we can expect to be used by
people who don't know the language well
enough to cope with the problems easily.

Thoughts on separating out the arithmetic algorithms:
* From an interface standpoint, arithmetic
 algorithms that can operate on arbitrary
 ranges are orthogonal to the functionality
 that the library provides.  An big integer type
 that is a (mostly) drop in replacement for
 int is important by itself.  IMHO, we should
 be reviewing the library that was submitted,
 not some hypothetical library that has not
 been written and has very different goals.
* I think this is a much harder problem than
 those demanding this feature seem to think.
 Just off the top of my head:
 - Memory management can't just be ignored.
   Unlike the STL algorithms, the amount of
   space required for the results is dependent
   on the values involved.  It isn't a direct
   function of the size of the input.  Not
   to mention that all but the most basic
   functions need to create intermediate results.
 - Different representations of integers can't
   easily be encapsulated behind a concept
   that the generic algorithms can use.  There
   are a quite a few possible representations.
   A class can pick one representation and
   stick with it.  Generic algorithms would
   need to handle anything.

I'd like to be able to make a fixedsize integer
that uses only stack storage.  There are two
reasons for this:
* Efficiency.  This has already been mentioned by others.
 This is not a high priority for me, since it can
 always be optimized without affecting the interface.
* Exception safety.  I have some cases where I need intermediate
 results larger than any built-in integer type.  However,
 I can easily find an upper bound on values I need to work
 with (Usually twice the size of whatever type I was given).
 I need to guarantee that these operations cannot fail.
 Just using nothrow is not an option, since NaN is
 as bad as an exception here.

I think I agree that is_prime should be called
is_probably_prime.

exceptions.hpp:

What is the rationale for on_exception?
normally you should just use BOOST_THROW_EXCEPTION.

integer.hpp

Virtual inheritance is probably wrong.
It's only needed with a diamond inheritence
graph.

Using chained inheritance instead of multiple
inheritance probably works better with the
empty base optimization.

What is the correct way to specify the allocator?
The example in the documentation shows
my_allocator<boost::xint::detail::digit_t>,
but I don't think that I as a user should
ever need to refer to namespace detail.

Can I use a Boost.Interprocess allocator to
put an integer_t in shared memory?  I doubt it
since I don't see any constructors taking an
allocator.

line 268: if (str[0] == tnan[0] && std::basic_string<charT>(str) == tnan)
You can compare a std::string directly to a const char*.

Why can the comparison operators throw?
I would have expected that they could
be implemented to never throw.

The comparison and arithmetic operators should be restricted
with SFINAE.  As written, they will allow comparison
with a string.  Is that intended?

When you test for integer_t<BOOST_XINT_APARAMS>::Nothrow && n.is_nan(),
you could just test n.is_nan() and make sure that
n.is_nan() is always false if Nothrow is true.

is_nan should be a free function, so it can overload with
is_nan for other types.

random.hpp:

Watch out for ADL issues.  Making strong_random_generator
a typedef for a type in namespace detail means that boost::xint::detail
is an associated namespace and boost::xint in *not*.

I don't think that base_random_generator is needed anymore.

addsubtract.hpp

basic_types_and_includes.hpp

digit_t:
"It must contain at least half the number of bits that a doubledigit_t
can hold,"
const std::size_t        bits_per_digit    =
   std::numeric_limits<digit_t>::digits;

These two statements are somewhat contradictory.  I believe that
you have to guarantee that the result of multiplying any two
digits together fits in a doubledigit_t.  If digit_t holds more
than half the number of bits of a doubledigit_t, then this won't
hold.  Of course this is rather hypothetical, since we always
work with powers of 2.

magnitude_t:
* It probably needs to be POD for you to make
 assumptions about the layout.
* Can't you make the assignment operator private instead
 of having it throw?  Actually if this is to avoid C4512,
 you're better off disabling the warning.

convert.hpp:

You assume that the letters are contiguous.  While
this is usually true, it is not guaranteed.  The
only guarantee that the standard gives about the
character set is that the digits 0-9 are contiguous.

to_string uses the global locale to convert
char to charT.  from_string uses implicit
conversion.  Be consistent.

gcd.hpp:
The behavior of invmod when the inverse doesn't
exist is to return zero.  Wouldn't an exception/NaN
be more consistant?

internals.hpp:
You should probably check BOOST_NO_EXCEPTIONS
(from boost/config.hpp) in addition to
BOOST_XINT_NO_EXCEPTIONS.

log2.hpp:
What about using boost/pending/integer_log2.hpp?
Perhaps this should also be called integer_log2,
to avoid confusion with std::log2 which returns
a floating point value.

prime.hpp

is_prime should take a generator instead
of creating its own.  That way random_prime
can use the same generator for everything.

randomgen.hpp:

Do you want the /dev/urandom implementation to
be buffered?  Boost.Random intentionally
uses raw file descriptors to avoid reading
more random bytes than are actually needed.

streams.hpp:

Even though you templated the stream operators
on the traits, they won't compile with anything
other than std::char_traits, because to_string
uses the default traits, and when you send a
string to a stream, the traits have to match.

I don't think std::showbase works correctly with
std::setw.  (This is a very common problem with ostream
operators)  Make sure that you handle std::internal, too.

operator>> should skip leading whitespace
(depending on whether this is set for the
stream of course.)

Tests:

You don't need to create an alias to run the tests.
Just use

run test_streams.cpp ;
run test_add.cpp ;
...

I've written a few extra test cases.
The ones called fail_*.cpp should
be marked as compile-fail, the ones
called test should pass.

Beyond that, here are a few more things
that I thought were missing from the
tests:

All the comparison operators.  Not just
operator< and operator>.

Check the behavior of <, >, <=, and >= for
equal arguments.

Check cases where the operators should
return false.

In Christ,
Steven Watanabe