Choosing the Right Integers | Hacker News Reader

Choosing the Right Integers

thecodedmessage.com

74 pointsxmhidalgo33 comments

I feel like, ideally, one should never have to face the conundrum of choosing an integer width for general-purpose use.

I really like that the "normal" integers in Common Lisp are arbitrary length, but they're represented automatically as register-sized quantities when small enough (which, for typical code, is most of the time). That way, at least in terms of space efficiency, and for the most part in terms of time efficiency, you can have your cake and eat it too.

If I really need performance, I can always declare that a variable will never contain a non-machine-sized integer:

    (defun f (x)
      (declare (type (unsigned-byte 64) x))
      ...)

This is me promising to Lisp that x will always be bound to an unsigned 64-bit integer. If I dial the optimization settings with high speed and low safety (which I can scope to just that file, or even just that function):

    (declaim (optimize (speed 3) (safety 0)))

then Lisp will eliminate bounds checks, bignum-promotions, etc. and produce the native assembly you expect.

My point is that I really appreciate the "safe and general by default" philosophy, while still being able to opt-in to practical efficiency considerations when I absolutely need it.

(If I'm pedantic: The above optimization behavior, while encouraged in various ways by the Common Lisp standard, is technically not de jure required. But any general purpose Lisp compiler from the past 30 years will do these things, like SBCL.)

Here’s Rob Pike’s proposal to change Go’s int to be arbitrary precision in Go 2.0. But after five years of debate about “performance”, the proposal has stalled.

https://github.com/golang/go/issues/19623

I am generally in the camp of maximally explicit and consistent semantics for integer types. The old C-style types (short, int, etc) and related promotion rules was the source of numerous bugs in practice, particularly when porting code across architectures with different type models. While not convenient in C, in C++ there is almost unlimited ability to define new families of integer types that follow their own rules.

I don't follow the argument for using signed integers outside of contexts where a negative value is valid. In code bases that always use unsigned integers for values that cannot be negative (common in C++), the MAX value is treated as a sentinel. This extends the range of valid values versus signed types, which is sometimes useful, and there will never be undefined behavior (decrementing zero generates the sentinel, for example).

The infinite loop example often given for why to use signed integers doesn't happen in practice for "default unsigned" code bases because that is not idiomatic expression of that case -- and this case will come up even in code bases that are default signed. Writing loops like this is often a code smell.

How will there never be undefined behaviour?

I meant in the sense that unsigned integers have C-specified defined behaviors for conditions like overflow that are undefined for signed integers. That said, if you bothering to create these integers types (e.g. the common MAX sentinel idiom), their behavior is often fully defined. If you go crazy with metaprogramming, type inference, etc in recent C++, you can often verify at compile-time that these conditions will not occur across arithmetic operations, though this is a lot less trivial.

> I am generally in the camp of maximally explicit and consistent semantics for integer types

Size 3 minus size 4 being 4 billion is not correct type semantics though. If unsigned integers crashed the program for those operations or returned something akin to NaN it would be correct. Which means that signed integers are more correct for sizes, since when signed integers overflow you try to allocate a negative length array, and that doesn't work so it crashes, that is what you want. When you do the same thing with unsigned integers you now get a very small array, and when you try to write values to this array you now write them to arbitrary places in memory, causing memory corruption, that is much much worse than any issues you get with signed integers.

So the reason to use signed everywhere is that it reduces the mental overhead, and it is safer, you now only needs to learn a single integer math system and don't have to worry about all the issues that comes with casting unsigned and signed values to each other. Unsigned only makes sense if you explicitly want the overflow mathematics of unsigned, you don't want overflow math for array sizes though so they should be signed in any sane type system.

A negative size is generally not a valid type instance regardless. In well-behaved code I would expect this to be an unreachable condition because you are explicitly checking for sensible inputs before doing this type of arithmetic. It makes no sense to check for sensible inputs after you do the arithmetic, that is the same amount of code done in the wrong order. It is not safer to use signed in this case nor does it decrease mental overhead.

Assuming an integer is signed can be much less safe in practice because there is often no guarantee that an integer type is always signed or unsigned in a given context. Typedefs are a ubiquitous thing, and you don't always control those definitions. In code designed to be robust and maintainable, it is usually idiomatic to always implement these things in a way that is correct regardless of signed-ness unless that signed-ness is an immutable contract (e.g. some syscall stuff), because whether or not a type is signed can sometimes change unexpectedly.

> In well-behaved code I would expect this to be an unreachable condition because you are explicitly checking for sensible inputs before doing this type of arithmetic

You previously claimed "there will never be undefined behavior [by using unsigned types]", but now you also require that the UB scenario is checked beforehand? I'm confused how you conclude unsigned types to be safer than signed ones ("no UB") when you require UB be ruled out in the first place.

Unless you explicitly intend for wraparound to happen, your program has a bug on overflow regardless of signedness. You can (and possibly should) guard against the situation, but that favors neither side.

> Assuming an integer is signed can be much less safe in practice because there is often no guarantee that an integer type is always signed or unsigned in a given context. [...]

That is not an argument for or against using signed types. If types change from under you, you have a host of other issues anyway (as you say). Mixed sign comparisons, unexpected promotions, overflows... You get the exact same issues whether you yourself favor signed or unsigned types when mixing them with (what are, in your description) effectively unknown types. So again, your argument against signed types appears to be "you have to be careful either way", which gives zero reasons to favor unsigned over signed types.

Unsigned types have an absolute advantage for unsigned values: they have twice the range. This turns out to have useful performance advantages e.g. in large data infrastructure software. In typical C++ metaprogramming for this type of software, the integer types for processing code paths are often generated using the most compact primitive type because it is expected that billions of instances of these types may be in memory and trillions in storage, and there are multiple integer types where the required range of values for each are interdependent. A considerable amount of design in database engines, for example, goes into maximizing scalability while minimizing the total footprint of integer type instances. This is a function of the expressible non-negative range of the types, and cutting it in half will cause some of the types to be promoted, doubling their footprint. It is difficult enough to squeeze them into unsigned types without a step change in integer size as it is.

That overflows are well-defined, in contrast to UB, has value in cases of bugs because the consequences of the bug will be well-defined and less subject to clever compiler optimizations.

> [unsigned] extends the range of valid values versus signed types, which is sometimes useful

When is it useful?

On a 32 bit platform, for file offsets, maybe that last bit was useful for a few years. But as soon as disks got bigger than 4GB, you needed to switch to a 64 bit `off_t` and `lseek` anyways.

For array indexes, on a 32 bit platform, there is really only one VERY CONTRIVED case where that last bit for `unsigned` matters: your program creates a single array of bytes greater than 2GB. As soon as it's an array of 2-byte shorts or anything larger, you never need that last bit. And the configurations where a 32 bit kernel lets a program use more than 2GB of address space were not super common - it was better to switch to a 64 bit platform at that point.

On 64 bit platforms, you never need that last bit for array indexes or file offsets because no system has 10,000 petabytes of memory or 10,000 petabyte file sizes. And they won't for a while. Unless clock speeds get back on Moore's law, that for loop is going to take a long time to run anyways...

> Writing loops like this is often a code smell.

One person's code smell is another person's daily idiom. I think signed array indexes are like complex numbers - people who don't need them can't imagine why anyone else does. (https://github.com/golang/go/issues/19921)

For me, I frequently do math on the array index. Reverse loops are necessary sometimes (I can give examples), but let's ignore that for now. How would you write this simple loop with unsigned loop indices?

    double scale = <non-integer value>
    for (ssize_t ii = 0; ii<len; ii++) {
        data[ii] = sinc(scale*(ii - len/2));
    }

Note that `len/2` using integer division (truncating) is doing the right thing for both even and odd lengths. I really want that `sinc` function centered on a specific sample.

If either `ii` or `len` is unsigned, C/C++ quietly does something awful here. Stuff like this makes me resent the STL for choosing size_t over ssize_t.

I think it's ugly in Rust too:

    let len = data.len(); // usize because that's the way
    for ii in 0..len {
        data[ii] = sinc(scale*(ii as isize - len as isize / 2) as f64);
    }

Thankfully the `as` operator binds pretty tightly.

I don't think there are any good reasons to use unsigned integers for array indexes or sizes. It doesn't help with bound checking (it's the same assembly to check for unsigned out of bounds as it is to check for signed out of bounds or less than zero). It doesn't help with "large" arrays (except in one very contrived case). And it gets in the way when you need to do math on the indexes.

(In Rust) the ugliness for me stems from the fact we got this array from somewhere and now we're overwriting it, and I start to think probably the code should actually make the data structure instead, whereupon the need for these to be indices goes away and it's some sort of iterator into collect ?

I see your point, but I've got some practical objections to it:

a) You can't (sanely) initialize a fixed-sized rust array with an iterator. It looks like one of the following:

    let a = [1.0f64, 2.0, 3.0];  // not convenient for large arrays
    let a = [1.0f64; 1000]; // large array, but only the same value

I did find an insane example using an unsafe block. I've got no moral qualms about unsafe blocks, but using them to initialize an array seems heavy.

b) If you want it dynamically sized, you're probably going to use `Vec` and maybe an iterator as you suggested. I didn't try to compile the following, but I don't think it looks better than the for loop:

    let len = get_command_line_argument() as isize;
    let a: Vec<f64> = (0..len).map(|ii| sinc(scale*(ii - len/2) as f64)).collect();

You could break it down with more .maps, but I think it'd be even worse to look at. I think it's also growing iteratively (amortized constant, but still reallocating and copying along the way).

c) There are obvious cases where you want to re-use rather than reallocate your arrays. In addition to the cost of allocation and initializing to the wrong value, there are other times you might like to re-use the existing array address (FFI, etc..). You'd probably want to keep it in a Box<[T]> instead of a Vec<T>, but the point stands.

