12 ms·
Bounded Integer: Header-only C++ library replaces integers, adds explicit bounds
- golemotron 7y ago> The built-in integer types in C++ (int, unsigned, long long, etc.) are mostly unusable because of the lax requirements on bounds. This must be some new definition of the word 'unusable.'
- LinuXY 7y agoconst std::string unusable = "unsuitable";
- vbezhenar 7y agoI agree with that statement. How can you use type when you don't know range of values. I want to store year. From 1850 to 2050. What type should I choose? I want to store colour value: from 0 to 2^24-1. What type should I choose?
- ori_b 7y agoint, long. The standard specifies their minimum sizes.
- anilakar 7y agoX86 has also had saturation arithmetic since MMX was introduced.
- leni536 7y agoYou 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.
- leetcrew 7y agotrue, but the behavior of unsigned integers is defined such that they can't overflow. the "wrapping" behavior of unsigned ints is defined: you get the arithmetic result modulo the max value for that width.
- tom_ 7y agoUndefined 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.
- leni536 7y ago> 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.
- pjc50 7y ago.... However, unless you use non portable intrinsics, you can't make the compiler use MMX. So in practice you get wrap on overflow. Worse, the compiler is entitled to use saturation arithmetic if you've assumed wrapping.
- gpderetta 7y agoYou can build portable libraries on top of nonportable primitives.
- jstanley 7y ago> 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. [1] http://port70.net/~nsz/c/c89/c89-draft.html http://port70.net/~nsz/c/c89/c89-draft.html
- ncmncm 7y agosigned and unsigned have different semantics. The compiler is allowed to do literally anything on signed overflow, including launching the missiles, and not running the program. Or both.
- brandon_weekly 7y agoIt specifies the minimum sizes, in the sense that sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) etc... but no requirements on how big they actually are. You could (in theory) end up with all of those being 9 bits wide on some weird platform.
- tspiteri 7y agoNo, they cannot all be 9 bits, they have higher minimums. https://en.wikipedia.org/wiki/C_data_types#Basic_types https://en.wikipedia.org/wiki/C_data_types#Basic_types
- josefx 7y agoOr include cstdint and use the fast or least types as needed.
- andai 7y agoYou can store year 1850-2050 in a byte.
- billsnow 7y agoHow long does it take you to code a program if you are being bogged down by such simple problems? Use ints and do bounds checking when it's necessary to do so. Is every single bucket of information a reinvention of types?
- golemotron 7y ago> I agree with that statement. How can you use type when you don't know range of values. 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.
- icedchai 7y agoI've been programming in C and C++ for almost 30 years. This has never been a problem for me.
- ComputerGuru 7y agoOr “mostly” ;)
- panpanna 7y agoIf you work with formal verification this is a pretty common sight.
- carlmr 7y agoIf you work with smaller embedded systems and you need portability this is also a common sight (when you also quote the part about cstdint, which most embedded people will be happy with).
- HelloNurse 7y agoOn a different platform, these "friendly" types can be larger, typically 2 or 4 times larger which can be devastating for performance, or smaller, leading to overflow. They are only "usable" if you restrict yourself on one version, of one compiler, on one hardware platform.
- vips7L 7y agoDoes C++ not have int32_t and the like from C?
- nitwit005 7y agoIt does. I personally stick to those exclusively except for for loop index variables.
- glouwbug 7y agoIt'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
- ncmncm 7y ago"i32" is better.
- vips7L 7y agoWhat would be different about loop variables? I don't really write C++.
- rleigh 7y agoI'm assuming here that they would use the `size_type` for the container they are iterating over. Otherwise I'm not sure.
- leni536 7y ago> bounded::integer uses built-in integers as the template parameter to determine its bounds. This means that it cannot store an integer larger than an unsigned 64-bit or unsigned 128-bit integer (depending on the platform) or smaller than a signed 64-bit or signed 128-bit integer. This restriction should be removed at some point in the future. 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.
- asveikau 7y agoI am not aware of any compiler or platform where int is 128 bits. The most common these days, even on 64 bit platforms, is 32 bits, which they don't even mention. 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.
- leni536 7y agoThe author probably meant the largest available integral type, which can be __int128 on gcc and clang.
- deleted 7y ago[deleted]
- SomeOldThrow 7y agoHow are you envisioning this library being used?
- asveikau 7y agoWhat? 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"
- deleted 7y ago[deleted]
- TazeTSchnitzel 7y agoMaybe Ada's approach of every number type requiring explicit bounds is a good one.
- ken 7y agoOr 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.
- codewiz 7y agoBut that performs very poorly on all architectures.
- vzaliva 7y agoit does not have to. A smart compiler can narrow it down to machine size integers then possible.
- desertrider12 7y agoIn many situations yes, and C/C++ compilers miss a lot of opportunities for constant folding/propagation. But still, an infinitely smart compiler can’t prove anything about a value that comes from a file, user input or socket at runtime. If control flow depends on those (which is true of every useful real-life program) then you’re out of luck. GMP arbitrary-size integers are amazingly fast but still much slower than native instructions, can’t be vectorized, require heap allocation, etc.
- klyrs 7y ago> 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; }
- deleted 7y ago[deleted]
- OskarS 7y agoAt 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.
- std_throwaway 7y agoIt 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.
- q3k 7y ago> What would be the alternative in those places? Fix the damn language.
- netheril96 7y agoAs in, adding more features to C++? And then people cry about how complex C++ is.
- byuu 7y agoStop worrying about 9-bit bytes, only logical shift right for signed integers, ones-complement and sign-bit integers, etc and define this stuff in the standard. PDP-11 was a long time ago. C++20 is heading in the right direction with defining twos-complement. The next good step would be declaring signed overflow as wrapping (eg -fwrapv)
- smitty1e 7y agoAnd if the application's run-time safety requirements demand that the debug performance hit be paid, then that audience will view the debug sluggishness as a cost of doing business. Welcome to engineering tradeoffs.
- ur-whale 7y agoIt takes quite some amount of stamina to keep on reading after "The built-in integer types in C++ (int, unsigned, long long, etc.) are mostly unusable"
- DubiousPusher 7y agoI can see why you'd say that that way but the author probably feels that way because of the domain they work in. I've encountered research types who just use bigint everywhere because it's safer and they don't worry about the perf. 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.
- deleted 7y ago[deleted]
- FpUser 7y agoOuch
- DubiousPusher 7y agoBecause of the field I work in I feel this much more keenly with floats. I have been bitten by their excentricities so many times I'd just much rather have a flexible fixed point type that let me choose how much precision I want on either side of the decimal for a given set of calculations.
- michaelcampbell 7y agoDoesn't COBOL do this?
- Animats 7y agoOh, 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.
- Animats 7y agoBotched 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.
- duneroadrunner 7y agoAt first glance it seems to be similar to boost::safe_numerics. Are there significant differences? https://github.com/boostorg/safe_numerics https://github.com/boostorg/safe_numerics
- proverbialbunny 7y agoBoth libraries do the same thing. Boost lets you set your exception policy and I'm unsure if this Bounded Integer library gives the same level of control.
- davidstone 7y agoThe bounded::integer types accept three template parameters: `integer<min, max, overflow_policy>`. That final parameter can be bounded::throw_policy, which is itself templated on the exception type thrown. The default exception policy is "overflow is undefined behavior". The other two policies supported out of the box are wrapping / modulo and saturation / clamping.
- ssalazar 7y ago> The built-in integer types in C++ (int, unsigned, long long, etc.) are mostly unusable 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?
- anon91831837 7y agoReminds me of Pascal having dependent types like var age: 18 ... 130;
- mister_hn 7y agowhat about support for older gcc (say 6), older clang (say 5) and old MSVC (say 2015/17)?
- davidstone 7y agoOnly very old versions of the library are supported by those older compilers. My library is targeting the C++20 standard, so currently the only compile version that can compile it is clang with the concepts branch.
- tom_mellior 7y ago> you don't pay for what you don't use > 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; } After this loop sum's type should be integer<55, 55>, but I'd bet (without having tried) that with this actual system it's inferred to integer<0, infinity> and you'd get dynamic checks. Unless you use the "null policy", in which case you don't need this library at all. 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.