Re: [boost] [xint] Boost.XInt formal review

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