Boost logo

Boost :

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.


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