Boost logo

Boost :

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2011-03-06 16:44:37


[Summary is given in the response to 3., in the beginning, for those who
don't wish to read the entire post.]

On 3/2/2011 2:58 AM, Vladimir Prus wrote:
> Boosters,
>
> the formal review of the Boost.XInt library, by Chad Nelson, starts now and will
> run through March 11.
>
> The documentation for the current version is available at:
>
> http://www.oakcircle.com/xint_docs/
>
> The source code is available via Subversion at:
>
> http://svn.boost.org/svn/boost/sandbox/xint
>
> or can be downloaded at:
>
> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=xint.zip
[...]
> 3. Please explicitly state in your review whether the library should be accepted.

No, XInt in its current incarnation should not be accepted. Yes, it
would be great for boost to formally endorse a bigint library. However,
it's not like the XInt library will be unavailable for others to use if
not accepted into boost. It seems like a lot of people's major reason
for accepting XInt is that "we desperately need a bigint library in
boost". Huh? Maybe I'm making a straw man argument here, but just
because something isn't in boost, doesn't make it unusable (although I
concede it makes it, perhaps, slightly less usable). Based on my
evaluation below, XInt has quite a lot of changes that I believe it
needs to go through before I would consider it acceptable for inclusion
in a boost release. These include some breaking interface changes. I
would like to see the implementation of said changes, or rationale for
rejecting said changes, before I vote for even conditional acceptance.

I understand, however, that my contribution to the boost community
outside of occasional participation on the developers mailing list is
scant, so I wouldn't believe it unfair to weight my vote appropriately,
as the review manager sees fit.

> 4. The general review checklist is provided below:
>
> - What is your evaluation of the design?

As far as the interface of xint::integer_t *specifically* is concerned,
it is dominated by the expected constructors and expected operator
member functions and operator free functions. There isn't really much
to evaluate here. A few of the non-operator functions kind of stick
out, though:
- boost::xint::integer_t<>::integer_t ( const integer_t< other > & b,
bool force_thread_safety = false ): This awkwardly exposes the COW
implementation details. If this functionality remains stays, this
constructor should be removed and the _make_unique member function
should be documented as part of the public interface.
- is_odd, is_even, sign, hex_digits, is_nan: These are all member
functions with no same-named free function...which makes me wonder why
these were chosen to be member functions while the likes of getbit,
setbit, is_prime, etc. were chosen to be strictly free functions.
- pow2, factorial, nan: Same deal. I don't see a problem with making
these free functions and specifying the desired return value as an
explicit template parameter. It will look the same but make the
interface more uniform:
     typedef integer_t< ... > integer_type;
     integer_type x = integer_type::pow2(n);
         vs
     typedef integer_t< ... > integer_type;
     integer_type x = pow2< integer_type >(n);
- random_by_size, random_prime: These shouldn't be part of the interface
of xint at all; more on this below.

The Boost.Parameter interface to the xint::integer_t template is fine,
although Boost.Parameter *might* be overkill. I was trying to find in
the source code where the template parameters fed to the xint::integer_t
template are interpreted, but failed. I can't seem to find where
xint::detail::integer_t_data is defined, nor any of the other base
templates for xint::integer_t. I would think they'd be in one of the
first 5 includes (not including exceptions.hpp and random.hpp) of
detail/internals.hpp. This gives me the impression that the
implementation, from a source file perspective, is badly designed, but I
might just be dense. In any case, as far as I know (that is, Chad
hasn't given me a specific example), XInt doesn't use the parameter
deduction feature of Boost.Parameter, so one could consider using a
Boost.MPL map to pack template parameters together. This gives a
slightly clunkier interface, but it avoids the need for the user to set
BOOST_PARAMETER_MAX_ARITY, so there's definitely a tradeoff.

The random number stuff and the cryptographic-specific stuff should not
be included within XInt. These should be left to other libraries
(Boost.Random in the former case). I think the scope of a bigint
library is very clearly to provide arithmetic algorithms and data
structures on which the algorithms operate. This does not include
cryptographic functionality.

As I've noted before, I'm disappointed that the algorithms Chad's used
to implement the arithmetic operations are hidden behind the
xint::integer_t class. Given the richness of these algorithms, I would
consider it a priority to expose them to the public through a generic
interface. Much has already been said about this both in the last week
and even earlier, and if Chad would like some help in this regard, I
would be willing to assist. Part (albeit a small part) of my reason for
not accepting XInt is, by Chad's own admission, that he wants the
interface to settle down before separating the algorithms out (if I'm
misinterpreting your comments, Chad, please correct), suggesting the
interface hasn't been finalized yet.

Also, I agree with Robert Stewart that the integer_t template should be
renamed basic_integer, a la basic_string.

The fixed-size integers leave something to be desired, but as Chad
himself has emphasized, they are second-class citizens. So-called
second-class citizens probably should not included within the library,
and if they are, not without huge warnings saying something like
"EXPERIMENTAL" or "SUBJECT TO CHANGE". I think a reasonable road map,
given Chad's priority to address arbitrarily-sized integers first, is to
scrap the fixed-size integers for the moment (let's concentrate on one
thing at a time!), and factor out the arithmetic algorithms in such a
way that they work on fixed-size integer concepts (including a 2's
complement implementation) equally well. At some later point, then,
include a policy-based data structure for fixed-size integers that
addresses everyone's various desires in how a fixed-size integer class
should behave.

> - What is your evaluation of the implementation?

Chad already knows my feelings on COW, but to be explicit: I'm not
necessarily against use of COW in general, but I have yet to be given a
use case where COW would outperform move emulation in theory. And I
don't fully trust the benchmarks that Chad has provided comparing COW
with move emulation, given his admission of possible errors. For
example, I believe after the first set of benchmarks, it was discovered
that some COW idioms were still being used internally when COW was
turned off and move emulation enabled; I could be remembering wrong, though.

In any case, aside from whether COW is "good" or "bad", if one wants
COW, it would probably be best built on top of a non-COW basic integer
class.

It is disturbing to me that the COW infrastructure still exists (and
even more disturbing that it is still used internally!) when COW is
supposedly disabled. Based on others' reports on the implementation,
there appears to some amount of bloat with certain pieces of the data
structure existing but remaining unused, depending on which policies are
enabled. I consider this a weakness of the implementation.

Multiplication and square roots (and possibly some other algorithms)
could likely be drastically improved from a complexity standpoint. I
know the reasons for not doing this are covered in the documentation,
but it is still a weakness in the implementation nonetheless.

> - What is your evaluation of the documentation?

I have never liked the documentation that Doxygen produces as much as
the documentation in most Boost libraries (presumably generated with
BoostBook (sp?)), but aside from that, the documentation is incomplete
in some places, as I and others have noted already.

The "fast" claim on the primary documentation page is unsubstantiated,
and, according to Chad, somewhat unsubstantiatable (assuming that's a
word). I don't think any claims about performance should be made *at
all* without some kind of benchmark or statistics to justify it. Any
library will be fast on a sufficiently fast (perhaps idealized) computer.

My evaluation of the documentation is the briefest, as I expect it will
change at least as much as the interface and implementation.

> - What is your evaluation of the potential usefulness of the library?

Oh, don't get me wrong, very useful indeed, and the library does exactly
what it says it does. I just disagree with how it effects that.

> - Did you try to use the library? With what compiler? Did you have any
> problems?

No, I did not.

> - How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?

I've probably paged through all of the documentation by this point,
accessed several of the source files through the documentation
interface, and discussed the various aspects of XInt at great lengths on
the boost developers mailing list. So I believe this is a relatively
in-depth study.

> - Are you knowledgeable about the problem domain?

Strictly as far as the arithmetic algorithms, yes, I think so. As far
as the cryptographic applications, not so much.

- Jeff


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk