[safe_numerics] questioning the basic idea
Hi, I was going through the Safe Numerics library in Boost Library Incubator, and I realized I disagree with the basic idea it is built on. I wanted to rise my concerns here. If I were to summarize in one sentence what this library is, I would say: a drop-in replacement for type int that checks for overflow in run-time and throws an exception if it finds one. Did I get it right? The remainder of this post is based on this interpretation. If so, I am not sure if this idea is a good one and worth promoting in Boost. BTW this is one of my criteria for letting a library into Boost: whether it promotes worthy ideas. I agree with the statement that a program should be UB-free. But I do not think that the approach of letting the programmer do what he did before, having the library or some run-time tool check for potential UB, and throwing an exception instead makes the program any better (or safer). It is just hiding the symptoms but not curing the disease. The programmer should not plant the UB in the first place - I agree. But this is different than first doing the mess and then having the run-time clean it up for you. I know it works for many people, in a number of languages, and it may even be considered a practical solution, but (by inclusion into Boost) I wouldn't like to be sending the message "this is how you are suppose to code". I try to recall how I use type int. I do not think I ever use it for anything that would be close to "numeric" as I know the term from math. Use Case 1 (an index): for (size_t i = 0, I = v.size(); i != I; ++i) { if (i != 0) str += ","; str += v[i]; } There doesn't appear to be a good reason to wrap it into safe<int> here, even though the incrementation could possibly overflow. Plus, it would kill my performance. Use Case 2 (using reasonably small range): I used an int to represent a square on a chessboard. There is only 64 squares, so I couldn't possibly overflow, on whatever platform. And even if there exists a platform where 64 doesn't fit into an int, I would not use safe<int> there. I would rather go for something like double_int. If I were to use some numeric computations on integers and I perceived any risk that I may overflow, I would not be satisfied with having the computations stop because of an exception. I would rather use a bigger type (BigInt?). I do not think int is even meant to be used in numerical computations. I believe it is supposed to be a building block for building more useful types like BigInt. One good usage example I can think of is this. After a while of trying to chase a bug I comae up with a hypothesis that my int could be overflowing. I temporarily replace it with safe<int> and put a break point in function overflow() to trap it and support my hypothesis. I would probably use a configurable typedef then: #ifndef NDEBUG typedef safe<int> int_t; #else typedef int int_t; #endif But is this the intent? But perhaps it is just my narrow perspective. Can you give me a real-life example where substituting safe<int> for int has merit and is not controversial? I do not mean the code, just a story. Regards, &rzej
On 18 November 2014 03:15, Andrzej Krzemienski <akrzemi1@gmail.com> wrote:
If so, I am not sure if this idea is a good one and worth promoting in Boost. BTW this is one of my criteria for letting a library into Boost: whether it promotes worthy ideas. I agree with the statement that a program should be UB-free. But I do not think that the approach of letting the programmer do what he did before, having the library or some run-time tool check for potential UB, and throwing an exception instead makes the program any better (or safer).
While I don't necessarily agree that throwing (because it basically makes the types unusable within destructors and functions called from destructors) is the correct response, there are certainly good use cases for this library.
It is just hiding the symptoms but not curing the disease. The programmer should not plant the UB in the first place - I agree. But this is different than first doing the mess and then having the run-time clean it up for you. I know it works for many people, in a number of languages, and it may even be considered a practical solution, but (by inclusion into Boost) I wouldn't like to be sending the message "this is how you are suppose to code".
C arithmetic is deceptively hard. For instance, look at < http://www.slashslash.info/2014/02/undefined-behavior-and-apples-secure-coding-guide/> and the discussion at <https://plus.google.com/+JonKalb/posts/DfMWdBKHHvJ>. All that comes from discussing this possibly incorrect code: size_t bytes = m * n; if (bytes < n || bytes < m) DoSomething(bytes); In general, you can either (a) prevent UB, or (b) detect what would be UB just before it happens and do something. A BigInt library is one way to mitigate (a), but it most certainly isn't applicable for all circumstances. I try to recall how I use type int. I do not think I ever use it for
anything that would be close to "numeric" as I know the term from math.
Use Case 1 (an index):
for (size_t i = 0, I = v.size(); i != I; ++i) { if (i != 0) str += ","; str += v[i]; }
There doesn't appear to be a good reason to wrap it into safe<int> here, even though the incrementation could possibly overflow.
Assuming v.size() returns a size_t, how can the increment possibly overflow? As I said, this stuff is incredibly difficult to reason about, and I'm not seeing the problem in the above code. #ifndef NDEBUG
typedef safe<int> int_t; #else typedef int int_t; #endif
I hope people don't do this. This isn't about finding programming bugs; rather, it's about something slightly different: detecting conditions where the normal assumptions about arithmetic do not hold. Then again, people call vector::at() for the wrong reasons, so I'm not holding my breath...
But is this the intent?
But perhaps it is just my narrow perspective. Can you give me a real-life example where substituting safe<int> for int has merit and is not controversial? I do not mean the code, just a story.
Besides security, just about anything financial. Do you, for instance, want any calculations involving UB to be applied to your bank account? Especially when it is unlikely to be an actual issue until you have a lot of money on the line? It is, as you point out, a tradeoff between safety and performance. When you are able to make that tradeoff, such a library is a life saver. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
One good usage example I can think of is this. After a while of trying to chase a bug I comae up with a hypothesis that my int could be overflowing. I temporarily replace it with safe<int> and put a break point in function overflow() to trap it and support my hypothesis. I would probably use a configurable typedef then:
#ifndef NDEBUG typedef safe<int> int_t; #else typedef int int_t; #endif
But is this the intent?
But perhaps it is just my narrow perspective. Can you give me a real-life example where substituting safe<int> for int has merit and is not controversial? I do not mean the code, just a story.
This is all a very good question, which I don't have a good answer to, but I'll add some comments anyway ;) One thing I've been asked from time to time is to extend support for boost::math::factorial or boost::math::binomial_constant to integer types - and it always gets the same response: "are you serious?". With Boost.Multiprecision one of the first support requests was for integer exponentiation and I reluctantly added it (as well as it's modular version) because I know there are situations where it's really needed, even though is clearly dangerous as hell. Now on to safe numerics: perhaps many folks don't realise this, but boost::multiprecision::cpp_int has always supported a "safe mode" where all operations are checked for overflow etc. What's more you can use this to create checked 32-bit int's right now if you really want to (it's a sledge hammer #include solution to the problem though). And yes, I have found bugs in number-theoretic type coding problems by using those types (mostly this is the algorithms within the multiprecision lib including the modular-exponentiation mentioned above). However there is going to be a noticeable performance hit if you really do use this with 32-bit integers. But not for extended precision integers - in fact I doubt very much you will be able to detect whether checking is turned on or not for those types - because the check is a fundamental part of the addition/subtraction/multiplication code anyway - you simply check at the end of the operation whether there is an unused carry. It's utterly trivial compared to everything else going on. So... I think yes, if you are writing a number theoretic algorithm then routine testing with a checked integer type is downright essential. However, for multiprecision types it has to be implemented as part of the number type's own arithmetic algorithms, not as an external add on which would be so utterly expensive as to be useless (all those multi-precision divides would kill you). Which is to say the proposed library would be quite useless for multiprecision types. None of which really answers your question. I guess if your pacemaker or your aeroplane uses integer arithmetic for critical control systems, then I rather hope that some form of defensive programming is in use. Whether this is the correct method, or whether some form of hardware support would be more effective is another issue. And my "favourite" integer bug: why subtracting (or heaven forbid negating) unsigned integers of course! John.
The original comment is couched in terms of acceptance as a boost library. I'm really pushing for this as a boost library - though if someone wanted it as such I wouldn't object. Right now, my major usage for it is as sample library for the incubator. I think this comment and replies are constitute a very useful and interesting discussion. They touch on fundamental issues that would be useful to users should the decide to use or not use such a component. So I would like to see these preserved as a permanent part of the Safe Numerics web page in the library. Also, I want to run a test of the comment mechanism with a real discussion to see how it has to be adjusted to be useful in the real (boost) world. So could I ask you all to post your comments at http://rrsd.com/blincubator.com/bi_library/safe-numerics/ . This would be very helpful to me on a number of levels. This means that Andrzej should post a comment and the rest of you should reply to this comment. I realize that is is sort of pain, but, again, I would be very helpful to me to test the idea of building and maintaining a libraries comment history in an permanent convenient place. Robert Ramey -- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
I'm NOT really pushing for this as a boost library -- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
This is an issue that is especially important to me, as I have written a library that also has the goal of making integer arithmetic safe: the bounded::integer library: http://doublewise.net/c++/bounded/ . I presented this library at C++Now 2014 this year. It has a different philosophy from the checked integer type that you described. It instead has compile-time min and max bounds on each integer type, and the goal is to replace all uses of built-in integer types. The result of the arithmetic operators is a new type that is able to hold any result of the operation (so bounded::integer<1, 10> + bounded::integer<4, 7> == bounded::integer<5, 17>). On Tue, Nov 18, 2014 at 11:45 AM, Robert Ramey <ramey@rrsd.com> wrote:
I'm NOT really pushing for this as a boost library
-- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Tue, Nov 18, 2014 at 7:57 PM, David Stone <david@doublewise.net> wrote:
This is an issue that is especially important to me, as I have written a library that also has the goal of making integer arithmetic safe: the bounded::integer library: http://doublewise.net/c++/bounded/ . I presented this library at C++Now 2014 this year. It has a different philosophy from the checked integer type that you described. It instead has compile-time min and max bounds on each integer type, and the goal is to replace all uses of built-in integer types. The result of the arithmetic operators is a new type that is able to hold any result of the operation (so bounded::integer<1, 10> + bounded::integer<4, 7> == bounded::integer<5, 17>).
Your implementation appears to also disable implicit conversions if the destination type is smaller. I abhore the C++ implicit conversion of integers, and I started to write an implementation that did only this (obviously I did not know about either of these libraries). Does anyone else find a library that only does a compile-time implicit conversion check useful? I know gcc and clang both have warnings that would do just this, but I also like the idea of having it consistent across any compiler. Might add too much overhead in compilation time for such a small feature. Also, what if one (or both) of these libraries added named ("add", "subtract", etc.) NOEXCEPT functions that returned bool? Overflow could be checked and handled without a try catch block. Lee
David Stone wrote
I attended your presentation at Boost Con and I thought you did a really great job. I think I even told you so. <snip> It instead has compile-time min and max bounds on each integer type, and the goal is to replace all uses of built-in integer types. The result of the arithmetic operators is a new type that is able to hold any result of the operation (so bounded::integer<1, 10> + bounded::integer<4, 7> == bounded::integer<5, 17>).
I have a good answer to this, and if you post a comment at http://rrsd.com/blincubator.com/bi_library/safe-numerics I'll respond. I know I'm being a pain on insisting on this but my main interest right now is testing out the comment feature on the incubator to see it can be helpful for these types of discussions. Thanks to all who are willing to help me out on this. Robert Ramey PS - there's no reason why your bounded integer library couldn't be loaded to the incubator. The incubator encourages competition!!! RR -- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
2014-11-18 19:45 GMT+01:00 Robert Ramey <ramey@rrsd.com>:
I'm NOT really pushing for this as a boost library
I am not sure I got your message right. Are you saying SafeNumerics library is there in the Incubator only to test the Incubator? I am still in the process of reviewing it. Does it mean it will be done for nothing? Regards, Andrzej
2014-11-24 9:37 GMT+01:00 Andrzej Krzemienski <akrzemi1@gmail.com>:
2014-11-18 19:45 GMT+01:00 Robert Ramey <ramey@rrsd.com>:
I'm NOT really pushing for this as a boost library
I am not sure I got your message right. Are you saying SafeNumerics library is there in the Incubator only to test the Incubator?
I am still in the process of reviewing it. Does it mean it will be done for nothing?
ping...
Andrzej Krzemienski wrote
2014-11-18 19:45 GMT+01:00 Robert Ramey <
ramey@
>:> I'm NOT really pushing for this as a boost library>I am not sure I got your message right.Are you saying SafeNumerics library is there in the Incubator only to testthe Incubator?
Hmmm - I didn't think about this aspect of it. I don't remember now why I originally wrote it. But when I needed an example for the incubator I used it because it's non-trivial in the issues it raises - there has already been lots of discussions on this topic. but usually not in terms of a real implementation. non-trivial in it's implementation - but not impossibly hard either. small enough to serve as an example that everyone can understand something that might have a wide enough interest to raise these kinds of questions. As far as submitting it to boost I've got my hands full just maintaining the serialization library and flogging the incubator. safe numerics opens up a huge amount of new territory to conquer: floating point modular arithmetic alternative type promotion policies to automatically promote types of results of avoid overflows entirely using safe_range to strict types so that they can never overflow - requires implementation of range arithmetic at compile time implementation of safe(type) where type is any numeric type as defined by (limits) So submission to boost would lead to this turning into a huge project for me if I were to do it. I actually did spend some time exploring the above extensions but failed to produce what I wanted. I would hope that one or more of the following might happen Someone might take responsibility for the library and submit it to boost - (note someone already suggested it as a candidate for the standard library!). Someone might decide to sponsor the library (in a monetary sense) which would justify the spending of more time on it. (How many billions of $ might this have shaved off the F-35 fighter jet program which is currently 7 years behind schedule?). It might just sit there garnering reviews and accumulating users. That is, once it's in the incubator, does it really need to be the official boost distribution (or the standard one) at all? Any one can git-clone or downloaded into their boost directory structure and start using it in exactly the same way that they use boost now. That is, for this person it IS a boost library. Could this be the future of boost - modular deployment like the incubator has. The incubator isn't there yet - but its headed in that direction. Maybe boost get's out of the deployment and distribution business and concentrates it's efforts on certification of library quality. In any/all of the above, you're review will be really useful. In fact more useful than a normal boost library review. Normally boost reviews are "lost" in the developer's list after the review ends. Reviews in the incubator be seen by anyone who looks at the safe numerics library page and is considering the library now or in the future. Robert Ramey -- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
2014-11-18 19:31 GMT+01:00 Robert Ramey <ramey@rrsd.com>:
The original comment is couched in terms of acceptance as a boost library. I'm really pushing for this as a boost library - though if someone wanted it as such I wouldn't object. Right now, my major usage for it is as sample library for the incubator.
I think this comment and replies are constitute a very useful and interesting discussion. They touch on fundamental issues that would be useful to users should the decide to use or not use such a component. So I would like to see these preserved as a permanent part of the Safe Numerics web page in the library. Also, I want to run a test of the comment mechanism with a real discussion to see how it has to be adjusted to be useful in the real (boost) world. So could I ask you all to post your comments at http://rrsd.com/blincubator.com/bi_library/safe-numerics/ . This would be very helpful to me on a number of levels.
This means that Andrzej should post a comment and the rest of you should reply to this comment.
Done. One remark as to BLIncubator I have already is that I was really missing a preview button when formatting my comment. I never know in this WordPress whether safe<int> will be treated as a HTML tag, and other problems like this. Regards, &rzej
Andrzej Krzemienski wrote
One remark as to BLIncubator I have already is that I was really missing a preview button when formatting my comment. I never know in this WordPress whether safe <int> will be treated as a HTML tag, and other problems like this.
Good point - I'll look into this -- View this message in context: http://boost.2283326.n4.nabble.com/safe-numerics-questioning-the-basic-idea-... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (6)
-
Andrzej Krzemienski -
David Stone -
John Maddock -
Lee Clagett -
Nevin Liber -
Robert Ramey