Re: [boost] a safe integer library

Subject: Re: [boost] a safe integer library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2015-12-12 12:11:38

Hi Robert,

Robert Ramey wrote:
> creating types which carry their ranges around with them through 
> expressions.

I'm curious to know how well this works in practice, i.e. how much
of the time do you need run-time checking in real programs.  Here
are a few examples that have occurred to me:

1. Arguments to functions

void f(safe<int> i)
{
   int8_t j = i;  // Needs a run-time check unless we know i<128
}

f(3);  // Run-time check happens, even though value is known.

Even though the body of f is visible at the point of the call,
I don't think an approach based on types can avoid the run-time
check unless the function args are templates:

template <typename RANGE_TYPE>
void f(RANGE_TYPE i)
{
   int8_t j = i;
}

f(3);

Here you can presumably arrange things so that the type of i inside
f includes the range information and the run-time check can be
avoided.  But this does rely on the body of f being visible at the
point of the call.  The verbosity of the function declaration should
improve a bit with concepts, but it's not really a drop-in replacement.

Related to this is function return types:

safe<int> incr(safe<int> i)
{
   return i+1;
}

int8_t j = incr(42);  // Run-time check or not?

Maybe auto return types help a bit but what about

   return (i%2==0) ? i/2 : 3*i+1;

2. Merging constraints

Example:

void g(int j);

void f(safe<int> i)
{
   for (int a = 0; a < 1000000; ++a) {
     g(i+a);
   }
}

Does that generate a million run-time checks?  If my expectation
is that i will be "small", most likely I would be happy with just
one check at the start of f:

   assert(i < maxint - 1000000);

3. Implied constraints:

vector<S> v;
f(v);  // fills v
safe<size_t> bytes = v.size() * sizeof(S);

I know that the multiplication can't overflow, because if v.size()
was large enough that it would overflow then I would have run out
of memory already.

So as I say, I'm curious to hear whether you've applied your safe<int>
to any real applications and measured how many of the potential run-
time checks are avoidable.  My fear is that it could be fewer than
you hope, and that the checks remain inside loops rather than begin
hoisted outside them.

Another reservation about this is the question of what should
happen when an overflow is detected.  Exceptions are not great,
because you have to worry about what you'll do when you get one.
One ambitious idea is to find a way to fall back to arbitrary
precision arithmetic:

template <typename INT>
void f(INT i) {
   INT i2 = i*i;
   INT j = (i2 + 4096) << 2;
   g(j%7);
}

try {
   f<int>(n);
}
catch (overflow&) {
   f<arbitrary_precision_int>(n);
}

How much syntactic sugar can we hide that in?

I recently experimented with LLVM's thread safety checking (see
http://clang.llvm.org/docs/ThreadSafetyAnalysis.html ); it lets
you annotate variables to indicate that locks must be held when
they are accessed:

   mutex m;
   int i GUARDED_BY(m);

I've been impressed by that, and I wonder if attributes defining
expected ranges and static analysis might be a more practical
way to find potential overflows.

Regards, Phil.