Re: [boost] Multiprecision vs. xint

Subject: Re: [boost] Multiprecision vs. xint
From: John Maddock (boost.regex_at_[hidden])
Date: 2012-06-18 08:33:40

> There is a problem here - in that there is no "one true way"
> for a slightly larger integer type - it all depends on how much
> larger, and the particular size of the integers it encounters
> in practice.

>What about int_fast32_t and friends as models?  That is, might there be 
>different types for different purposes that can be selected based upon how 
>the main class
>template is parameterized?  IOW, allow the user to indicate which backend 
>(or intermediate bridge layer) to use based upon the user's own preference 
>or performance analysis.

Nod.

> For example:
>
> * For int128, simplicity will probably always win out, making
> the "naive" implementation the best.
> * By the time you get to say int1024, computational
> complexity wins out, so something like the fixed sized integers
> already provided are likely to be best (modulo the fact that
> more profiling and fine tuning is still required).  That's why
> I was persuaded to switch to those prior to the review from a
> more traditional fixed int (like Phil's).
> * To complicate matters more, for say int1024, the "naive"
> version wins if most of the values use all the bits, where as
> the version that maintains a runtime-length wins when most
> values are small.

>Cannot those options be selected by the user?

Not yet, it gets kind of complicated real fast if there are too many 
options, but yes I realise theres a lot of detailed analysis to do to figure 
out what can be improved where.

> Having said all that, I think it is true that a weakness of
> the library is inherent overhead when dealing with "trivial"
> types that are extremely close to the metal to begin with.
> Probably that reflects the original focus of the library where
> this is a non-issue.

>Surely templates can select an optimal backend and erase all overhead in 
>using it.  For example, if the user selects the naïve, but optimal, backend 
>for a
>128 bit integer type, must there necessarily be overhead that wouldn't 
>exist in a customized 128 bit integer type?  If your current design imposes 
>such overhead,
>might there be a way to refactor the design such that one interface (the 
>user-facing class template) can select the right IL to bridge that 
>interface and the optimal backend?

I don't know, it's a question of getting stuck in and analysing specific use 
cases and seeing why they do/don't perform as you expect.  The problem is 
that if the operation being performed is sufficiently "trivial" 
(algorithmically speaking), then quite simple front end changes can have a 
surprising (and also quite capricious) performance change.  So typically you 
improve one thing, and something else suffers an inexplicable slowdown 
:-(   All quite frustrating, but like I said there's still more to do for 
sure.  Also if folks have more "real world use cases" I'd really like to see 
them, it helps a lot.  I already have a few ideas I need to explore from 
looking at Phil's case.

> >> John's concept takes the first step toward establishing an
> >> architecture for extended numeric types.
> >
> > It is reasonable to view this as "the first step" and leave
> > the fulfillment of some of these other requirements for
> > later. However, if there is no proof of concept for the
> > various use cases, then you can't be sure the abstraction and
> > points of customizations are correct.
>
> True.  However, you can't carry on forever, you have to ask
> for a review at some point.  At present the focus is more on
> "breadth" than "depth".

>I cannot argue your point beyond saying I'd hate to think that your library 
>was accepted and then six months later you realized a
>fundamental oversight (and I don't assert there is one).  OTOH, there is no 
>requirement for backward compatibility in Boost and if
>you did discover such an oversight, you could choose to break 
>compatibility -- for a fledgling library -- for the sake of significant
>improvement and avoidance of having to creating BMP2.

I think we'd all like to avoid capricious breaking changes in the future. 
However, if someone down the road wants to introduce a number kind we 
haven't even thought of yet, it's sort of inevitable that some changes (or 
at least extensions) may be required.  It's the old chicken & egg issue, and 
I can't tell you at what point one hatches into the other ;-)

Thanks, John.