Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

bitbucket.org

Post reply on HN
Print view View original

81–90 of 130 posts

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#81

Post by banachtarski »

OskarS wrote: post #79
banachtarski wrote: post #75

Earlier quoted context omitted.

> but with a library like this, it has to make a subroutine call. I mean, before I wrote my comment I checked and it's `constexpr` all the way down to the add instruction so if it's going to make a call, I'm not seeing it. There is definitely a lot of template machinery, but I can't be the judge of that immediately. > I personally feel that libraries like this are taking C++ in the wrong direction ("ranges" is anothe…

constexpr functions are not inlined in debug builds. They can't be: the whole point of debug builds is that you can attach a debugger and step through the code. Illustration, compare the assembly for "foo1" and "foo2": https://godbolt.org/z/t9Zkx-

Ah ok, my mistake, I read "debug" as "-g" not "-O0." I generally run with optimizations on but with symbols.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#82

Post by CoolGuySteve »

makapuf wrote: post #78
CoolGuySteve wrote: post #68

Earlier quoted context omitted.

I feel like that's mostly Microsoft's fault, their STL implementation is super aggressive about checks in debug builds to the point that it becomes sort of useless in heavy use/high performance scenarios. Between that and the lack of valgrind, I'm pretty glad I left that world. Over in Linux/g++ land, it's not nearly so bad. Bounds errors are mostly handled by address sanitizer such that -O0 performance is decent. An…

Doesn't gcc have -Og that enables some optimizations but leaves the ones that prevent debugging.

It has issues sometimes evaluating inlined expressions, unfortunately.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#83

Post by q3k »

std_throwaway wrote: post #33
OskarS wrote: post #30

At this point, when I see libraries like this all I can think is ”oh good, my compile times aren’t long enough, lets make EVERY INTEGER a template”. Also, while I can reasonably beliveve that most of the overhead goes away at -O2 or -O3, this has to just trash performance for debug builds, which is not unimportant.

It does not change your existing integers or compilation time. Only where you use the new types the compiler will have more work to do. What would be the alternative in those places? Manual code? Preprocessor macros? Assertions everywhere? A theorem prover? To me the implementation seems to be a good solution given that you don't want to change the core language.

> What would be the alternative in those places?

Fix the damn language.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#84

Post by klyrs »

vzaliva wrote: post #41
codewiz wrote: post #27

Earlier quoted context omitted.

But that performs very poorly on all architectures.

it does not have to. A smart compiler can narrow it down to machine size integers then possible.

> A smart compiler can narrow it down to machine size integers then possible.

A smart compiler will be able to narrow it down in a limited set of scenarios, but all we need to do is put an accumulator into a loop to see that bounding an integer is equivalent to the halting problem. Or for another example, should we expect our "smart" compiler to bound y in the following? The bound on x is a freebie.

  bigint n(uint64_t x) {
    bigint i = 0;
    bigint y = x;
    while (y != 1) {
      i++;
      if (y%2) y = y//2;
      else y = 3*y-1; 
    }
    return i;
  }

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#85

Post by leni536 »

tom_ wrote: post #57
leni536 wrote: post #15

Earlier quoted context omitted.

You should never rely on the underlying CPU architecture's behavior on integer overflow when you write C or C++. It is undefined and not unspecified or implementation defined.

Undefined behaviour is undefined only by the standard - an implementation may choose to handle undefined behaviour in some documented, specific fashion. Undefined behaviour exists to give implementations exactly this flexibility.

> an implementation may choose to handle undefined behaviour in some documented, specific fashion

Or they can leave it undefined and not make any guarantees. I do not think that any compilers on any platform makes any guarantee on signed overflow.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#86

Post by cpeterso »

ken wrote: post #18
TazeTSchnitzel wrote: post #9

Maybe Ada's approach of every number type requiring explicit bounds is a good one.

Or Lisp’s approach of just using ”big” ints by default (which is practically the same but with an implicit default of “infinity”). And trust the compiler to use fixints internally when the programmer has declared it safe to do so.

Here's a Go2 proposal from Rob Pike to change Go's int to an arbitrary-precision BigInt:

https://github.com/golang/go/issues/19623

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#87

Post by tobinfricke »

ken wrote: post #18
TazeTSchnitzel wrote: post #9

Maybe Ada's approach of every number type requiring explicit bounds is a good one.

Or Lisp’s approach of just using ”big” ints by default (which is practically the same but with an implicit default of “infinity”). And trust the compiler to use fixints internally when the programmer has declared it safe to do so.

The performance hit when the system has to switch from regular integers to BigInts is likely to be unacceptable in the realtime / safety-critical applications where we really care about bounds guarantees. Consider an autopilot system where the execution time massively increases when some critical value exceeds some bounds, and the system can no longer execute in the time required. In floating point systems, this is often experienced when "denormalized" numbers are encountered.

In other words, it's not just guaranteed bounds on the value that is required, but bounded (and consistent) execution time.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#88

Post by nitwit005 »

rleigh wrote: post #53
vips7L wrote: post #42

Earlier quoted context omitted.

What would be different about loop variables? I don't really write C++.

I'm assuming here that they would use the `size_type` for the container they are iterating over. Otherwise I'm not sure.

Yep, it's to match vector/array size_type and difference_type, although I tend to just use size_t and ptrdiff_t directly.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#89

Post by pjmlp »

Gibbon1 wrote: post #56
TazeTSchnitzel wrote: post #9

Maybe Ada's approach of every number type requiring explicit bounds is a good one.

I think that's a good part of ADA that should have been copied 30 years ago. That and you should be able to define overflow semantics as well.

It was indeed copied, by Pascal, Turbo Pascal, Delphi, Modula-2, Modula-3, unfortunately not by the languages that won.

Re: Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds

#90

Post by Animats »

Animats wrote: post #71

Oh, that's nice. I wanted that decades ago, when I was working on program verification. Templates have made a lot of progress if this can be done entirely in C++ templates. I once wrote, but never published, "Type Integer Considered Harmful", back when there were still 16-bit integers in most C programs. I wanted ranges on everything, like Ada. As a practical matter, integer overflow became less of an issue with 32-b…

Botched the editing near the examples.

Sizes of intermediates are a big issue. My thinking on this was that it's the compiler's job to prevent overflow in intermediate values where the final result will not overflow.

When you write

    int_32 a,b,c,n;
    ...
    n = (a*b)*c;
that's legal to compute in 32-bit, but requires overflow checking on the intermediates. If an overflow occurs, there will be an overflow in the result. (Although, the case where some values are zero is an issue. Suppose a * b overflows but c is zero so it doesn't matter. That's probably an error.)

Sometimes you have to use larger sized intermediates. For

    int_32 m,n,p;
    ...
    n = (m * n) / p;
how big is each part? Above, you'd have to compute (m * n) as a 64-bit product, do a 64-bit divide, and only then check that the result fit in n.
Post reply on HN