For (b), I suppose you could write a helper function:

    let a = make_vec(len, |ii| sinc(scale*(ii - len/2) as f64));

That's not awful. Both len and ii can be isize, and the implementation of make_vec can reserve the size in advance. Maybe I'll add something like that to my toolbox :-)

> I think it's also growing iteratively (amortized constant, but still reallocating and copying along the way).

Nah. Let's see why that isn't the case because it's instructive:

0..len is a Range, Range implements core::iter::TrustedLen which is an unsafe trait that says "I promise" (hence it must be unsafe) "that my size hint isn't a hint at all but my actual exact size".

[ Rust's "built-in" containers and iterator adaptors eagerly implement TrustedLen, you should consider doing likewise if you make things that you're absolutely certain know their correct size and wouldn't otherwise be TrustedLen ]

Because Range implements TrustedLen the Map also chooses to implement TrustedLen since it doesn't change the length and can just pass along what Range said.

The iterator.collect() call effectively ends up as spec_extend(iterator) on the Vec, and spec_extend() for an iterator with TrustedLen uses the size hint to reserve() the appropriate amount of space in the vector up front.

Feels like archaeology or a treasure hunt to track that down, but yeah it all looks very clever:

https://doc.rust-lang.org/src/core/iter/traits/iterator.rs.h... (collect)

https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#2549-255... (FromIterator for Vec)

https://doc.rust-lang.org/src/alloc/vec/spec_from_iter.rs.ht... (SpecFromIter for Vec)

https://doc.rust-lang.org/src/alloc/vec/spec_extend.rs.html#... (SpecExtend for Vec)

https://doc.rust-lang.org/src/core/iter/range.rs.html#854 (TrustedLen for Range)

https://doc.rust-lang.org/src/core/iter/range.rs.html#17 (TrustedStep for isize)

The `TrustedLen for Range` is marked unstable, and the issue tracker has comments from just 8 days ago. Does that mean this only works with nightly?

Back to the topic though,the iterator/collect solution looks uglier than the for loop to my eyes, and I still can't think of any (reasonable) case where unsigned array/slice/vec indexes are better. :-)

The compiler and standard library are allowed to use whatever unstable features they want. So really, things like TrustedLen can be seen as implementation details that nightly programs can tap into, provided they're not worried about building on all future versions of the compiler.

Interesting. Just to be clear though: if I'm up to date using rustup with stable, `Vec` and `collect` _are_ using this?

They've been using this for a long time. I actually have a checkout of Rust's git from summer 2021 when I was contemplating doing a bunch of doc changes (to use arrays instead of Vec in examples where that was now reasonable and maybe clearer) sitting around and used that to quickly verify what you summarised above when I answered.

So this was all true in like 1.53 or whatever that checkout is, and presumably long before. There are quite a few of these unstable Traits laying about in Rust's standard library that express important ideas that we can't live without, and yet are not something that's nailed down solidly enough to stabilize, the standard library is allowed to do this while claiming to be stable even though we are not - the rationale is that if they rip out one of these unstable traits, they can do the work to fix all the mess and deliver stability in the stable API anyway, whereas the same could not be true for some third party crate.

Another unstable but useful feature, check out Pattern: https://doc.rust-lang.org/std/str/pattern/trait.Pattern.html

Rust's string matching code uses Pattern everywhere so that even though Rust does not have ad hoc polymorphism (method overloading in C++):

  "clowns".contains("owns") // That's a literal string

yet also

  "clowns".contains('c') // That's not a string it's just one character

and

  "clowns".contains(char::is_lowercase) // A method on characters which here functions as a simple predicate

A sound API and yet also more convenient and more extensible.

Cool stuff.

I've also seen generic traits and tuples used to fake function overloading with different arity:

    trait Foo<T> { fn foo(&self, other: T); }                                                
                                                                                         
    impl Foo<()> for &str {                                                                  
        fn foo(&self, _other: ()) {         print!("0 params\n"); } }

    impl Foo<(f64,)> for &str {
        fn foo(&self, _other: (f64,)) {     print!("1 params\n"); } }

    impl Foo<(f64, f64)> for &str {
        fn foo(&self, _other: (f64, f64)) { print!("2 params\n"); } }

    fn main() {
        "".foo(());          // pretend that's 0 args
        "".foo((1.0,));      // pretend that's 1 args
        "".foo((1.0, 2.0));  // pretend that's 2 args
    }

Not quite as pretty, but it works, and you can be generic or specific over each sub-item in the tuple.

I appreciate the challenge. :)

