Thoughts On Integers (2023)
19 points by abhin4v
19 points by abhin4v
Well written, but I continue to strongly disagree about using signed integers for values that should never be negative. This is a variant of violating the rule that illegal values should be unrepresentable. Every time we have to think about a non-negative value being out of range, it gets more complicated if using signed integers.
I like the principle of making illegal values unrepresentable. But getting that to play nice with arithmetic is hard. If you want to push hard in that direction, then the return type of subtracting two unsigned integers should be a signed integer, but I'm not aware of any language that does that.
Likewise, I generally will try to make illegal values unrepresentable, but when it comes to numbers that approach always seems to backfire. There are a few examples in the blog, and everyone who tries to force unsigned index types seems to end up regretting it. I don't know what the answer is, but I'm pretty sure that it's not unsigned numbers.
I haven't. I switched to using unsigned (technically, size_t) for index types in C in the mid-90s. It has not caused me grief, but then again, projects I start begin with that assumption. There has been plenty of code I've worked with from the 80-90s that played fast and loose with signed/unsigned arithmetic, but C compilers today can (with the proper warning level) mark such questionable code.
It's a user-defined type, not a language feature, but there was this Lobsters comment earlier this year:
I've been designing and using a type for quantities of and indices into memory that is a 63-bit unsigned integer, which can safely implicitly convert into either 64-bit signed or unsigned. The key insight is that then, subtraction from this value can be considered a cast to a signed value.
https://lobste.rs/s/bzltqt/unsigned_sizes_five_year_mistake#c_rdmyej
libCat for C++ does that by its idx type which is used for all its indices, iterators, and most loops.
I think that's safe and fine if you error or panic on overflow, or if you really don't do any arithmetic on the value.
Number types with custom ranges, or lots of contracts, seem like the better choices if you want to get the machine to check your work more thoroughly.
I'm being pedantic here, but unsigned integers are technically no better because they don't represent a number that can't be negative, rather they're more like offsets/memory addresses. From a type system perspective the true/proper solution would be something like Ada's integer range types.
Not having used Ada in anger, how would Ada handle two variables typed as 0..4 and multiplied together? Not allowed? Exception? Wrapping?
When we discussed this a couple of weeks ago, I wrote that a new language supporting range types should use flow-aware type inference so that the types of intermediate values within a fuction have types that cover the interval of their possible values, and comparisons should narrow range types in the obvious way. It should be a lot better than Ada or Pascal.
That's how Wuffs refinement types work.
https://github.com/google/wuffs/blob/main/doc/note/interval-arithmetic.md
I think there's a good path for groups of numbers, via metadata and doing type squeezing etc. If you have an array of 100 numbers, you can calculate their minimum, store that as the base, then represent every number as the offset of that (or even as deltas of eachother) (or have a min and max and use pos or neg offsets for directions from which of those...) and have your functions directly calculate off of e.g. this representation. You can also double the whole array by only changing the metadata number. Many other attributes of the group can be saved in meta data and many operations can be simplified through them. Since CPUs are so much faster than memory, making the CPU do 1-2 extra operations to e.g. add each offset to the base is faster (because the numbers can be represented smaller) this way.
It also gives a good pathway to defining an enum or type of e.g. only even numbers between 22 and 26.
Some unsorted comments:
Rust doesn’t have implicit integer casting, so you really do have to use usize for your array indexes
Yes, and I find it truly annoying that not even harmless extensions for indices are done implicitly.
To fix this we can change the condition to i <= top:
A canonical form for an unsigned loop from n-1 to 0 (inclusive) is
for (uint32_t i = n; i-- > 0;) {}
Performing a bounds check when using signed indexes requires checking both 0 <= i and i < count. These two checks are independent from one another, and so a contemporary CPU can run them in parallel.
Not generally true: if the two checks are lowered to two branches, they increase the potential for mispredictions and cause more pressure on the branch target buffer; if the checks are lowered to two compares (or ccmp where available, e.g. AArch64), they lengthen the dependency chain on the branch condition, which increases the cost of a branch miss (which is critical on out-of-order CPUs).
ISAs such as A64 only have 32- and 64-bit arithmetic instructions, so operating on 8- and 16-bit integers requires an extra and instruction.
Not generally true: most arithmetic operations don't require extra instructions (the upper bits can stay undefined) and AArch64 in particular permits encoding sign/zero-extensions in the second operand of some operations.
If an extra instruction is required, modern e.g. x86-64 CPUs tend to give a zero-extension (8/32->64 bit) for free while a sign extension requires one op/uop, lengthening dependency chains. Short dependency chains are quite important for address computations, typical pointer-heavy code can somewhat easily end up being memory-latency-bound even for L1 hits.
Aside: C/C++ char signedness is implementation-defined and is often signed, but unsigned on e.g. non-Darwin/Windows AArch64. This is for historical reasons: early ARM chips didn't have a sign-extending load, but C promotes all char/short to int by default, so loading a char from memory would require an expensive sign extension via ldrb+lsl+asr -- making char unsigned improved efficiency. Nowadays, it mainly uncovers code doing arithmetic on char when porting from x86-64 to AArch64.
Another aside: in C/C++, uint16_t a = 0xffff; uint16_t b = a * a; is undefined behavior for 32-bit int due to integer promotion and multiplication overflow.
Yet another aside: given that ISAs like x86-64 and AArch64 require the top N bits of canonical addresses to be identical, one can view pointers as signed; the check whether an address is user vs. kernel is a fast check for addr < 0. (This doesn't hold with extensions like top byte ignore (AArch64) or linear address masking (Intel 64).)
Yes, and I find it truly annoying that not even harmless extensions for indices are done implicitly.
It's very easy to implement the Index trait for your own collection types with whatever index type you desire. Handy if you are, say, writing a VM for an 8 or 16-bit system, like CHIP-8.
use std::ops::{Index, IndexMut};
struct MyArray<T, const N: usize>([T; N]);
impl<T, const N: usize> Index<u8> for MyArray<T, N> {
type Output = T;
fn index(&self, i: u8) -> &T {
&self.0[i as usize]
}
}
impl<T, const N: usize> IndexMut<u8> for MyArray<T, N> {
fn index_mut(&mut self, i: u8) -> &mut T {
&mut self.0[i as usize]
}
}
fn main() {
let arr = MyArray([4, 3, 2, 1]);
println!("{}", arr[1u8]);
}
When generic_const_exprs is stable you should even be able to constrain N to be u8.
In both this post and another post on this topic, they mention the kind of surprising way to correctly for loop downwards with wrapping unsigned ints (which also does the correct thing when len == 0):
for (unsigned i = len - 1; i < len; i--)
At first read this looks weird -- i is going downwards, why a less-than check? But after meditating a bit on this, I realized you can read the for loop is "i starts at len - 1 and it decrements, looping as long as i is within bounds".
That reading illustrates how i < len is correct whether i goes forwards, backwards, or steps by some other unit.
Perhaps we should have a CPU where all pointers are signed and the program counter starts at 0 and the stack at -1.
[Or maybe we should have an "almost unsigned" where there's a special representation for -1, which can be used for null pointers and decrementing loops.]
For Morello, we actually proposed making pointers signed. It has some nice properties with capability bounds because you don’t have to be able to represent the bounds of the entire possible VA space (which requires one more value than you want) and you can optimise the capability encoding for your VA space by not bothering to reserve space to represent sizes that don’t make sense. Most 64-bit systems don’t actually support a 64-bit VA space, they use page tables that can represent some smaller part of the space.
You still have the kernel and userspace in the same locations, except now you don’t have a big hole in the middle of the VA space, you have the kernel below 0 and userspace above (so your VA layout now looks like the pictures people draw with the kernel under userspace).
I’m all regards, it’s a nicer model. I remain sad we couldn’t persuade Arm to adopt it. We didn’t even try with RISC-V.
Interesting. Maybe I'll try it then if I design another toy CPU. Doubt I'll add virtual addressing though.
Without virtual addressing, you typically have an even smaller address space. Most 64-bit systems support a much smaller PA space than VA space, because PA space translates to wires, whereas VA space only impacts the latency of the page-table walk.
The issue in this case is that it would probably be 8-bit or 16-bit TTL @ a few MHz, so addressing is still slow when the address bus is wider than the data bus, and memory access is still fast. Still, 32-bit VA might be practical with a 16 or 24-bit PA. It just requires more chips. I know of at least one TTL computer that does something like that.
you don’t have to be able to represent the bounds of the entire possible VA space (which requires one more value than you want)
I'm not very familiar with Morello, but from what I'm guessing... is "requires one more value than you want" because you're using half-open [low, high) half-open intervals instead of [low, high] closed intervals?
Interesting post. Integer types can feel a bit "solved" compared to most aspects of pl design, so I appreciate the author taking the time to consider them more deeply. I also strongly prefer the more explicit type names of Rust, and feel similarly queasy to the author when reading some of the shared articles on unsigned vs signed for things like indices, and UB as a mechanism for optimization.
I might not have been able to hold back on C for thinking that long long is an acceptable type name :P. Lately I've been considering that although today the lowest-level most programmers go is C or a similar language (e.g. Zig, Odin), when C was developed it was relatively high level. As such "softer" and perhaps more humane type names probably shouldn't be a surprise. I haven't read any primary writings on the initial design of the language, but I expect K&R didn't want programmers to need to concern themselves with type width and such. After all, they'd be writing assembly if they needed such control!
Two more thoughts on constructs like for (uint32_t i = top; i >= 0; i--) {} being an infinite loop do to unsigned behavior: