[boost] [xint] review

Subject: [boost] [xint] review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-03-09 16:44:55

Dear All,

Here is my review of the proposed XInt library.

There seem to be several issues with the design of this library; all 
have been discussed before at length so I will simply summarise:

1. Performance of small and fixed-length integers is poor.  This could 
be resolved by storing fixed-length values on the stack, or by using 
some sort of small buffer optimisation.

2. There is no assembler, and there are no "hooks" in the 
implementation where a contributor could insert assembler fragments for 
critical code.

3. Performance is hindered by the creation of temporaries in 
expressions such as a = b+c+d+e; a system of expression templates that 
allowed the expression to be computed "slicewise" would eliminate the 
need for temporaries.

4. The interface is not very generic; for example the 
is_(probably)_prime function cannot be used on a regular int; the 
implementation operates on the internal representation of the integer 
for no apparent reason.  (If the reason is performance, then that 
itself indicates a deficiency in the interface.)  (Aside: I feel that 
is_(probably)_prime would be better in Boost.Math, which is apparently 
already organised into sub-libraries.)  Also the basic algorithms 
(addition, multiplication...) are not generic, i.e. they cannot be used 
other than on the provided integer type (this would matter much less if 
the provided type were more performant).

5. Although I don't have strong views either way on COW, I do feel that 
in 2011 we should focus primarily on thread-safe code i.e. 
single-thread code is now the special case, not the norm.  So if COW is 
to be used it should be thread-safe COW.

6. Apparently sign-magnitude is used without tweaks for bitwise 
operations, giving "wrong" answers for negatives (in contrast to e.g. 
GMP which stores sign-mag yet gives "right" answers, IIUC).

7. Choice of algorithms for some operations (e.g. sqrt) seems to have 
poor big-O complexity.

In view of these issues, I do not believe that this library should be accepted.

I am not suggesting that all of these issues need to be fixed for the 
library to be acceptable.  Boost libraries do not have to be perfect.  
I just believe that the current state is below the required threshold.

Standard answers:

- What is your evaluation of the design?

See above.

- What is your evaluation of the implementation?

It seems reasonably bug-free.

- What is your evaluation of the documentation?

I'm not a huge fan of doxygen, but that's mostly my problem.  The docs 
would benefit hugely from some benchmarks.

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

I've never needed a large integer library.

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

Yes, g++ (ARM Linux), no problems.

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

Two or three hours work, running benchmarks, reading a few bits of the 
source, and following the discussion.

- Are you knowledgeable about the problem domain?

More so now than a week ago, but fundamentally no.

One final comment: many reviews end with some sort of "accepted subject 
to changes" result.  This indicates some trust that the author would be 
able to make the required changes without further review.  I do not 
believe that this would be appropriate in this case.

Regards,  Phil.