I think you may be underestimating how large systems are today and the performance engineering considerations that drive design decisions toward e.g. 32-bit storage and memory addressing types on current servers with locally attached storage measured in petabytes. The metadata for managing data under these constraints starts to seriously pressure RAM.

Locally, this implies only 50-something bits but it also means the virtual memory silicon can no longer be used. Not a big deal, we know how to deal with this. At this scale, we aren't using conventional file systems either, they perform very poorly. Nonetheless, the dozen or so bits left over are often required for other critical addressing metadata that don't use that remaining value range efficiently. A single bit here or there may not seem like much but it forces tradeoffs that cascade through the architecture.

Locally, you want to be able to represent most addressing types as 32-bits, 64-bits at the outside, even though the global addressing is often necessarily 128-bits in large systems. The elided bits are inferred, not stored.

In large data infrastructure systems, we are right up against what 64-bits can naively support, but in implementation 32-bits is used everywhere for good reason. We can mostly fit within 64-bits globally, if we are clever, but that isn't going to last for too much longer. Machines generate incredible numbers of records per second in a way that humans do not.

FWIW, the largest single data models I am aware of are not byte-addressable with a 64-bit integer, signed or unsigned. Fortunately, that is not a problem I have had to solve, but it is a portent of the future. Nonetheless, if you look at the internals of current ultra-scale database kernels, just about everything addressing-wise is intentionally fitted into composites of uint32_t types for performance reasons.

