[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often
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
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
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
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=gccview=revrev=173400 Log: 2011-05-04 Marc Glisse marc.gli...@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
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.
[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often
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
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
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
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
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
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
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
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_addratio1,(m-1)*(m-2),ratio1,(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
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
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=gccview=revrev=170616 Log: 2011-03-02 Marc Glisse marc.gli...@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
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
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
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
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
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
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
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
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
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
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.
