Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

collection.Searching does not use binary search for Array since ArrayOps is not a IndexedSeq #9605

Closed
scabug opened this issue Dec 27, 2015 · 2 comments
Closed

collection.Searching does not use binary search for Array since ArrayOps is not a IndexedSeq #9605

scabug opened this issue Dec 27, 2015 · 2 comments
Assignees
@Ichoran
Labels
enhancement library performance
Milestone
2.12.0-M4

Comments

@scabug
Copy link

scabug commented Dec 27, 2015 •
edited by retronym

Description

someBigArray.search(element) is slow because ArrayOps is not a IndexedSeq (but a IndexedSeqOptimized), so that collection.Searching does not use binary search.

Reproducing Code

Running attached file [^slow.scala], searching on an Array with 1000000 elements is 10000x slower than searching on a WrappedArray.

searchArray: 3116.342782 ms
searchWrappedArray: 0.273139 ms

Cause

The object Searching is implemented as follows:

object Searching {
  class SearchImpl[A, Repr](val coll: SeqLike[A, Repr]) {
    final def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult =
      coll match {
        case _: IndexedSeq[A] => binarySearch(elem, 0, coll.length)(ord)
        case _ => linearSearch(coll.view, elem, 0)(ord)
      }
    ...
  }

  implicit def search[Repr, A](coll: Repr)
  (implicit fr: IsSeqLike[Repr]): SearchImpl[fr.A, Repr] = new SearchImpl(fr.conversion(coll))
}

In the implicit method search, Array is converted to ArrayOps by IsSeqLike:

import scala.collection.generic.IsSeqLike
implicitly[IsSeqLike[Array[Int]]].conversion(Array(1)).getClass
 // class scala.collection.mutable.ArrayOps$ofInt

ArrayOps is a IndexedSeqOptimized but not a IndexedSeq since methods like IndexedSeq#filter and others must returns a IndexedSeq; therefore, binary search is not used.

Resolution

Rewriting from case _: IndexedSeq[A] to case _: IndexedSeqLike[A, _] fixes this. Try attached file [^fast.scala].

searchArray: 0.170193 ms
searchWrappedArray: 0.267205 ms
@scabug
Copy link
Author

scabug commented Dec 27, 2015

Imported From: https://issues.scala-lang.org/browse/SI-9605?orig=1
Reporter: takuo
Affected Versions: 2.11.7, 2.12.0-M3
Attachments:

  • fast.scala (created on Dec 27, 2015 11:07:46 AM UTC, 4517 bytes)
  • slow.scala (created on Dec 27, 2015 10:50:22 AM UTC, 639 bytes)

@scabug
Copy link
Author

scabug commented Jan 12, 2016

@ruippeixotog said:
I have just submitted a PR with the fix: scala/scala#4902

@scabug scabug closed this as completed Feb 10, 2016
@scabug scabug added this to the 2.12.0-M4 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Ichoran Ichoran

Labels
enhancement library performance
Projects
None yet
Milestone
2.12.0-M4
Development

No branches or pull requests
2 participants
@Ichoran @scabug