New integer types I’d like to see
foonathan.net
foonathan.net
The idea to separate bit vectors from numbers is a good one though, it always seemed a little weird to me that we're passing around numeric types for FLAG_FOO & FLAG_BAR.
Also "character strings" were a distinct type.
I also believe that these types must be clearly distinguished, even if conversion functions must be provided between them, and even if in certain contexts it may be convenient for the conversions to be implicit.
That’s because lots of hardware back then had support for bit addressing. The machine I love the best, the PDP-6/PDP-10 had addressable bytes of width ranging from 1-36 bits, which were extremely handy.
The few C compilers for those machines didn’t support them of course because the PDP-11s didn’t support them, but C on the PDP-10 was only used for porting stuff anyway.
Honestly I’m surprised they haven’t been revived. Packed bitfields are really handy and should be fast.
ARM has bit addressing with their bit-banding feature where individual bits are mapped onto byte addresses.
When you have a very large dataset tricks like this can significantly reduce RAM and especially cache pressure.
In low-level code, integer types are not numbers. They are fixed-length bit fields with a numerical interpretation. One thing I like in Rust over C/C++ is that it makes this clear. You always specify the size and signedness of the integer explicitly, and the standard library provides many useful operations beyond the operators.
Rust's Option<NonZeroU32> is guaranteed to be the exact same size as u32 (4 bytes) and the standard library could do the same thing with a BalancedI32 type if it wanted to.
And INT_MIN is a better place for it than zero imo. If Rust had a `BalancedI32` I would reach for it a lot more than I use the NonZero types. In my code at least, I've found zero is a pretty useful number.
That's clearly not impossible to solve, but if I'm correct it means significant compiler development work rather than just a fun weekend chore writing and testing a custom type intended to work only in the standard library.
Herb has made lots of proposals for changing C++ over the past half a decade or so, a few of them have shipped in newer C++ versions, most didn't go anywhere. At CppCon (a big C++ convention) Herb's keynote was about a transpiler which takes a different syntax, including most of Herb's features that didn't make it and some new features, and turns that into C++. This has been referred to as either "cppfront" or "cpp2".
You overestimate my knowledge of Rust :D I wasn't aware that NonZeroU32 is a thing, thanks for pointing it out.
It seems like a really obvious feature that's easy to support but isn't.
What do you see happening in that case?
> However, because compilers love exploiting undefined behavior for speedups
Except if the behavior had been well defined any attempt to catch overflow would violate the standard - see unsigned integers for reference.
> so it's actually fairly slow on modern processors.
Are you sure that having a potential branch every second operation, that depends directly on the result of the preceding operation, has at any point in time not been horribly slow?
Correct.
> Except if the behavior had been well defined any attempt to catch overflow would violate the standard - see unsigned integers for reference.
Then the compiler could emit them only on signed operations, but they don't.
> Are you sure that having a potential branch every second operation, that depends directly on the result of the preceding operation, has at any point in time not been horribly slow?
Yes; it's been shown that `INTO` is slower than `JO raiseOverflowError` because, by the nature of `INTO` being an interrupt, it doesn't get the advantage of branch prediction, but `JO` would.
On an older processor without a pipeline, sure, it'd be just as slow as an equivalent check, but with how massive the pipelines are on today's processors, it's bad.
A CPU could predict INTO — simply predicting it as not taken would be a good guess. This would require designing, implementing, verifying, and maintaining, and it might add some area to important parts of the CPU. The vendors haven’t seen it as a priority.
(AIUI at least older CPUs couldn’t predict branches in microcode, and INTO is presumably fully microcoded, so it doesn’t get predicted.)
The issue is that unsigned integers must not trap on overflow, and CPUs, if they could be configured to trap on arithmetic overflow, usually do not have separate opcodes for overflowing arithmetic operations and trapping arithmetic operations.
For example with gcc one should always use these compile options, unless there exists an extremely serious reason to do otherwise:
-fsanitize=address,undefined -fsanitize-undefined-trap-on-error
These options provide correct behavior not only on overflows, but also on out-of-bounds accesses and other C undefined operations.
That is what I have meant by "an extremely serious reason to do otherwise".
For many programs the speed is determined by things like the throughput or latency of accessing the main memory, or by I/O operations, or by interaction with an user, in which case the sanitize options have negligible influence on speed.
When necessary, they should be turned off only for specific well tested functions whose performance is limited by CPU computation in registers or in cache memory, and they should remain on for the rest of the program.
I understand the existing undefined behavior, that's not particularly interesting. What would be interesting is well-defined behavior for new types that does not interfere with however defined or undefined behavior exists for the existing types.
> usually do not have separate opcodes for overflowing arithmetic operations and trapping arithmetic operations.
I don't care how good or bad the codegen is. Just emit the code for the right behavior, because I'm using this type that requires this behavior.
You forgot to add 'in C', in Zig they have the same behaviour as signed integers.
# [16] c := a + b;
movq U_$P$TEST_$$_A(%rip),%rdx
movq U_$P$TEST_$$_B(%rip),%rax
addq %rdx,%rax
jno .Lj9
call FPC_OVERFLOW
.Lj9:
movq %rax,U_$P$TEST_$$_C(%rip)
How can you use memory addressing modes to do math, like 987*765?
Lol. See for yourself if you don't believe me.
https://godbolt.org/z/o14f7cdsc
> Why would a compiler use memory access to do math?
Because there are efficient instructions for it. Have you written an arithmetic code generation pass? It's normal to do it like this.
> Math operations are register based, none of the quantities are addresses.
An address is just a number. Yeah they're in registers or can be immediate. So what?
> How can you use memory addressing modes to do math, like 987*765?
Because AMD64 addressing modes have a base, a scale, and an offset component. That's multiplying and adding.
Let me know how you think you can work out if that lea overflowed!
You can use -ftrapv to check for integer overflows, like this
https://godbolt.org/z/snbdadv8b
>Let me know how you think you can work out if that lea overflowed!
LEA (Load Effective Address) can't overflow... memory is supposed to wrap, the byte after the last byte is byte 0.
> LEA (Load Effective Address) can't overflow...
You're mistaken - it's defined to overflow.
https://reverseengineering.stackexchange.com/questions/11442...
RISC-V architects weighted pros and cons of having a flags register, and pros and cons of having overflow exceptions.
They concluded it is best to not have flags at all (conditional branches do their own testing, and no flag dependencies need to be tracked which simplify superscalar implementations) nor overflow checks (flow breaking and costly; if you need the check, the cost of a software check is minimal, by design).
It also doesn't look like to me the cost of a software check can always be trivial. It can be for a single operation, but an advantage of an overflow register is that it allows to check for a group of operations as a whole (check/branch just once and abort), which is what is probably practical to do algorithmically. In such scenario switching to software checks for each op and/or bound check the inputs sounds by far not minimal.
On i8086 at least a non-taken conditional jump is 4 cycles while a unconditional jump is 15, for a total of 19 cycles, while a taken conditional jump is only 16. So it makes sense to almost always take the conditional jump.
[1]: https://wiki.freepascal.org/Free_Pascal_supported_targets
[2]: https://edge.edx.org/c4x/BITSPilani/EEE231/asset/8086_family... (page 2-45, or 60 in the PDF)
[3]: page 2-58 in[2] or 73 in the PDF
> I really don’t like this asymmetry – it leads to annoying edge cases in all sort of integer APIs.
And gets to here:
> Third, you’re getting an unused bit pattern 0b1'0000000, the old INT_MIN, which you can interpret however you like.
This isn't solving the original problem. If you don't like annoying edge cases in all sorts of integer APIs, it's worse.
edit: I can add: the article goes on to suggest that "old INT_MIN" should be called INT_NAN and "let’s just say arithmetic on INT_NAN is undefined behavior". So now what's the result of a + b? Undefined behavior! a * b? Undefined behavior! The general result of any function taking an integer or returning one is undefined behavior!
> I’d like to have . . . a 63 bit unsigned integer. . . . However, it is undefined behavior if it ever stores a negative value.
No. There is no "debug mode" for undefined behavior. Undefined behavior is always undefined behavior.
It also doesn't "automatically come[] with a precondition that it cannot be negative" - only that if it's ever negative, your program might crash for reasons that cannot be found in your code.
If you really want this, use uint64_t and treat any value over 0x7fffffffffffffff as an error.
Curious about the drive-by downvoters: Can you point out where you think I'm wrong?
https://blog.janestreet.com/what-is-gained-and-lost-with-63-...
This is not true; the standard explicitly allows implementations to, and I quote directly from the standard, "behave during translation or program execution in a documented manner characteristic of the environment".
This idea that undefined behavior is always undefined behavior and there's no way to reason about it is purely academic, incorrect, and not in any way justified either by source material or in practice.
As for debugging undefined behavior, UBSan [1] is an excellent tool that is well supported by GCC and clang, and MSVC is working to add support for it as well.
[1] https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
The point of adding more undefined behavior for this case, or any case in general, is to provide optimization opportunities that do not require introducing changes to the syntax (such as additional type checking or analysis). That way a C++ compiler is welcome to provide debugging support and various checks when a program is compiled in debug mode, and then eliminate those checks and make very strong assumptions about the program's runtime behavior when a program is compiled with optimizations enabled.
This is in contraposition to OPs claim that "There is no "debug mode" for undefined behavior.". There absolutely is a debug mode and it absolutely can catch undefined behavior, and UBSan is an excellent tool for doing precisely what OP claimed is not permissible in C++.
This. I always find bitwise operations an unneeded exercise in mental gymnastics.
On the other hand, I wonder if a lot of the other quirks about numbers could be handled via a library?
Great characterization! I’ve always been confused why most languages don’t have better tools for bit vectors. They’re incredible common and it’s really confusing to have to use the underlying representation of numbers to do anything with them.
1. No dynamic resize, have to know size at compile time or allocate based on max expectations. And yes, std::vector<bool> sucks too.
2. Despite being only statically sized, several classes of bugs are not prevented at compile-time. For example:
std::bitset<4> fail1{"10001"}; // This produces a value of 0b1000, no warnings or exceptions thrown
std::bitset<10> fail2; fail2.set(11); // Exception at runtime. Why is this not a static_assert?
3. Size is implementation defined. std::bitset<1> can use up to 8 bytes depending on compiler/platform.
4. Debug performance is 20x slower than Release. In many cases you are going from what would be a single assembly instruction to multiple function calls.
5. Limited options for accessing underlying storage efficiently (for serialization, etc). to_ullong() will work up to 64 bits, but beyond that it will throw exceptions.
6. Uses exceptions. This is still a deal breaker for many.
7. Cannot toggle a range of bits at once. It's either one or all.
(But actually a ton of other stdlibs do have one too.)
Right now though you will probably get such a type for free with a library of common maths features you'd likely want to use with it. So the only question is whether there are several different libraries and people would prefer to mix and match.
It's nice to require analysis for maximum performance rather than for correctness, since maximum performance usually doesn't matter but correctness usually does.
Personally I'm wary of it: it's not hard to think of adversarial scenarios where this could lead to OOM. On the other hand, adversarially overflowing an int can cause plenty of havoc too...
Something being O(N) can also be a security issue since it introduces a timing side channel.
I don’t think I’ve ever needed a bignum in my life or even a 64-bit integer (excluding pointers and file sizes). Of course I’ve used them inside black box crypto libraries but they have to be careful with them because of said security issues.
More recently, you can use Frama-C to constrain allowable sequences of 0's and 1's for C types and formally verify correctness.
In Ada since 1983 you can, e.g, declare your own 8 bit signed symmetric type without the wart -128 like so:
type Sym_8 is new Integer range -127 .. 127;
My_Signed_Byte : Sym_8 := -128;
In Frama-C, say you want a function that returns an absolute value. This function will fail to verify:
/*@ ensures (x >= 0 ==> \result == x) &&
(x < 0 ==> \result == -x);
assigns \nothing; */
int abs (int x) {
if (x >=0)
return x;
return -x;
}
#include <limits.h>
/*@ requires x > INT_MIN;
ensures (x >= 0 ==> \result == x) &&
(x < 0 ==> \result == -x);
assigns \nothing; */
int abs (int x) {
if (x >=0)
return x;
return -x;
}It has to have a check somewhere, no?
The ability to be precise with integer ranges could prevent many types of arithmetic and OOB errors.
base.u8[0 .. =99] is a single byte with values from 0 to 99 inclusive
base.u16[0 .. =99] is a 16-bit type with the same values
base.u16[100 .. =400] is still 16 bits but values from 100 to 400 inclusive
In WUFFS all arithmetic overflow or array bounds misses are compile time errors. From the point of view of WUFFS if pixels is an array with 200 elements, and idx is a base.u8[0.. = 240] then pixels[idx] is a type error as it wouldn't make sense to index 240 into an array of 200 elements so that doesn't compile.
As well as the obvious safety implication, this also means WUFFS can in principle go just as fast as if you were inhumanly careful with a conventional low level language and skipped any safety checks, since it knows it already took care of that. In practice it transpiles to C (which doesn't know what safety checks are).
“Safe” languages like Java try to achieve safety by making you write boilerplate casts here - “short = int + int” is illegal without a (short) cast even though that doesn’t change the meaning of the program.
If it was “x = i32<0,3> + i32<0,3>” then it highlights how silly this is and maybe they wouldn’t make you write a (i16<0,6>) cast.
https://github.com/hlslibs/ac_types
Arbitrary bit length, symmetrical and unsymmetrical, rounding and wraparound behaviour specifiable etc. etc.
Just set INT_MIN to -127 and never use -128.
> Second, you’re getting symmetry back. All the operations mentioned above are now symmetric and can’t overflow. This makes them a lot easier to reason about.
But you seem to want the actual bits to be symmetric with the sign bit just being a literal + or -. This makes it easier for humans to reason with, but it does NOT make it easier for a CPU's adder to add -15 and +63, which in the current standard signed int implementation does not even require the CPU adder to know that it's a signed int.
Unsigned and signed int adding work exactly the same bit-wise, and can use the same hardwired circuits to process at blazing speed. That's the beauty of the current standard implementation.
I think people say this because they rarely use bitwise operators, and so are scared of them.
LuaJIT uses a bit library, while Lua 5.3 and up have the native bitwise operators. I prefer the former.
From a general programming viewpoint pervasive bigints, ints with NaN/+Inf/-Inf and bitfields would be interesting too, but I don't know if the they are worth the complexity they introduce
but with the uint63_t i dont quite see the point but admit it would be neat having an unsigned int that cant overflow
I mean, if using that value is supposed to be UB anyway, then the current behavior if standard ints conforms to the spec. Doesn’t that make the proposal largely pointless?
The author needs to go back and study some history as to why we dropped that idea 40+ years ago.