Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds
bitbucket.org
bitbucket.org
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.
To me the implementation seems to be a good solution given that you don't want to change the core language.
Fix the damn language.
Welcome to engineering tradeoffs.
Also, what do you mean by "this has to just trash performance for debug builds". Do you mean runtime performance?
In more explicit terms-- you are a soft-realtime app developer trying to live in a world that rarely measures performance or even writes specs with your constraints in mind.
I wish you game devs would harp on this more. I'm just a lowly soft-realtime audio software dev. My voice doesn't carry because there aren't mountains of cash behind me to help echo it.
I've worked on games with "DebugOptimized" builds where it's optimized,but instrumented in other ways. That's probably the best solution. You only drop down to full debug if you absolutely can't debug a specific issue in an optimized build.
With Visual C++, if you are careful you can build a version with release runtimes and third party libs so only your code is debug. Microsoft makes it harder than it has to be though.
But yeah, very often it’s basically the only option, running an optimized build with debug symbols. This is why it’s such a problem with C++: debug builds are frequently pointless because the performance is so bad, which makes debugging a lot harder.
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. And if -O0 is too slow, there's -Og which takes slightly longer to compile and has less information for gdb.
I work almost exclusively in "g++ -O0" until it's time to release.
Clang is decent too, but I find the C++ compile times are atrocious, like almost double for my admittedly template-heavy code. And performance of the compiled output is no better.
"Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to--they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law."
-- Tony Hoare, "The 1980 ACM Turing Award Lecture"
In fact, the README says as much: it has only zero time/space overhead "assuming basic compiler optimizations like inlining".
And I did actually look at the code, but at a glance I couldn't get much sense of it. The main header imports like two dozen other headers, and the "detail" folder is filled to the brim with more headers. I tried cloning and using it, but I couldn't get it to compile (which is probably mostly my fault, but I really didn't want to spend too much time on it). I did run just the preprocessor though, and "#include <bounded/integer.hpp>" expanded to 48000 lines. 48000 extra lines to compile in order to use integers. For every file you use it in.
I don't want to be too harsh here, I'm sure it's an excellent library and it does what it says brilliantly, and if you need bounded integers I'm sure it's awesome. But language like "[integers in C++] are mostly unusable" rankles a bit, and the the implication in this file is that this is something you should regularly use instead of integer types.
I personally feel that libraries like this are taking C++ in the wrong direction ("ranges" is another obvious example) and making the language less and less usable in my profession.
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.
Illustration, compare the assembly for "foo1" and "foo2": https://godbolt.org/z/t9Zkx-
That's a variation of "did you even read the article", which the HN guidelines specifically ask users not to post, so please edit those out of your posts. The comment would be just fine without that bit.
I found that it didn't really hurt compile times much (500KLOC compiles in about 40 seconds with make -j on a 16-core box), and performance is just barely impacted at -O2, but it definitely destroys debug build performance completely and makes a mess of code profiling and backtrace debugging output.
There are also all kinds of subtle gotchas: you can make "x ? y : z" work when y and z are different primitive types, but not if one is a template. You cannot make them work with printf("%d", x) directly (it compiles fine and then you run into problems), etc.
Trying to enforce stronger type checking (not allowing the implicit mixing of signed and unsigned, etc) introduces endless worlds of pain and ambiguous operator overload problems.
Trying to make eg "x++" or "x+y" return another template instance instead of a primitive type similarly causes a world of pain everywhere.
I still feel it was 100% worth it in my case, but it has many pitfalls. Taking it even further to bounding to specific ranges as this library aims to do feels even more fraught with danger. I do not envy the work of its authors.
To be fair that's also true for standard intN_t or uintN_t types. "%d" expects an int argument, and while several of the intN_t types may be converted to int by the default argument type promotion rules, that isn't guaranteed. For example, while plain "%d" works for int64_t on ILP64 platforms with 64-bit int values, LP64 (32-bit int, 64-bit long) requires "%ld" and 32-bit platforms require "%lld". That's why you have e.g. the PRId64 macro from <inttypes.h> to select the correct format code for printing int64_t values. You could provide something similar to abstract away the required format code. If you're using the GNU C library you can even define custom format codes with register_printf_function(), which might be your only option if the calling convention for your template doesn't match any of the standard integer types.
For run-time performance, yes, you definitely get a hit in your run time if you have all optimizations off. However, I have found that the practical benefits of things like this library, combined with run-time sanitizers, is worth much more at finding bugs than a debugger, so I typically debug and develop with `-O3 -fsanitize=undefined -fsanitize=address` and release mode is `-O3 -flto=thin -DNDEBUG`. This is an area where it's not possible (yet) to satisfy all use cases. I am hopeful that in the future, it will be much easier to tell your compiler "this is the code I care about debugging, optimize the rest".
Sizes of intermediates are a big issue. When you write
int_32 a,b,c,n;
...
n = (a*b)*c;
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;
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;
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.
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;
Sometimes you have to use larger sized intermediates. For
int_32 m,n,p;
...
n = (m * n) / p;
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;
}Performance improved by 100x - 1000x. And it was already blazingly fast before, if measured against performance standards we’ve become accustomed to from JavaScript and other GC languages.
In high performance systems (where the benefits of C/C++/etc. outweigh the downsides), dynamic allocations always come back to bite you.
If you rely on them too heavily from the start (and don’t plan for custom allocation schemes in the future), you can even get into bad situations where it’s infeasible to refactor to custom memory management (without a total rewrite), when you later need the performance gain.
Incorporating even the possibility of heap allocations into a language’s most fundamental data types will doom that language to being relegated to performance-insensitive and latency-insensitive tasks, if only because it requires that a heap exist (whereas C, Rust, etc can run on embedded real-time systems with no heap).
And that’s okay! It’s good that we have languages for that. But C/C++/Rust/etc. are definitely not where you can tolerate such a thing in the core language.
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.
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.
Anybody using a "message protocol" with ring buffers, or doing copies out of them, is Doing It Wrong. I routinely get 10x performance by doing away with FIFOs and buffer allocation and freeing.
Process separation means you can start and stop readers independently of any other activity.
Therefore, the implementation you’re suggesting is actually not all that different from my current solution, except for a few important details related to the particular problem I’m solving — e.g. handling many parallel streams which may momentarily drift out of sync (where those that are not delayed must still be processed without the state of other streams interfering to add latency), among other important details.
Ultimately though, aside from this discussion on high performance designs (which though fun, would not work without you actually knowing the requirements of what I’m working on — e.g. it’s not HFT), I’m just glad we’re in agreement that there are applications where avoiding dynamic allocations is absolutely essential, and that it would be a huge mistake to add them to a high-performance language’s most fundamental integer types.
Obviously a ring buffer is, literally, a first-in first-out medium. The essential difference between your typical FIFO and a ring buffer is the entire lack of interaction between writer and reader. More precisely, readers never have any effect on the writer. This allows any number of readers to be at random places along the sequence. The FIFO queues I find myself replacing tend to allocate a buffer, under a lock, and push it to a queue, under another lock (often these are hardware locks, what is often called "lock-free"), and readers pop a buffer under the same lock, use them for awhile, and then return them to a pool, under ther first lock. All this interaction generates overhead and cache pollution.
The only coupling in a ring buffer is readers checking the current state of the head pointer, done under relaxed semantics. The head pointer lives at all times in the writer's cache.
You probably understand all this, but remarkably many don't.
In other words, it's not just guaranteed bounds on the value that is required, but bounded (and consistent) execution time.
I should have taken the effort to write it better, sorry about misinformation.
When I was coming up as a game programmer no one would use boost shared_ptr and weak_ptr because of perceived issues with it. Everyone rolled their own handle system.
In fact there were a lot of people that considered languages beside C/C++ untouchable due to perf. They couldn't fathom there were domains where that perf just wasn't that important.
I now work a lot with Unity and find people feel the same about C# foreach because it used to trigger an allocation.
You'll find people often make the mistake of thinking their domain specific problem is a problem for everyone.
So when an overflow happens here I assume it's a compile time error (UB due to integer overflow in constexpr context must be diagnosed by the compiler). A handful of multiplications can get you there easily.
I am not sure why they chose to speculate about sizeof(int) in this way, vs. expressing the limit in terms of something more concrete.
I am saying the author did not express the limitation well, and instead made it sound like they don't understand sizeof(int). The explanation that leni536 offered makes a lot more sense, so maybe they should have put it that way instead of using an easily misunderstood term as "built-in integer" to mean "one of several integer types that we may choose based on some ifdef"
Why would you assume your observations are relevant to the use case?
> bounded::integer uses built-in integers as the template parameter to determine its bounds. This means that it cannot store an integer larger than ...
They say the limitation arises from using "built-in integers" as template parameters. It is reasonable to assume "built-in integer" means "int". It is more a stretch to assume "built-in integer" means any number of types depending on the evaluation of several ifdefs [which is what I found in the source].
There is nothing about a "use case" relevant to any of that quoted statement, so I find your reply very confusing too.
This strikes me as a little nuts for C but it definitely explains this thread. I just assumed people had already switched over to e.g. sint32/size_t to avoid this problem a long time ago. I couldn’t tell if this was a legitimate complaint or someone’s language lawyering tendencies gone too far.
Second, it is not "nuts" to use int, I would argue it's quite a bit more crazy to use rarely-supported 128-bit quantities when you don't need them. Your suggestion of "sint32" (this is not a standardized typedef, you mean int32_t perhaps) would be the same as int on most compilers today, and size_t is likewise very often 32 bits. Your suggestion is basically a no-op in a lot of places. Domain-specific areas like file formats or network protocols are a different story, as those have to be explicit about specifying sizes.
Third:
> someone’s language lawyering tendencies
I suggest you avoid passive-aggressive communication style and just say "you" instead of "someone". If you're going to criticize or give feedback, be direct. Don't vaguely tell me that "somebody" "might" have a problem.
Best regards to you, friend.
SSE2 has native 128-bit math, AVX has 256-bit native integer math, and AVX-512 has 512-bit integer math.
See https://en.wikipedia.org/wiki/AVX-512
The Intel compiler supports these types.
I'll make sure to update the documentation.
Weird. Ive been programming in C/C++ professionally for over a decade and have been using built-in integer types mostly without issue. Might want to qualify your hyperbole- is it worth reading on?
This must be some new definition of the word 'unusable.'
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.
Worse, the compiler is entitled to use saturation arithmetic if you've assumed wrapping.
C89 (draft[1], because the actual spec is not public) section 3.1.2.5 states:
> ... a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.
So, unless I'm misunderstanding, the compiler is not entitled to use saturation arithmetic on unsigned integers.
The compiler is allowed to do literally anything on signed overflow, including launching the missiles, and not running the program. Or both.
That might be a question for developers of the billons of lines of C++ in production. Asking them, you'd discover how they they actually use the builtin types.
typedef Int int32_t;
> throwing an exception on overflow or clamping the value to the minimum or maximum are also possible by use of template policies (and those particular use cases are already built in to the library)
> Never perform a run-time check when a static check would work instead
... but sometimes do run-time checks?
> Have no space or time overhead
This is a very confusing set of claims. You can't have all of these at the same time. Dynamic checks will be needed more often than you'd think, even in cases that "we" can tell won't overflow, so you'll definitely pay for stuff that you use even though with a stronger system you wouldn't need to use it.
For example, I'm wondering if this system can eliminate dynamic checks in cases like these:
int sum = 0;
for (int i = 0; i < 10; i++) {
sum += i;
}
There is definitely a case to be made for a system that tries to trap overflows but also tries to use static analysis to be smart about where to put the dynamic checks. But I don't think this system is that.
var
age: 18 ... 130;