Opt: Use unsigned arithmetics in Range, instead of Longs. #5176
Conversation
297f137 to
09bbab0
Compare
| (if (step >= 0) start > end else start < end) | ||
| else | ||
| (if (step >= 0) start >= end else start <= end) | ||
| ) |
There was a problem hiding this comment.
Move this diff to a separate commit? Seems (a-priori) unrelated to moving to unsigned arithmetic.
I understand that optimizing isEmpty becomes more important because of the changed definition of numRangeElements. So in that sense, it is clearly related.
I understand how it (likely) improves codesize: isInclusive is highly likely to be known constant, so the other branch can be eliminated.
| * standard unsigned int encoding of the mathematical value otherwise. | ||
| * | ||
| * This interpretation allows to represent all values with the correct | ||
| * modular arithmetics, which streamlines the use sites. |
| /** Creates a new range containing the first `n` elements of this range. | ||
| * | ||
| * $doesNotUseBuilders | ||
| * | ||
| * @param n the number of elements to take. | ||
| * @return a new range consisting of `n` first elements. | ||
| */ | ||
| final override def take(n: Int): Range = ( | ||
| final override def take(n: Int): Range = |
There was a problem hiding this comment.
nit (also below): use braces?
There was a problem hiding this comment.
I see the style here is to enclose a single if expr in braces, but braces signal that there are statements, so that is not my learned preference. ("Learned" as in "not innate", not as in "overeducated".) (Unbraced is easier with checked indentation or -Wnonunit-statement. Parens served that purpose of ensuring there is just an expression.)
Extract branches to be mostly dependent on `isInclusive` and `step >= 0`. These are often constant, and when they're not statically constant, they are probably predictable anyway.
Previously, `Range` used a number of intermediate operations on `Long`s to avoid overflow. The optimizer was already good enough to remove them in many cases, in particular when the step is `1` and/or the start is `0`, which are common cases. Now that the optimizer can reason about unsigned division, we can do a lot better. We can entirely avoid `Long` computations, *and* streamline a lot of code, by using unsigned `Int` arithmetics. This produces much better code for the cases where the optimizer cannot entirely get rid of the computations.
09bbab0 to
d972218
Compare
Previously,
Rangeused a number of intermediate operations onLongs to avoid overflow. The optimizer was already good enough to remove them in many cases, in particular when the step is1and/or the start is0, which are common cases.Now that the optimizer can reason about unsigned division, we can do a lot better. We can entirely avoid
Longcomputations, and streamline a lot of code, by using unsignedIntarithmetics. This produces much better code for the cases where the optimizer cannot entirely get rid of the computations.Diffs of the test suite in 2.12 and 2.13 can be seen here (I trimmed away all the local variable name changes):
https://gist.github.com/sjrd/e270bc3acaf86526b86767a4d107b409
My favorite diff is the following, happening for a range
by 2:Turned 3 Long division operations into a few int shifts. 👌