Live data from Hacker News

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

bitbucket.org

71–80 of 130 posts

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

#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-bit.

Sizes of intermediates are a big issue. When you write

    int_32 a,b,c,n;
    ...
    n = (a*b)*c;  
how big is each part? 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. So, 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.

is 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.

To do this right, you need something in the compiler that can do basic reasoning about machine arithmetic. Something that knows, for example, that

    uint_16 n;
    ...
    n = (n + 1) % 65536;
cannot really overflow and can be optimized down to a plain unsigned 16-bit add.

If you try to to this through linguistic type analysis only, it's not going to be satisfactory. You need to be able to prove out inequalities.

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

#72
post #53
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.

An unsigned type is sometimes a poor choice for a loop index. The compiler then cannot assume the loop will terminate, and generate worse code. Usually this doesn't matter -- until you discover it did.

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

#73

Earlier quoted context omitted.

It does. I personally stick to those exclusively except for for loop index variables.

It's a good choice. Sometimes your best choice for a general purpose int is typedef Int int32_t; for the entire compilation as a whole, and when things get screwy just bump Int up to int64_t and take the performance hit for the extra bit of safety

"i32" is better.

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

#74
post #67

Earlier quoted context omitted.

I just finished writing a custom FIFO allocator for an extremely high bandwidth and low latency data processing (and UI) system written in C/C++ (even std::deque was doing WAY too many heap allocations, not to mention the allocations within each object passing through the system, despite use of move semantics to minimize redundancy). Performance improved by 100x - 1000x . And it was already blazingly fast before, if…

If you are doing high-throughput, and you ever allocate anything after startup, you are Doing It Wrong. Any brand of FIFO loses. What you need is a big-ass ring buffer, mmapped on a hugetlbfs, fed by a process on a NOHZ isolcpu core. Readers are separate processes.

No. Thread local/core-specific FIFO is more cache efficient than a ring buffer because the address about to be allocated is significantly more likely to be in a high level cache.

With a ring buffer, you're constantly cycling out to L3 or worse and hoping the prefetcher figures out what you intend. It's basically a LIFO allocator.

Even if you want to use a separate processing core, you get better latency using a FIFO allocator between 2 threads on the same core complex and the code is simpler, reducing instruction fetch overhead.

Frankly, I see architectures like yours all the time from firms like Hudson River Trading and I think they suck. They incur tons of overhead, the process separation adds a useless layer of abstraction that's annoying to transcend, and you end up with this useless message protocol between cores that invokes tons of copies and breaks compiler inlining features.

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

#75
post #65

Earlier quoted context omitted.

I don't think you even looked at the library, but from I can tell, debug perf would not be impacted at all.

Of course it will be impacted. Libraries like these are "zero-cost" only because of very aggressive inlining (not generally available in debug builds), otherwise all its operations happen in subroutines. Operator overloading is the most obvious example: for regular integers, addition is basically a single instruction even in debug, but with a library like this, it has to make a subroutine call. A call which has who k…

> 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 another obvious example)

I think you're making an emotional argument based on some preconceived twitter-verse sentiment. I'm in games too (graphics specifically) and people are up and arms about the wrong thing. Maybe there are corner cases that are a bit overly complex, but what's wrong with being able to write `std::sort(container)` instead of `std::sort(container.begin, container.end)`. There may be things we don't like, but I don't think we should resort to hyperbole either.

Incidentally, I wouldn't use this library if only because for what I do, having explicitly sized data types is important.

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

#76
post #72
post #53

Earlier quoted context omitted.

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

An unsigned type is sometimes a poor choice for a loop index. The compiler then cannot assume the loop will terminate, and generate worse code. Usually this doesn't matter -- until you discover it did.

Good point. Probably not a problem in practice for most containers, but yet another reason for why the STL (and C library, for that matter) should have used a signed size type from the beginning.

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

#77
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.

[deleted]

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

#78
post #45

Earlier quoted context omitted.

Yes, that’s what I mean. And before you say ”debug performance doesn’t matter”: yes it does. I work in gamedev and it’s a huge problem that C++ has such awful debug performance, because it’s hard to debug a game if it’s running in single-digit framerates. It’s a large part of the reason why EASTL is so popular in gamedev.

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.

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

#79
post #65

Earlier quoted context omitted.

Of course it will be impacted. Libraries like these are "zero-cost" only because of very aggressive inlining (not generally available in debug builds), otherwise all its operations happen in subroutines. Operator overloading is the most obvious example: for regular integers, addition is basically a single instruction even in debug, but with a library like this, it has to make a subroutine call. A call which has who k…

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

Post reply on HN