> I think you may be underestimating how large systems are _today_

I don't think so, and I think you're moving the goal posts on me! :-)

I've got a good friend that works at a large search company, and he's happy to wow me with the scale of things, particularly in contrast to when we used to work together at a different company, processing piddly terabyte files. He's currently working on something that requires every last smidge of a 64 bit integer, so I get it.

However, we were talking about array indexes, for loops, and file offsets for a single file. These are 8 byte variables within a running program.

> FWIW, the largest single data models I am aware of are not byte-addressable with a 64-bit integer

I'm not sure what you're referring to here. I don't think you're saying you have a single machine with 18 Exabytes of storage in a block device or memory map. So if that's 64 bit keys on a distributed "database", I can see that. I can also see how using 128 bit UUIDs might be wasteful at scale, so you optimize bits.

But those aren't good reasons for Rust or the C++/STL to use unsigned integers for their collections. :-)

"However, we were talking about array indexes, for loops, and file offsets for a single file. These are 8 byte variables within a running program."

This depends on storage/page layout etc. See for ex. https://db.cs.pitt.edu/courses/cs3551/16-1/handouts/db2BLU.p...

> I appreciate the challenge. :)

Thank you for being friendly btw. So many conversations here go south, it's nice to just talk ideas without it being an unpleasant confrontation.

