Override some collections methods in Range to use optimised implementations #7062

hrhino · 2018-08-13T14:43:17Z

indexOf and lastIndexOf are calculable in constant time
sorted on a Range, if it uses the default Int ordering, is a no-op
sameElements can be calculated by comparing start/step/last, if the
other collection is also a Range

joshlemer · 2018-08-13T15:02:39Z

src/library/scala/collection/immutable/Range.scala

+    if (contains(i)) (i - start) / step else -1
+
+  override def sorted[B >: Int](implicit ord: Ordering[B]): IndexedSeq[Int] =
+    if (ord eq Ordering.Int) this else super.sorted(ord)


Is it worth also check if ord eq Ordering.Int.reverse to return this.reverse ?

Maybe so. Anyone else have an opinion?

The main reason I did this is that Ordering.Int is the vastly most common value that this method will be passed, and it's also the one for which the least work can be done. Passing Int.Reverse is probably far rarer.

Maybe Ordering.Int could also override val reverse: Ordering[Int] = ... so that it doesn't need to allocate a new instance each time

This is actually completely wrong for negative step size

javax-swing · 2018-08-13T17:06:07Z

src/library/scala/collection/immutable/Range.scala

+      case _ => super.indexOf(elem, from)
+    }
+
+  override final def lastIndexOf[@sp(Int) B >: Int](elem: B, end: Int = -1): Int =


the default for end should be length - 1

otherwise the result would always be -1 when not supplying an end index

as per SeqOps

https://github.com/scala/scala/blob/b78715242877fc623744f3d06d87e37d576945e9/src/library/scala/collection/Seq.scala

oops, good catch.

that

javax-swing · 2018-08-13T17:14:11Z

src/library/scala/collection/immutable/Range.scala

 package scala
 package collection.immutable

+import scala.{specialized => sp}


is it usual/necessary to rename the import here?

mkeskells · 2018-08-13T21:10:46Z

maybe also def distinct as a noop unless step is 0

there are a bunch of iterator abstract methods as well that could be implemented. Not sure how often they are called though

hrhino · 2018-08-13T23:27:43Z

@mkeskells distinct is already overridden as def distinct = this. I'll look for more methods that could be optimised. I don't think we really need to worry about the RangeIterator too much.

mkeskells · 2018-08-14T07:14:46Z

src/library/scala/collection/immutable/Range.scala

+          case 0 => other.isEmpty
+          case 1 => other.length == 1 && this.start == other.start
+          case n => other.length == n && (
+            (this.start == other.start)


what about reverse ordered Range?
Range.inclusive(1,10,1) == Range.inclusive(10,1,-1)

no, they're unequal; sameElements is confusingly named in that it means "same elements and in the same order"

mkeskells · 2018-08-14T07:26:26Z

@szeiger (and a little off topic) do we really need 2 implementation of Range (inclusive and exclusive)
all of the behaviour could be handled by the companion apply and inclusive methods, and the implementation of Range could be simplified by removing all of the isInclusive checks, and then Range becomes final. As a bonus the JIT can be more aggressive as it doesn't need the deopt hooks

I dont think that the implementation classes, or isInclusive are part of the user API, so should be private[scala] at least. I presume this idea (if accepted) would require a deprecation cycle

mkeskells · 2018-08-14T07:27:16Z

Some of these changes could be replicated/shared with NumericRange

hrhino · 2018-08-14T12:16:40Z

@mkeskells yes I'd like to share them; I just wanted review on the Int-specialized version first

hrhino · 2018-08-14T13:40:54Z

src/library/scala/collection/immutable/Range.scala

    }
  }

+  override final def indexOf[@sp(Int) B >: Int](elem: B, from: Int = 0): Int =


porting this to NumericRange is nontrivial, because B is unbounded above; here we know the element type is Int (and can special-case it accordingly) but NumericRange has no way of telling whether elem is a T or not, so the Integral arithmetic is unsafe.

hrhino · 2018-08-14T13:42:17Z

