Increment operator in Rust

help
42

Future unknown CPUs, or future compiler optimizations.

But actually, x86-64 processors already directly support shifting 32-bit numbers by 32 bits by using certain instructions. One way is to use 64-bit registers (which are already used for 32-bit numbers). Another is the SSE PSLLD instruction. So the choice made by Rust to make 1u32 << 32 be 1 rather than 0 for quirky hardware reasons already prevents using these more capable instructions on existing hardware in certain cases, making both performance and usability worse.

For negative modulo, certain compiler optimizations are also prevented by the choice on x86. For example a % 256 should be, and is, optimized as "take the lowest byte of a". Except it can't do that for signed a because it has to implement the quirk that was introduced in C, and copied by Rust, for negative numbers because of hardware. So again the choice already decreases both performance and usability in certain cases on already existing hardware.

43

So you want to make code slower today to push hardware designers in the direction of special Rust-compatible CPUs?

Well… that's for showing us the reasons to implement shift like they are done today. As we can see half-century of C and it's popularity (and if you count it's descendants it's quite obviously is crazy popular) were not enough to bring C-friendly CPUs. Why do you think Rust would fare better?

Just what we got after half-century of development with division? As in: nothing?

Sure, C can use them and Rust can't, but the question then becomes: is this optimisation worth all the countless hours of debugging that this brings?

I think Rust have picked the right balance given the existing constraints. psld is used when possible (the most important case in practice when constant value is used) and it's entirely not clear whether waiting another half-century for Rust-optimized CPU would have been better.

One may argue that Rust should have picked “what most CPU do” with division, too, but there it's entirely not clear whether this would have been good choice given popularity of C: yes, division is slower then it can be, but it's slow no matter what thus compatibility with C looks justified.

Would have been nice to have another option which maps directly on hardware division, though, I guess that's fair.

44

For the specific case of shifts, a shift of the type's bit width or greater has a mathematically correct answer: 0. There's no good mathematical explanation for the "wrapping shift" behavior; it's not the shift which wraps, it's the shift amount which wraps. This is even called out in the documentation for wrapping_shl as surprising, noting that you may be looking for the rotate operation instead.

It's almost certainly impossible to say whether shift-to-zero or wrapping-shift-amount causes more debugging effort. What certainly causes less debugging effort is the default behavior in debug mode of panicking when a shift amount overflow happens.

There's good reason to support always having overflow panic (unless e.g. the wrapping methods are used) even in release mode. If Rust were designed independent of looking at today's CPU's behavior, overflow checks would be on by default in release mode, and might not even have an option to turn it off. (And you should consider turning it on anyway — it costs less than you might expect.)

For %, it's a toss-up. Both mathematical modulo and remainder are useful operations in different applications. Tbh, probably just don't define it for signed types, so it's only available where the two are the same, and use named remainder/modulo functions for signed inputs.

45

This is actually reasonable, given that -3 / 10 returns 0 (so that (-x)/y == -(x/y) == x/(-y)), and the reasonable desire that (a / b) * b + (a % b) == a.

I agree it's awkward, but it's coherent in a way that the shifts aren't.

(Though as I've said before, I think that basically everything about negative integers are weird, and they should be generally avoided.)

I don't really care, actually. I'd rather it did the most numerically-reasonable option, and people who really want the masked shift can just write that -- after all, that's what Rust emits to LLVM for it today, so it would handle that just fine.

The shortest code in rust should be the least-weird one, not the fastest one. That's why we spell wrapping addition as wrapping_add, not as +.

46

I agree it's coherent in a way but I have never seen a practical use case requiring this behavior of division or modulo, I have seen (and written!) bugs caused by this, and have seen many use cases for doing modulo the other way. The most obvious and common scenarios for negative modulo is when you're moving both ways in some sort of circular buffer or when doing modular arithmetic. In neither of these cases do you want the C behavior.

This paper agrees:

It is argued that the E- and F-definitions are superior to all other ones in regularity and useful mathematical properties and hence deserve serious consideration as the standard convention at the applications and language level.

However, it follows from the observations thus far, and from Table I, that the T-definition is far inferior to the other ones, and hence is not the one we wish to implement anyway.

The T-definition is the one used by C and Rust.

I have seen this distinction before, I guess it comes from IEEE-754 fmod and remainder operations. But AFAICT, "modulo" and "remainder" are normally synonyms in mathematics. And Wikipedia agrees and uses both terms interchangeably:

In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation).

There are three different possible definitions mentioned in the paper above. All three definitions are "remainders" of division in the sense that a = (a div b) * b + (a mod b).

47

At least Rust is careful to call it Rem in std::ops - Rust, not Mod :slightly_smiling_face:

48

As I said above, I think that's a strange distinction. Both "remainder" and "modulo" have inconsistent definitions between books and programming languages, so I don't think that really clarifies things much, they both mean the same thing really.

49

But at least you get the correct thing on wikipedia, for example.

In arithmetic, the remainder is the integer "left over" after dividing one integer by another to produce an integer quotient (integer division).

~ The second sentence on Remainder - Wikipedia

Which is what rust's % does: a % b = b - (a / b * b).

Calling it Mod would make it very easy to end up on Modular arithmetic - Wikipedia, which it's not.

50

This is true for all three definitions of div / mod / rem (they come in consistent pairs like that).

51

To remove the need for click-though, the three main integer division/remainder definitions are

  • “T” — truncating (towards 0) division
  • “F” — flooring (towards -∞) division
  • “E” — euclidean modulo

The paper also mentions in passing that you can also define

  • ceiling (towards +∞) division
  • rounding (closest, ties even) division

