[safe_numerics] questioning the basic idea

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

[safe_numerics] questioning the basic idea

Andrzej Krzemienski
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Nevin Liber
On 18 November 2014 03:15, Andrzej Krzemienski <[hidden email]> 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:[hidden email]>  (847) 691-1404

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

John Maddock-3
In reply to this post by Andrzej Krzemienski
> 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.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Robert Ramey
In reply to this post by Andrzej Krzemienski
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
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Robert Ramey
I'm NOT really pushing for this as a boost library
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

David Stone
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 <[hidden email]> 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-tp4669173p4669205.html
> Sent from the Boost - Dev mailing list archive at Nabble.com.
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Lee Clagett-2
On Tue, Nov 18, 2014 at 7:57 PM, David Stone <[hidden email]> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Andrzej Krzemienski
In reply to this post by Robert Ramey
2014-11-18 19:31 GMT+01:00 Robert Ramey <[hidden email]>:

> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Robert Ramey
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
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Robert Ramey
In reply to this post by David Stone
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
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Andrzej Krzemienski
In reply to this post by Robert Ramey
2014-11-18 19:45 GMT+01:00 Robert Ramey <[hidden email]>:

> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [safe_numerics] questioning the basic idea

Andrzej Krzemienski
2014-11-24 9:37 GMT+01:00 Andrzej Krzemienski <[hidden email]>:

>
>
>
> 2014-11-18 19:45 GMT+01:00 Robert Ramey <[hidden email]>:
>
>> 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...

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

[safe_numerics] [future of boost]questioning the basic idea

Robert Ramey
In reply to this post by Andrzej Krzemienski
Andrzej Krzemienski wrote
2014-11-18 19:45 GMT+01:00 Robert Ramey <[hidden email]>: > 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?
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