(rebased to maybe unwedge scabot)

hrhino · 2018-08-14T13:47:03Z

another method which may be profitably implemented here is copyToArray... IndexedSeq inherits IterableOnce's version, which goes (unsurprisingly) through an Iterator. Assuming fast apply should let us optimize it, but it turns out that the iterator version is faster for Vector (presumably because VectorIterator is smart) so an implementation in IndexedSeq would help only Range. (WrappedString needs an override as well but it should use getChars; I'll do that in a separate PR)

szeiger · 2018-10-10T10:38:27Z

@mkeskells Range.Inclusive and Range.Exclusive are part of the API. They are useful when you treat a range not just as a sequence. But the methods in Range shouldn't have to treat inclusive and exclusive ranges separately. Just make everything operate on an "inclusive end".

szeiger · 2018-10-10T10:57:48Z

src/library/scala/collection/Seq.scala

    * @param  offset  the index where the sequence is searched.
    * @return `true` if the sequence `that` is contained in this $coll at
    *         index `offset`, otherwise `false`.
+    * @throws NoSuchElementException if `offset` is greater than the size of this $coll


No, it should never throw an exception. See scala/bug#10931 and scala/bug#11199 for semantics in corner cases.

szeiger · 2018-10-10T12:02:41Z

src/library/scala/collection/immutable/Range.scala