Whenever anyone specifies “math modulo” and differentiates that from remainder, they almost always mean euclidean modulo. This is the mod-dominant definition, coming from the convention of using the smallest nonnegative integer n for n (mod m) equivalence classes. The “remainder” operation is then perhaps left ambiguous, but that's because it's referring to using the div-dominant definition. It's “ambiguous” only because it's unspecified what integer division rule is being used; that's assumed to be implicitly understood from context.

To that point, I argue that the choice of integer division definition is what actually matters to programming language design/usability; the remainder operation simply follows. (A div-dominant definition is used.) Personally, because the standard way of writing integers is sign-and-magnitude, the truncating definition of integer division makes the most sense to me.

When considering the (q,r) pair, the flooring and/or euclidian definitions may be more desirable; I'm not arguing against that. Preferring truncating integer division may be in not insignificant part from conditioning... but familiarity of definition should not be undervalued, either.

All of that said, I agree with Scott that doing math to integers of unknown sign is uncommon in practice, and doing integer mul/div of unknown sign is uncommon within that. When it does happen, IME negatives are most often used for directionality of offsets; sign and magnitude, where truncating makes sense.

I can't help but feel like this post is missing something, but I can't quite identify what. A point, perhaps?

52

True, but it's easy to say that choice made by C causes the most debugging effort: if you ever shift 1i32 by 32 then compiler has the right to turn your program into a pile of goo.

But it's also the only one which makes it easily possible to both use pslld and regular x86 shifts in one program.

Rust could have adopted a mild version which just returns one of two values depending on what optimizer does, but this, too, would have been surprising to many.

Panic is probably the least-weird one, but it's also the most expensive one.

I can, probably, accept that argument, but I most definitely don't want C-style treatment.

53

Ah, I'd missed that you were suggesting that the division should be changed accordingly. I don't know if that's net less confusion -- I've never heard people confused by the current division behaviour, except in relation to the remainder.

Basically, every choice seems to have to break some expectation someone has. Maybe in whatever comes after Rust we'll be able to just not have / & % on integers, and use named methods that return pairs instead. (That'd probably have been too much Strangeness Budget for current rust, though.)

54

Python has a different (F) definition for // and %, it doesn't seem to cause too much trouble. Most people probably don't even think about it even when they happen to use it for negative numbers because "it just works" with the same regular pattern as you have for positive numbers.

It might seem like that in the abstract because of the sign-magnitude notation, but as soon as you try to use it for a number that can be negative, you typically run into trouble.

Example: Unix timestamps. Divide a Unix timestamp by 86400 and you have the day number. Seems natural. Except, with the T definition, this stops working for negative timestamps before 1970! It does work with the F and E definitions.

Very rarely that's what you actually want. Note that a Unix timestamp is an offset, so that's an example.

55

Not quite! While it is represented as an offset from 1970-01-01T00:00:00, a timestamp is logically treated as an absolute unit.

The value which trunc_div(signed_unix_timestamp, SECONDS_PER_24_HOURS) is giving you is the number of full 24 hour periods between 1970-01-01T00:00:00 and your unix timestamp. If you're actually working with offsets, then (I argue that) this is typically what you want: the offset in larger units that gets you almost to buy not past your initial offset.

floor_div asks a different question; phrased in terms of offsets, it's giving you the offset in 24 hour units such that the original timestamp is within the 24 hour period after the coarse offset. If you want to identify the bucket that the original offset falls into (e.g. in this case the day), then this is of course a useful query.

I'm not intending to say that floor_div (or euclid_div) isn't a useful semantic; I'm arguing that (at least in my experience) for signed integer quantities trunc_div is the correct semantic a plurality of the time (or at the least, a less poor choice than the paper argues).

There's actually another subtle detail there: a unix timestamp offset isn't even an integer offset quantity — it's a quantized real value offset. What's the quantizing rule for unix time? It's probably floor (i.e. at 12:34:56.99 the unix time is still 12:34:56), in which case the correct quantizing division is to use the same quantizing mode: floor_div. If using a differently quantized value (e.g. graphics APIs' SNORM, which is rounding quantization for minimized error) then you want to keep the same quantization method when doing integer division to requantize the value at a different scale.

So if anything, my argument ends up being we should have more types, differentiating between pure integer quantities/offsets (which I argue should use trunc_div) and integer-quantized quantities/offsets (which should maintain the same quantization method for integer division).

I have no intuition for what integer division of real numbers should do; in this I'll agree with the paper that euclidian division is probably the most useful default, followed by flooring and truncating being the worst, but with the caveats that: a) you can and probably should just name it unambiguously, and b) if ambiguous, it probably makes sense to match (a/b) as int's behavior — a motivating factor not brought up by the paper.

56

This one almost bit me in the rear end when I was writing a custom bit field implementation. Had to do this instead:

const fn shlz(value: u32, nbits: u32) -> u32 {
    let mask = (-1 + (nbits >= 32) as i32) as u32;
    value.wrapping_shl(nbits) & mask
}
57

Smart bit hacking, but interestingly, the compiler is smart enough to untangle it and compile it to the same exact assembly code as the more straightforward:

pub fn shl2(value: u32, nbits: u32) -> u32 {
    value.checked_shl(nbits).unwrap_or(0)
}

(playground)

58

I was aware of this and really wanted to use it, but unwrap_or is not const on stable. I was too stubborn to let const fn go and had to play dirty.

59

Until unwrap_or becomes const, you can do the same manually -- this works and also generates the same code:

pub const fn shl2(value: u32, nbits: u32) -> u32 {
    match value.checked_shl(nbits) {
        Some(x) => x,
        None => 0,
    }
}

I have also had to deal with full 32- or 64-bit shifts in two of my projects, so I think this is a real gotcha.