[Bug libstdc++/47913] New: [C++0x] improve ratio_add to overflow less often

[Bug libstdc++/47913] New: [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

           Summary: [C++0x] improve ratio_add to overflow less often
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: marc.glisse@normalesup.org


ratio_add currently computes something like:
gcd=gcd(den1,den2)
num=num1*(den2/gcd)+num2*(den1/gcd)
den=den1*(den2/gcd)
gcd2=gcd(num,den)
num/=gcd2
den/=gcd2

In cases where gcd2 is not 1, the computation may overflow whereas the final
result would fit. Even without that, it is possible that one or both of the
terms added in num are too large but their sum is not.

As a quality of implementation issue, it would be nice to reduce those cases a
bit. But that comes far far behind the ratio_less improvement described in PR
42622.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-27 13:54:46 UTC ---
Looks like there is a pretty simple (eg, no continued fractions & co) way to do
this: http://www.boost.org/doc/libs/1_46_0/boost/rational.hpp

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #2 from Marc Glisse <marc.glisse at normalesup dot org> 2011-02-27 19:12:07 UTC ---
(In reply to comment #1)
> Looks like there is a pretty simple (eg, no continued fractions & co) way to do
> this:

The continued fraction thing for ratio_less may actually be easier:
- compare the integral parts
- if they are equal, remove that integer and compare the inverses
- have a terminating criterion (when denominators are 1?)

> http://www.boost.org/doc/libs/1_46_0/boost/rational.hpp

The runtime fraction addition in this file is what gcc currently does. I also
looked at ratio.hpp (and what it includes), which factors out the gcd of the
numerators and multiplies back with it at the end. That's a slight but fairly
limited improvement, I'm sure we can do better.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|paolo.carlini at oracle dot |unassigned at gcc dot
                   |com                         |gnu.org

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-27 23:29:53 UTC ---
Well, if you could come up with some code... By the way, I don't think what
Boost does right now for operator+= is *exactly* the same, see the last two
lines of the comment.

I'm unassigning myself for now.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-27 23:34:10 UTC ---
By the way, a couple of testcases, would not hurt.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #5 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-01 22:15:48 UTC ---
Created attachment 23509
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23509
Overkill

I was having a hard time making it nice and clean, so I went for totally
overkill. It might be a bit scary to have 200 lines of code just to implement
an addition. And questionable whether avoiding a few overflows is worth the
complication. On the plus side, it makes it possible to give a simpler
implementation of ratio_less. And __safe_add can be removed (24 lines).

I'll try again to come up with a simpler solution.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-01 23:00:05 UTC ---
Thanks again for your help on this.

Preliminarily, a few observations: 1- Please make sure the code is minimally
documented (are the comments in longlong.h enough?); 2- I see stuff like
__builtin_clzll(__d) on __d a uintmax_t, I'm not sure it's always ok, on any
32-bit and 64-bit target. More generally - I'm asking to Marc the mathematician
here, not Mark the libstdc++ contributor - do we have a clear characterization
of which specific overflows can be avoided? Are we *really* sure the
boost::rational implementation is equivalent to GCC and weaker than what you
are proposing: the first time I looked into it I remember seeing a
normalization happening earlier toward the end, per the last two lines of that
comment:

 // Which proves that instead of normalizing the result, it is better to
 // divide num and den by gcd((a*d1 + c*b1), g)

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #7 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 09:59:52 UTC ---
(In reply to comment #6)
> 1- Please make sure the code is minimally documented (are the comments in
> longlong.h enough?)

Ok, I wasn't sure it was worth it if the code was unlikely to ever make it.

> 2- I see stuff like __builtin_clzll(__d) on __d a uintmax_t, I'm not sure it's
> always ok, on any 32-bit and 64-bit target.

Do you have a better alternative in mind? Should I reimplement it using
templates? It shouldn't be too hard, but I would check on the gcc ML first.

> More generally - I'm asking to Marc the mathematician
> here, not Mark the libstdc++ contributor - do we have a clear characterization
> of which specific overflows can be avoided?

All of those where both the input and the output are legal std::ratio.

> Are we *really* sure the
> boost::rational implementation is equivalent to GCC and weaker than what you
> are proposing: the first time I looked into it I remember seeing a
> normalization happening earlier toward the end, per the last two lines of that
> comment:
> 
>  // Which proves that instead of normalizing the result, it is better to
>  // divide num and den by gcd((a*d1 + c*b1), g)

Boost isn't exactly equivalent to gcc. Making a mix of their ratio and rational
(and possibly extrapolating a bit), they avoid some overflows of the numerator
by factoring out the gcd of the numerators, and they avoid all overflows of the
denominator by reducing the numerator with the gcd of the denominators so they
can compute directly the right denominator. They still fail on 2 types of
numerator overflow, either when the numerator is too large before
simplification with the gcd, or when the 2 products are large but their sum is
small. The example at the end of the attached file shows the second case.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 10:59:06 UTC ---
Hi,

> > 1- Please make sure the code is minimally documented (are the comments in
> > longlong.h enough?)
> 
> Ok, I wasn't sure it was worth it if the code was unlikely to ever make it.

Right. Mine was sort of a general comment: the comments in ratio_less are also
rather terse ;)

> > 2- I see stuff like __builtin_clzll(__d) on __d a uintmax_t, I'm not sure it's
> > always ok, on any 32-bit and 64-bit target.
> 
> Do you have a better alternative in mind? Should I reimplement it using
> templates? It shouldn't be too hard, but I would check on the gcc ML first.

I don't think you should really handcode something, just pick the right
__builtin_* depending on the actual type of uintmax_t (after all it's just a
typedef for one of the builtin types). Thus, if we aim for something really
general here, use just a bit of templates to pick the best match among the
various available __builtin_*, via make_signed on uintmax_t and then three
special cases for int, long, long long. Granted, probably on widespread 32-bit
and 64-bit machines, long long it's indeed a safe bet.

> > More generally - I'm asking to Marc the mathematician
> > here, not Mark the libstdc++ contributor - do we have a clear characterization
> > of which specific overflows can be avoided?
> 
> All of those where both the input and the output are legal std::ratio.

Right. I was just curious to understand whether we can somehow characterize the
inputs which are going anyway to overflow either numerator or denominator. I'm
trying to figure out what the brute force approach boils down to: is it just
matter of attempting simplification at each arithmetic operation, or we have to
do also something else, of a more global nature in order to achieve the goal?
Whatever we do, I think eventually we need something in a comment before the
code anyway...

> Boost isn't exactly equivalent to gcc. Making a mix of their ratio and rational
> (and possibly extrapolating a bit), they avoid some overflows of the numerator
> by factoring out the gcd of the numerators, and they avoid all overflows of the
> denominator by reducing the numerator with the gcd of the denominators so they
> can compute directly the right denominator. They still fail on 2 types of
> numerator overflow, either when the numerator is too large before
> simplification with the gcd, or when the 2 products are large but their sum is
> small. The example at the end of the attached file shows the second case.

Understood. Since 4.6.0 is approaching, do you think it would make sense for
this release series to modify only a bit the GCC code, to the point that we are
as good or even slightly better, if possible, than Boost, without requiring too
much new code? I fear regressions, as you of course can easily understand.
Ideally, we should add, mano a mano, testcases for each "subclass" of inputs
which we are able to process without overflowing.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #9 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 11:50:41 UTC ---
(In reply to comment #8)
> Right. Mine was sort of a general comment: the comments in ratio_less are also
> rather terse ;)

I'll try to expand a bit on them.

> I don't think you should really handcode something, just pick the right
> __builtin_* depending on the actual type of uintmax_t (after all it's just a
> typedef for one of the builtin types). Thus, if we aim for something really
> general here, use just a bit of templates to pick the best match among the
> various available __builtin_*, via make_signed on uintmax_t and then three
> special cases for int, long, long long. Granted, probably on widespread 32-bit
> and 64-bit machines, long long it's indeed a safe bet.

If intmax_t is guaranteed to be one of int/long/long long, then it seems that
it has to be equivalent to long long. I was more afraid that it might be a
bigger type than long long.

(by the way, __builtin_clz takes an unsigned argument)

> Understood. Since 4.6.0 is approaching, do you think it would make sense for
> this release series to modify only a bit the GCC code, to the point that we are
> as good or even slightly better, if possible, than Boost, without requiring too
> much new code? I fear regressions, as you of course can easily understand.
> Ideally, we should add, mano a mano, testcases for each "subclass" of inputs
> which we are able to process without overflowing.

I think there is nothing wrong with the implementation of ratio_add currently
in libstdc++ (shipping it as it is seems fine), but we could indeed easily
avoid all unnecessary denominator overflows (attachment in a minute). The
factorization of the gcd of numerators is a heuristic that sometimes helps but
doesn't really close a category of overflow, so I am more reluctant to add it,
but it is really easy if you think it should be done.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #10 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 11:53:58 UTC ---
Created attachment 23512
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23512
avoid denominator overflows (untested)

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #11 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 11:59:34 UTC ---
Thanks for the attachment. Do you have a small testcase for it? I would test
here, commit, and then we can proceed with more serious changes for post 4.6...

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #12 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 12:07:13 UTC ---
About int/long/long long I see what you mean, but we should double check that
__builtin_clzll is unconditionally available and the same as __builtin_clz if
intmax_t == int (etc): at the moment I'm not 100% sure.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #13 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 14:05:23 UTC ---
(In reply to comment #11)
> Thanks for the attachment. Do you have a small testcase for it? I would test
> here, commit, and then we can proceed with more serious changes for post 4.6...

constexpr intmax_t m=(intmax_t)1<<(4*sizeof(intmax_t)-1);
ratio_add<ratio<1,(m-1)*(m-2)>,ratio<1,(m-3)*(m-2)> >

fails with the current libstdc++, works with the small patch, works with boost.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #14 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 14:14:55 UTC ---
Excellent.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #15 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-03-02 14:58:00 UTC ---
Author: paolo
Date: Wed Mar  2 14:57:57 2011
New Revision: 170616

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170616
Log:
2011-03-02  Marc Glisse  <marc.glisse@normalesup.org>

    PR libstdc++/47913
    * include/std/ratio (ratio_add): Avoid denominator overflow.
    * testsuite/20_util/ratio/operations/47913.cc: New.


Added:
    trunk/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/ratio

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 14:59:23 UTC ---
Done. Then we can add more tests to 47913.cc.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #17 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 20:50:42 UTC ---
Some more examples. Using the constants:
m=INTMAX_MAX;
n=INTMAX_MAX/2;
p=((intmax_t)1<<(4*sizeof(intmax_t)-1))-3

(m,2)-(m,3)==(m,6)  boost should manage this one

(m/7*5-1,5)-(m-2,7)  __big_mul would be enough (__big_div is the hard thing)

(n-5,15)+(n,35)  one could cheat by removing the integral part

(p^2,(2*p-3)*(p-2))-(p+2,(p-1)*(p-2))  one may be able to write gcd=(p-2), p^2
as (p+2)*gcd+4 and the computation of the numerator becomes
gcd*((p+2)*(p-1)-(2*p-3))+4*(p-1)-4*(2*p-3) and both computations
(p+2)*(p-1)-(2*p-3) and 4*(p-1)-4*(2*p-3) fit in a intmax_t. But with a larger
gcd, they may not (I'll try to add an example later).

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #18 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 23:21:07 UTC ---
(In reply to comment #17)
> Some more examples. Using the constants:
> m=INTMAX_MAX;
> n=INTMAX_MAX/2;
> p=((intmax_t)1<<(4*sizeof(intmax_t)-1))-3
> 
> (m,2)-(m,3)==(m,6)  boost should manage this one

I'm not sure to understand, I was under the impression that right now GCC is
essentially equal to boost::rational?!?

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #19 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-03 06:41:45 UTC ---
(In reply to comment #18)
> I'm not sure to understand, I was under the impression that right now GCC is
> essentially equal to boost::rational?!?

That's the heuristic I was mentioning at the end of comment #9. I could add it
if you like. I am reluctant because, as I said, it is just a heuristic that
doesn't close a class of problems but only a few random cases.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #20 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-03 09:51:16 UTC ---
Ah, ok then: when I looked a bit into boost::rational it seemed pretty simple,
didn't notice that additional simplification. Thanks for the additional set of
tests, anyway, as soon as 4.6 is out of the door, we'll move ahead.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #21 from Marc Glisse <marc.glisse at normalesup dot org> 2011-05-04 16:27:28 UTC ---
Created attachment 24182
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24182
first iteration in patch format

Inserted in <ratio>, with some cleanup of dead code, rewrite of ratio_less. The
static_assertions should help notice problems (in particular the __big_div ones
should be good). I haven't tested much, but it seems to pass the current
testsuite. Additional tests (no time to format or check them now) are
available:
* at the end of the "overkill" attachment
* in comment #13 and comment #17

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011.05.04 16:57:29
         AssignedTo|unassigned at gcc dot       |paolo.carlini at oracle dot
                   |gnu.org                     |com
   Target Milestone|---                         |4.7.0
     Ever Confirmed|0                           |1

--- Comment #22 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-05-04 16:57:29 UTC ---
Thanks a lot Marc. Let me work on this, add all the testcases we have around,
regression test again.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #23 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-05-04 17:56:19 UTC ---
Nit (for the future): library patches are diffed from where the library
ChangeLog is.

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #24 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-05-04 23:23:57 UTC ---
Author: paolo
Date: Wed May  4 23:23:54 2011
New Revision: 173400

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173400
Log:
2011-05-04  Marc Glisse  <marc.glisse@normalesup.org>

    PR libstdc++/47913 (again)
    * include/std/ratio (ratio_add, ratio_less): Rewrite.
    * testsuite/20_util/ratio/operations/47913.cc: Extend.
    * testsuite/20_util/ratio/cons/cons_overflow_neg.cc: Adjust dg-error
    line numbers.
    * testsuite/20_util/ratio/operations/ops_overflow_neg.cc: Likewise.


Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/ratio
    trunk/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc
    trunk/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc
    trunk/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc

[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #25 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-05-04 23:33:52 UTC ---
Completely done for 4.7.0.