+      if (this.isEmpty && other.isEmpty) true
+      else {
+        (this.length : @annotation.switch) match {
+          case 0 => other.isEmpty


You already know that other.isEmpty is false at this point

mkeskells · 2018-10-10T19:24:32Z

@szeiger I think that is what I was proposing - keeping the APIs but having one implementation

lrytz · 2018-11-02T13:20:14Z

Ping @hrhino

som-snytt · 2018-12-18T19:29:01Z

@hrhino temporarily taking over pinging duties. Curious if there were any other contenders for oldest mergeable PR.

szeiger · 2019-01-03T17:17:10Z

src/library/scala/collection/immutable/Range.scala

+        case n => other.length == n && (
+          (this.start == other.start)
+            && (this.step == other.step)
+            && (this.last == other.last)


Comparing both length and last appears to be redundant

szeiger · 2019-01-03T17:37:22Z

src/library/scala/collection/immutable/WrappedString.scala

      case _       => super.lastIndexOf(elem, end)
    }

-  override def indexOfSlice[B >: Char](that: collection.Seq[B], from: Int = 0): Int =


Nice catch. We should put import scala.Predef.{wrapString => _, _} into this file to avoid such accidents. ArrayOps does the same for the array conversions.

SethTisue · 2019-01-31T23:44:21Z

@hrhino interested in returning to this? time is running short for RC1

SethTisue · 2019-02-26T22:02:04Z

the remaining review feedback was minor. I added two commits in response

if CI likes it, let's squash, rebase, and merge.

…ations. - `indexOf` and `lastIndexOf` are calculable in constant time - `sameElements` can be calculated by comparing `start`/`step`/`last`, if the other collection is also a `Range` - `contains` can't override `Seq`'s `contains`, but we can add a forwarder that will

I don't know why I thought it was on jl.String.

SethTisue · 2019-02-28T05:20:00Z

squashed, rebased

hrhino · 2019-03-09T01:46:13Z

@SethTisue yes, this has gotten older than I would have thought! What more do you need from me?

SethTisue · 2019-03-09T01:49:01Z

nothing, we're good. thanks 👍

som-snytt · 2019-03-09T03:14:14Z

My previous comment hinting that there is a competition for the title of oldest active PR was not intended to elicit protestations of false modesty. hrhino's offer of further help is a transparent ploy to keep it open a few more weeks and extend its standing. More experienced contributors know that the most effective tactic is to set the milestone a few point releases down the road; in a previous era, one had only to request comment from soc to guarantee that a PR remain unmerged for months or even years.

Changes from: * scala/scala#7784 * scala/scala#7062

Changes from: * scala/scala#7784 * scala/scala#7062 * scala/scala#7670

scala-jenkins added this to the 2.13.0-RC1 milestone Aug 13, 2018

joshlemer reviewed Aug 13, 2018

View reviewed changes

javax-swing reviewed Aug 13, 2018

View reviewed changes

This comment has been minimized.

Sign in to view

hrhino force-pushed the faster/range-indexof branch from 31efee1 to c2d407e Compare August 13, 2018 23:25

This comment has been minimized.

Sign in to view

mkeskells reviewed Aug 14, 2018

View reviewed changes

hrhino commented Aug 14, 2018

View reviewed changes

hrhino force-pushed the faster/range-indexof branch from 59ec32e to a8e9cba Compare August 14, 2018 13:41

This comment has been minimized.

Sign in to view

szeiger reviewed Oct 10, 2018

View reviewed changes

lrytz assigned hrhino Nov 2, 2018

hrhino force-pushed the faster/range-indexof branch from a8e9cba to 6d52192 Compare November 6, 2018 13:59

SethTisue added the library:collections PRs involving changes to the standard collection library label Nov 8, 2018

hrhino force-pushed the faster/range-indexof branch from 6d52192 to a966258 Compare December 22, 2018 03:10

szeiger approved these changes Jan 3, 2019

View reviewed changes

sjrd mentioned this pull request Jan 30, 2019

Release 2.13.0-RC1 scala/scala-dev#599

Closed

51 tasks

SethTisue self-assigned this Feb 26, 2019

hrhino added 3 commits February 27, 2019 21:18

throw custom NSEE for empty ranges rather than Nil's

92eede3

Fix WrappedString#indexOfSlice by removing it, and add tests

ea470f7

I don't know why I thought it was on jl.String.

SethTisue force-pushed the faster/range-indexof branch from 0cf8c11 to ea470f7 Compare February 28, 2019 05:19

SethTisue merged commit 2c32023 into scala:2.13.x Mar 9, 2019

sjrd added a commit to sjrd/scala-js that referenced this pull request Mar 11, 2019

Update overrides for the latest 2.13 nightly.

e668732

Changes from: * scala/scala#7784 * scala/scala#7062

sjrd mentioned this pull request Mar 11, 2019

Update overrides for the latest 2.13 nightly. scala-js/scala-js#3581

Merged

sjrd added a commit to sjrd/scala-js that referenced this pull request Mar 11, 2019

Update overrides for the latest 2.13 nightly.

8e13590

Changes from: * scala/scala#7784 * scala/scala#7062 * scala/scala#7670

Override some collections methods in Range to use optimised implementations #7062

Override some collections methods in Range to use optimised implementations #7062

Uh oh!

Conversation

hrhino commented Aug 13, 2018

Uh oh!

joshlemer Aug 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hrhino Aug 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

This comment has been minimized.

mkeskells commented Aug 13, 2018

Uh oh!

hrhino commented Aug 13, 2018

Uh oh!

This comment has been minimized.

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mkeskells commented Aug 14, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mkeskells commented Aug 14, 2018

Uh oh!

hrhino commented Aug 14, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hrhino commented Aug 14, 2018

Uh oh!

hrhino commented Aug 14, 2018

Uh oh!

This comment has been minimized.

This comment has been minimized.

szeiger commented Oct 10, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mkeskells commented Oct 10, 2018

Uh oh!

lrytz commented Nov 2, 2018

Uh oh!

som-snytt commented Dec 18, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SethTisue commented Jan 31, 2019

Uh oh!

SethTisue commented Feb 26, 2019

Uh oh!

SethTisue commented Feb 28, 2019

Uh oh!

hrhino commented Mar 9, 2019

Uh oh!

SethTisue commented Mar 9, 2019

Uh oh!

som-snytt commented Mar 9, 2019

Uh oh!

Reviewers

Assignees

Labels

joshlemer Aug 13, 2018 •

edited

Loading

hrhino Aug 13, 2018 •

edited

Loading

mkeskells commented Aug 14, 2018 •

edited

Loading