> How would you write this simple loop with unsigned loop indices?

  > double scale = <non-integer value>
  > for (ssize_t ii = 0; ii<len; ii++) {
  >     data[ii] = sinc(scale*(ii - len/2));
  > }

It took me a minute to realize that generating negative multiples of scale was (presumably) not a bug, but that would just be:

  double scale = <non-integer value>;
  for(size_t ii=0; ii<len ;ii++)
    { data[ii] = sinc(-scale*(len/2-ii)); }

(Assuming my guesses about the intended behaviour and the types of data/sinc/etc are correct.)

FWIW, idiomatic (so admittedly non-obvious) reverse loops look like:

  for(size_t ii=len; ii-- > 0 ;)
    { data[ii] = sinc(-scale*(len/2-ii)); }

The negative sign doesn't save you. `ii` takes every value in [0,len), so as soon as `ii` gets to `len/2 + 1` the unsigned subtraction became `2^64 - 1` (18446744073709551615), quietly converted/rounded to a pretty big double (18446744073709551616.0), and gave you the wrong answer without even a compiler warning.

You're proving my point :-)

> (Assuming my guesses about the intended behaviour and the types of data/sinc/etc are correct.)

I probably should've specified that, but I'm too verbose as is. I intended `data` as an array of doubles, and `sinc` is a function that returns a double. Change `sinc` to `sin` or `cos` if it helps to think about it.

> idiomatic (so admittedly non-obvious) reverse loops

Heh, I've only seen that as a joke where people call `-->` the "goes to operator". It's not an idiom I'm eager to embrace. I think some people like:

    for (size_t ii = len-1; ii != SIZE_MAX; ii--)

I'm not a fan of that one.

> [for odd len] as soon as `ii` gets to `len/2 + 1` the unsigned subtraction became `2^64 - 1`

That's actually a completely different problem, namely my tendency to mistake x/2 as rounding up rather than down. The original code generates sinc(+scale) on the last element of a odd-length array, rather than sinc(0). (So apparently my guess that the original had a bug was correct, it just wasn't the negative multiples. Admittedly, I should have caught that immediately from the fact that it aligns the zero point to the end of the array rather than the beginning.) Correct code would be:

  double scale = <non-integer value>;
  for(size_t ii=0; ii<len ;ii++)
    { data[ii] = sinc(-scale*((len+1)/2-ii)); }

This reinforces my belief that unsigned integers are preferable: they (occasionally) make off-by-one errors explode loudly rather than quietly producing subtle rounding and (visual/audio) alignment issues.

> Correct code would be: ...

Nah, it's still really broken :-)

Here, let's take all the confusing stuff out - no arrays, sinc functions, etc.. This compiles cleanly with -Wall and -Wextra

    #include <stdio.h>
    int main() {
        size_t len = 6;
        double scale = 0.1;
        for(size_t ii=0; ii<len ;ii++) {
            printf("%.2lf\n", -scale*((len+1)/2-ii));
        }
    }

