8000 Opt: Use unsigned arithmetics in Range, instead of Longs. · scala-js/scala-js@d972218 · GitHub
[go: up one dir, main page]
Skip to content

Commit d972218

Browse files
sjrdsjrd
committed
Opt: Use unsigned arithmetics in Range, instead of Longs.
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.
1 parent a5337ed commit d972218

File tree

3 files changed

+295
-176
lines changed

3 files changed

+295
-176
lines changed

‎project/Build.scala

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2053,32 +2053,32 @@ object Build {
20532053
case `default212Version` =>
20542054
if (!useMinifySizes) {
20552055
Some(ExpectedSizes(
2056-
fastLink = 626000 to 627000,
2057-
fullLink = 96000 to 97000,
2056+
fastLink = 624000 to 625000,
2057+
fullLink = 94000 to 95000,
20582058
fastLinkGz = 75000 to 79000,
2059-
fullLinkGz = 25000 to 26000,
2059+
fullLinkGz = 24000 to 25000,
20602060
))
20612061
} else {
20622062
Some(ExpectedSizes(
2063-
fastLink = 425000 to 426000,
2064-
fullLink = 283000 to 284000,
2065-
fastLinkGz = 61000 to 62000,
2063+
fastLink = 424000 to 425000,
2064+
fullLink = 281000 to 282000,
2065+
fastLinkGz = 60000 to 61000,
20662066
fullLinkGz = 43000 to 44000,
20672067
))
20682068
}
20692069

20702070
case `default213Version` =>
20712071
if (!useMinifySizes) {
20722072
Some(ExpectedSizes(
2073-
fastLink = 443000 to 444000,
2074-
fullLink = 92000 to 93000,
2073+
fastLink = 442000 to 443000,
2074+
fullLink = 90000 to 91000,
20752075
fastLinkGz = 57000 to 58000,
2076-
fullLinkGz = 25000 to 26000,
2076+
fullLinkGz = 24000 to 25000,
20772077
))
20782078
} else {
20792079
Some(ExpectedSizes(
2080-
fastLink = 301000 to 302000,
2081-
fullLink = 258000 to 259000,
2080+
fastLink = 299000 to 300000,
2081+
fullLink = 257000 to 258000,
20822082
fastLinkGz = 47000 to 48000,
20832083
fullLinkGz = 42000 to 43000,
20842084
))

‎scalalib/overrides-2.12/scala/collection/immutable/Range.scala

Lines changed: 145 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -67,42 +67,92 @@ extends scala.collection.AbstractSeq[Int]
6767
{
6868
override def par = new ParRange(this)
6969

70-
private def gap = end.toLong - start.toLong
71-
private def isExact = gap % step == 0
72-
private def hasStub = isInclusive || !isExact
73-
private def longLength = gap / step + ( if (hasStub) 1 else 0 )
74-
75-
// Check cannot be evaluated eagerly because we have a pattern where
76-
// ranges are constructed like: "x to y by z" The "x to y" piece
77-
// should not trigger an exception. So the calculation is delayed,
78-
// which means it will not fail fast for those cases where failing was
79-
// correct.
8070
override final val isEmpty = (
8171
if (isInclusive)
8272
(if (step >= 0) start > end else start < end)
8373
else
8474
(if (step >= 0) start >= end else start <= end)
8575
)
8676

77+
if (step == 0) throw new IllegalArgumentException("step cannot be 0.")
78+
79+
/** Number of elements in this range, if it is non-empty.
80+
*
81+
* If the range is empty, `numRangeElements` does not have a meaningful value.
82+
*
83+
* Otherwise, `numRangeElements` is interpreted in the range [1, 2^32],
84+
* respecting modular arithmetics wrt. the unsigned interpretation.
85+
* In other words, it is 0 if the mathematical value should be 2^32, and the
86+
* standard unsigned int encoding of the mathematical value otherwise.
87+
*
88+
* This interpretation allows to represent all values with the correct
89+
* modular arithmetics, which streamlines the usage sites.
90+
*/
8791
private val numRangeElements: Int = {
88-
if (step == 0) throw new IllegalArgumentException("step cannot be 0.")
89-
else if (isEmpty) 0
90-
else {
91-
val len = longLength
92-
if (len > scala.Int.MaxValue) -1
93-
else len.toInt
94-
}
92+
val stepSign = step >> 31 // if (step >= 0) 0 else -1
93+
val gap = ((end - start) ^ stepSign) - stepSign // if (step >= 0) (end - start) else -(end - start)
94+
val absStep = (step ^ stepSign) - stepSign // if (step >= 0) step else -step
95+
96+
/* If `absStep` is a constant 1, `div` collapses to being an alias of
97+
* `gap`. Then `absStep * div` also collapses to `gap` and therefore
98+
* `absStep * div != gap` constant-folds to `false`.
99+
*
100+
* Since most ranges are exclusive, that makes `numRangeElements` an alias
101+
* of `gap`. Moreover, for exclusive ranges with step 1 and start 0 (which
102+
* are the common case), it makes it an alias of `end` and the entire
103+
* computation goes away.
104+
*/
105+
val div = Integer.divideUnsigned(gap, absStep)
106+
if (isInclusive || (absStep * div != gap)) div + 1 else div
95107
}
96108

97-
// This field has a sensible value only for non-empty ranges
98-
private val lastElement = step match {
99-
case 1 => if (isInclusive) end else end-1
100-
case -1 => if (isInclusive) end else end+1
101-
case _ =>
102-
val remainder = (gap % step).toInt
103-
if (remainder != 0) end - remainder
104-
else if (isInclusive) end
105-
else end - step
109+
/** Computes the element of this range after `n` steps from `start`.
110+
*
111+
* `n` is interpreted as an unsigned integer.
112+
*
113+
* If the mathematical result is not within this Range, the result won't
114+
* make sense, but won't error out.
115+
*/
116+
@inline
117+
private[this] def locationAfterN(n: Int): Int = {
118+
/* If `step >= 0`, we interpret `step * n` as an unsigned multiplication,
119+
* and the addition as a mixed `(signed, unsigned) -> signed` operation.
120+
* With those interpretation, they do not overflow, assuming the
121+
* mathematical result is within this Range.
122+
*
123+
* If `step < 0`, we should compute `start - (-step * n)`, with the
124+
* multiplication also interpreted as unsigned, and the subtraction as
125+
* mixed. Again, using those interpreatations, they do not overflow.
126+
* But then modular arithmetics allow us to cancel out the two `-` signs,
127+
* so we end up with the same formula.
128+
*/
129+
start + (step * n)
130+
}
131+
132+
/** Last element of this non-empty range.
133+
*
134+
* For empty ranges, this value is nonsensical.
135+
*/
136+
private[this] val lastElement: Int = {
137+
/* Since we can assume the range is non-empty, `(numRangeElements - 1)`
138+
* is a valid unsigned value in the full int range. The general formula is
139+
* therefore `locationAfterN(numRangeElements - 1)`.
140+
*
141+
* We special-case 1 and -1 so that, in the happy path where `step` is a
142+
* constant 1 or -1, and we only use `foreach`, we can entirely
143+
* dead-code-eliminate `numRangeElements` and its computation.
144+
*
145+
* When `step` is not constant, it is probably 1 or -1 anyway, so the
146+
* single branch should be predictably true.
147+
*
148+
* `step == 1 || step == -1`
149+
* equiv `(step + 1 == 2) || (step + 1 == 0)`
150+
* equiv `((step + 1) & ~2) == 0`
151+
*/
152+
if (((step + 1) & ~2) == 0)
153+
(if (isInclusive) end else end - step)
154+
else
155+
locationAfterN(numRangeElements - 1)
106156
}
107157

108158
/** The last element of this range. This method will return the correct value
@@ -135,18 +185,31 @@ extends scala.collection.AbstractSeq[Int]
135185
def isInclusive = false
136186

137187
override def size = length
138-
override def length = if (numRangeElements < 0) fail() else numRangeElements
139188

189+
override def length: Int =
190+
if (isEmpty) 0
191+
else if (numRangeElements > 0) numRangeElements
192+
else fail()
193+
194+
// Check cannot be evaluated eagerly because we have a pattern where
195+
// ranges are constructed like: "x to y by z" The "x to y" piece
196+
// should not trigger an exception. So the calculation is delayed,
197+
// which means it will not fail fast for those cases where failing was
198+
// correct.
140199
private def fail() = Range.fail(start, end, step, isInclusive)
141200
private def validateMaxLength() {
142-
if (numRangeElements < 0)
201+
if (numRangeElements <= 0 && !isEmpty)
143202
fail()
144203
}
145204

146205
final def apply(idx: Int): Int = {
147-
validateMaxLength()
148-
if (idx < 0 || idx >= numRangeElements) throw new IndexOutOfBoundsException(idx.toString)
149-
else start + (step * idx)
206+
/* If length is not valid, numRangeElements <= 0, so the condition is always true.
207+
* We push validateMaxLength() inside the then branch, out of the happy path.
208+
*/
209+
if (idx < 0 || idx >= numRangeElements || isEmpty) {
210+
validateMaxLength()
211+
throw new IndexOutOfBoundsException(idx.toString)
212+
} else locationAfterN(idx)
150213
}
151214

152215
@inline final override def foreach[@specialized(Unit) U](f: Int => U) {
@@ -162,22 +225,26 @@ extends scala.collection.AbstractSeq[Int]
162225
}
163226
}
164227

228+
/** Is the non-negative value `n` greater or equal to the number of elements
229+
* in this non-empty range?
230+
*
231+
* This method returns nonsensical results if `n < 0` or if `this.isEmpty`.
232+
*/
233+
@inline private[this] def greaterEqualNumRangeElements(n: Int): Boolean =
234+
(n ^ Int.MinValue) > ((numRangeElements - 1) ^ Int.MinValue) // unsigned comparison
235+
165236
/** Creates a new range containing the first `n` elements of this range.
166237
*
167238
* $doesNotUseBuilders
168239
*
169240
* @param n the number of elements to take.
170241
* @return a new range consisting of `n` first elements.
171242
*/
172-
final override def take(n: Int): Range = (
243+
final override def take(n: Int): Range = {
173244
if (n <= 0 || isEmpty) newEmptyRange(start)
174-
else if (n >= numRangeElements && numRangeElements >= 0) this
175-
else {
176-
// May have more than Int.MaxValue elements in range (numRangeElements < 0)
177-
// but the logic is the same either way: take the first n
178-
new Range.Inclusive(start, locationAfterN(n - 1), step)
179-
}
180-
)
245+
else if (greaterEqualNumRangeElements(n)) this
246+
else new Range.Inclusive(start, locationAfterN(n - 1), step)
247+
}
181248

182249
/** Creates a new range containing all the elements of this range except the first `n` elements.
183250
*
@@ -186,15 +253,11 @@ extends scala.collection.AbstractSeq[Int]
186253
* @param n the number of elements to drop.
187254
* @return a new range consisting of all the elements of this range except `n` first elements.
188255
*/
189-
final override def drop(n: Int): Range = (
256+
final override def drop(n: Int): Range = {
190257
if (n <= 0 || isEmpty) this
191-
else if (n >= numRangeElements && numRangeElements >= 0) newEmptyRange(end)
192-
else {
193-
// May have more than Int.MaxValue elements (numRangeElements < 0)
194-
// but the logic is the same either way: go forwards n steps, keep the rest
195-
copy(locationAfterN(n), end, step)
196-
}
197-
)
258+
else if (greaterEqualNumRangeElements(n)) newEmptyRange(end)
259+
else copy(locationAfterN(n), end, step)
260+
}
198261

199262
/** Creates a new range containing the elements starting at `from` up to but not including `until`.
200263
*
@@ -204,14 +267,16 @@ extends scala.collection.AbstractSeq[Int]
204267
* @param until the element at which to end (not included in the range)
205268
* @return a new range consisting of a contiguous interval of values in the old range
206269
*/
207-
override def slice(from: Int, until: Int): Range =
208-
if (from <= 0) take(until)
209-
else if (until >= numRangeElements && numRangeElements >= 0) drop(from)
270+
override def slice(from: Int, until: Int): Range = {
271+
if (isEmpty) this
272+
else if (from <= 0) take(until)
273+
else if (greaterEqualNumRangeElements(until) && until >= 0) drop(from)
210274
else {
211275
val fromValue = locationAfterN(from)
212276
if (from >= until) newEmptyRange(fromValue)
213277
else new Range.Inclusive(fromValue, locationAfterN(until-1), step)
214278
}
279+
}
215280

216281
/** Creates a new range containing all the elements of this range except the last one.
217282
*
@@ -250,9 +315,6 @@ extends scala.collection.AbstractSeq[Int]
250315
else current.toLong + step
251316
}
252317
}
253-
// Methods like apply throw exceptions on invalid n, but methods like take/drop
254-
// are forgiving: therefore the checks are with the methods.
255-
private def locationAfterN(n: Int) = start + (step * n)
256318

257319
// When one drops everything. Can't ever have unchecked operations
258320
// like "end + 1" or "end - 1" because ranges involving Int.{ MinValue, MaxValue }
@@ -300,30 +362,19 @@ extends scala.collection.AbstractSeq[Int]
300362
* $doesNotUseBuilders
301363
*/
302364
final override def takeRight(n: Int): Range = {
303-
if (n <= 0) newEmptyRange(start)
304-
else if (numRangeElements >= 0) drop(numRangeElements - n)
305-
else {
306-
// Need to handle over-full range separately
307-
val y = last
308-
val x = y - step.toLong*(n-1)
309-
if ((step > 0 && x < start) || (step < 0 && x > start)) this
310-
else new Range.Inclusive(x.toInt, y, step)
311-
}
365+
if (n <= 0 || isEmpty) newEmptyRange(start)
366+
else if (greaterEqualNumRangeElements(n)) this
367+
else copy(locationAfterN(numRangeElements - n), end, step)
312368
}
313369

314370
/** Creates a new range consisting of the initial `length - n` elements of the range.
315371
*
316372
* $doesNotUseBuilders
317373
*/
318374
final override def dropRight(n: Int): Range = {
319-
if (n <= 0) this
320-
else if (numRangeElements >= 0) take(numRangeElements - n)
321-
else {
322-
// Need to handle over-full range separately
323-
val y = last - step.toInt*n
324-
if ((step > 0 && y < start) || (step < 0 && y > start)) newEmptyRange(start)
325-
else new Range.Inclusive(start, y.toInt, step)
326-
}
375+
if (n <= 0 || isEmpty) this
376+
else if (greaterEqualNumRangeElements(n)) newEmptyRange(end)
377+
else new Range.Inclusive(start, locationAfterN(numRangeElements - 1 - n), step)
327378
}
328379

329380
/** Returns the reverse of this range.
@@ -341,14 +392,14 @@ extends scala.collection.AbstractSeq[Int]
341392
else new Range.Inclusive(start, end, step)
342393

343394
final def contains(x: Int) = {
344-
if (x==end && !isInclusive) false
395+
if (isEmpty) false
345396
else if (step > 0) {
346-
if (x < start || x > end) false
347-
else (step == 1) || (((x - start) % step) == 0)
397+
if (x < start || x > lastElement) false
398+
else (step == 1) || (Integer.remainderUnsigned(x - start, step) == 0)
348399
}
349400
else {
350-
if (x < end || x > start) false
351-
else (step == -1) || (((x - start) % step) == 0)
401+
if (x > start || x < lastElement) false
402+
else (step == -1) || (Integer.remainderUnsigned(start - x, -step) == 0)
352403
}
353404
}
354405

@@ -399,8 +450,13 @@ extends scala.collection.AbstractSeq[Int]
399450

400451
override def toString = {
401452
val preposition = if (isInclusive) "to" else "until"
453+
402454
val stepped = if (step == 1) "" else s" by $step"
403-
val prefix = if (isEmpty) "empty " else if (!isExact) "inexact " else ""
455+
def isInexact =
456+
if (isInclusive) lastElement != end
457+
else (lastElement + step) != end
458+
459+
val prefix = if (isEmpty) "empty " else if (isInexact) "inexact " else ""
404460
s"${prefix}Range $start $preposition $end$stepped"
405461
}
406462
}
@@ -433,16 +489,19 @@ object Range {
433489
)
434490
if (isEmpty) 0
435491
else {
436-
// Counts with Longs so we can recognize too-large ranges.
437-
val gap: Long = end.toLong - start.toLong
438-
val jumps: Long = gap / step
439-
// Whether the size of this range is one larger than the
440-
// number of full-sized jumps.
441-
val hasStub = isInclusive || (gap % step != 0)
442-
val result: Long = jumps + ( if (hasStub) 1 else 0 )
443-
444-
if (result > scala.Int.MaxValue) -1
445-
else result.toInt
492+
val stepSign = step >> 31 // if (step >= 0) 0 else -1
493+
val gap = ((end - start) ^ stepSign) - stepSign // if (step >= 0) (end - start) else -(end - start)
494+
val absStep = (step ^ stepSign) - stepSign // if (step >= 0) step else -step
495+
496+
val div = Integer.divideUnsigned(gap, absStep)
497+
if (isInclusive) {
498+
if (div == -1) // max unsigned int
499+
-1 // corner case: there are 2^32 elements, which would overflow to 0
500+
else
501+
div + 1
502+
} else {
503+
if (absStep * div != gap) div + 1 else div
504+
}
446505
}
447506 3DD8
}
448507
def count(start: Int, end: Int, step: Int): Int =

0 commit comments

Comments
 (0)
0