Re: [boost] [XInt] review

Subject: Re: [boost] [XInt] review
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-09 09:13:59

On Mon, 7 Mar 2011 17:15:58 -0800
Steven Watanabe <watanabesj_at_[hidden]> wrote:

> *I vote to accept XInt into Boost*

Thank you for the review, and your extensive comments.

> 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.

Yes, a lot of the functions can be split off if the client code won't
need them. I've made a note to do so soon. There's already an
include-everything header, so that won't break client code even if I
can't get it in the first Boost version.

>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. 

Only to disable it on objects returned from the library. Which is all
that should be needed for thread safety, more on this below.

> boost::xint::integer is totally not thread-safe, because of the race
> on the reference count. 

I recently swore to eat my keyboard without salt if anyone found a flaw
in the thread-safety design (rather than an implementation bug). I like
this keyboard, but I doubt it would taste very good, especially without
any salt.

Every integer_t object will have unique storage when it's returned to
user code (assuming the threadsafe option isn't disabled), and no two
threads will ever have access the same integer_t object within the
library. With that in mind, should I get the knife and fork ready?

> 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.

That's intended as read-only static data. The inc/dec functions were
modifying the copy_count though, so you're right. I've changed it so
that the copy_count member is never altered on objects marked
read-only either. If CoW survives, I'll find a better solution.

> Thoughts on separating out the arithmetic algorithms: [...] * 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.

The design I see would require all such user-supplied magnitude types
to have a reallocation function that the library can call. If that
function doesn't provide the memory requested, the user gets only the
lower bits of the correct result. The code for handling that is already
in the library, for the fixed-length integers.

> - 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 think that can be handled by putting the onus of dealing with it onto
the person providing the new type.

> I think I agree that is_prime should be called is_probably_prime.

Already done in my working copy.

> exceptions.hpp:
>
> What is the rationale for on_exception?

<http://www.oakcircle.com/xint_docs/exception_handler.html>

> normally you should just use BOOST_THROW_EXCEPTION.

Hm... it looks like that could be used with -fno-exceptions. Added to
the list.

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

No probably to it, CRTP is a much better choice. I'll be changing it to
that for the next release.

> 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.

digit_t is already slated to be moved to the boost::xint namespace in
the next release.

> 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.

I've never tried it, but if it has the standard allocator interface, I
believe you can. Just specify the allocator class as a parameter to the
integer_t class template. (The documentation for that has already been
improved for the next release.)

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

So far as I know, the only reason they would ever throw is if they're
passed a Not-a-Number value, or if something unpredictable has gone
seriously wrong.

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

It would be highly unusual, but not specifically an error, assuming the
string contains a base-ten numeric value.

> 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.

Couldn't that prevent some less-intelligent compilers from optimizing
out the test?

> 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. 

You're right, the comment is mistaken.

> Of course this is rather hypothetical, since we always work with
> powers of 2.

Those types, and the originally-arcane methods used to come up with
them, were intended to support *any* platform, no matter how odd. I've
heard horror stories of systems with seventeen-bit words and nine-bit
characters. :-)

> magnitude_t:
> * It probably needs to be POD for you to make assumptions about the
> layout.

The "struct hack" is a standard C idiom, and has been for as long as C
has been around. It only became explicitly documented behavior in C99,
but it works with all known C and C++ compilers; I checked very
thoroughly, and even asked on this list (where one might reasonably
expect to find people with experience with really odd architectures and
compiler setups), and wasn't able to find a single report of a compiler
where it would fail.

> * 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.

I wanted something that would fail loudly if the library attempted to
use it. Making it private would probably work even better.

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

I prefer to reserve exceptions for exceptional behavior, primarily
errors. A number that doesn't have an inverse isn't really exceptional,
there are many such values.

> 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.

The ones in that file are for internal use only, but your point is
valid for the log2 function in integer.cpp.

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

I'd forgotten that was even there. :-( You're right, it should... and
now does, optionally.

> I don't think std::showbase works correctly with std::setw.  (This is
> a very common problem with ostream operators) [...]

It looks like the standard library mostly works the way my code does,
but has some quirks with zero values that I'm not presently emulating,
according to
<http://stackoverflow.com/questions/3273654/ostream-showbase-non-present-for-zero-value-and-internal-doesnt-work-for-handle>.

> 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.

GCC balks at some of those tests here (haven't tried MSVC yet). Maybe
you can see why? In test_invalid_overload.cpp:

Line 34 says "result.message() =", which the compiler won't accept. I'm
not sure what is intended there.

The compiler balked at lines 54 and onward ("error: no matching
function for call to ‘boost::xint::integer_t<>::integer_t(const
unrelated_type&)’"). No idea how to fix it, other than removing
unrelated_type from the mpl::vector.

The test_complement case reports "error: cannot pass objects of
non-trivially-copyable type ‘class boost::xint::integer’ through
‘...’".

I was able to get test_arithmetic_conversion.cpp to compile and work,
but only after changing the uniform_int_distribution.hpp include to
uniform_int.hpp instead, and tweaking the first two lines of the
test_arithmetic function. I'm not using the very latest Boost yet, but
I'm using a very recent one (1.45), so I'm not sure what happened there.

Does fail_adl_detail.cpp compile on your system? It shouldn't, so far
as I can see, but on mine it does.

Again, thank you.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*