Using size_t, it prints:

    -0.30
    -0.20
    -0.10
    -0.00
    -1844674407370955264.00
    -1844674407370955264.00

If you change it to use to `ssize_t`, you get the desired result:

> This reinforces my belief that unsigned integers [...]

I hope to show you that's wrong :-)

> they (occasionally) make off-by-one errors explode loudly

The problem isn't an off-by-one error, it's unsigned underflow.

Too many years ago, I wrote something in-house, now lost, titled "Type integer considered harmful". I was arguing for the idea that everything should have an explicit range, written

     foo: 0..100;

This was around the time Ada was being designed. The way I wanted this to work is that the size of intermediate variables was determined by the compiler, with the following rules:

- Unless a named typed variable result will overflow, no unnamed intermediate variable can overflow. The compiler must size intermediate temporary values accordingly.

- If this requires a larger intermediate variable than the machine can provide, a compile error is reported.

The implication is that you often need longer integers than you'd expect. Expressions such as

    x = a + b - c

    x = (a + b) / c

with signed values, all, say, 32-bit integers, can overflow in a+b without overflowing x. So such expressions have to be computed in 64 bits, then checked for overflow. This eliminates hidden overflow in intermediates. An expression with only one operator never overflows in a recoverable way, so it just has to be checked, not expanded.

That was written in an era when there were computers in use with word sizes of 8, 12, 16, 18, 24, 32, 36, 48, 60, and 64 bits. So word size was more of a practical issue than it is now, when non power of 2 machines have died off. Also, machines of that era tended to be slower on longer values. Much slower on some machines which had to do double-length arithmetic in software. Thus, there was a performance hit for this approach, which was the main objection.

WUFFS call that type refinement, although you are free to refine much larger types e.g. you can say base.u32[0 ..= 15] and this is a 32-bit unsigned integer... that can't be more than 15.

WUFFS not only refuses overflow (you get a compiler diagnostic) it also infers these refinements from array sizing so as to (at compile time) ensure bounds errors never occur. If you try to index into an array of 426 integers with k, WUFFS will go ahead and refine k to the 0..425 range.

Of course Ada (and presumably your proposal) are for general purpose software, whereas WUFFS is specifically targeted at software for well, Wrangling Untrusted File Formats Safely. So it's fine for some things to be completely impossible in WUFFS (e.g. you cannot write "Hello, World" in WUFFS, because WUFFS intentionally has no idea what a "string" is, or what "console output" is).

WUFFS calls them that because the formal name for the concept is a Refinement Type[1].

[1] https://en.wikipedia.org/wiki/Refinement_type

> An expression with only one operator never overflows in a recoverable way, so it just has to be checked, not expanded

(Nitpick: I think you intended to write either always or unrecoverable)

_If the target CPU doesn’t have status flags indicating overflow_, that may be more work than using a larger intermediate. For a+b, detecting overflow after the fact highly likely is faster, but already is a bit convoluted if a and b are signed and, thus, can be negative (https://stackoverflow.com/a/45261894)

For a×b https://stackoverflow.com/questions/1815367/catch-and-comput... has a simple algorithm, but it requires a division by b. I don’t see that perform well. Possibly, double size multiplication and then testing for overflow beats that (but, if the CPU has a ‘count leading zeroes’ instruction, I would use that (https://stackoverflow.com/a/59109502. I haven’t checked that for correctness, but even if it can’t be made correct, it likely can provide a fast path for most multiplications that your program does)

For CPUs with an overflow bit, the compiler can use it, but not all CPUs have that.

This should really have been called, "Choosing the right integer types in C/C++" rather than "Choosing the right integers".

Been thinking the same thing for just as long. "int" was supposed to be a full native word. Nowadays it's best to never use "int".

Google’s C++ coding style recommends using bare “int” by default or “int64_t” if the number might be “big”. It also recommends using signed integers over unsigned.

https://google.github.io/styleguide/cppguide.html#Integer_Ty...

Reply on news.ycombinator.com