Scala Programming Language
  1. Scala Programming Language
  2. SI-6150

Vector updated, +:, and :+ fall back to slow performance when builder comes from IndexedSeq

    Details

      Description

      When SI-5937 was fixed, that is in this https://github.com/scala/scala/commit/d8fbd9a54d commit, a new problem was introduced:

      scala> import collection.generic.CanBuildFrom
      import collection.generic.CanBuildFrom
      
      scala> import collection.immutable.{IndexedSeq => IIdxSeq}
      import collection.immutable.{IndexedSeq=>IIdxSeq}
      
      scala> val cbf1 = implicitly[CanBuildFrom[Vector[Int],Int,IIdxSeq[Int]]]
      cbf1: ... = scala.collection.immutable.Vector$VectorReusableCBF@106ac20f
      
      scala> val cbf2 = implicitly[CanBuildFrom[IIdxSeq[Int],Int,IIdxSeq[Int]]]
      cbf2: ... = scala.collection.generic.GenTraversableFactory$ReusableCBF@583dfc8b
      

      With cbf2, the check in Vector's methods updated, +:, and :+ for optimised O(1) algorithms fails.


      The suggested solution is as follows: the default implementation of collection.IndexedSeq is collection.immutable.IndexedSeq, and that in turn gives Vector. Vector can thus safely call the optimised methods when the builder target is ndexedSeq. The long-term solution probably is to introduce an IndexedSeqFactory. The direct fix is to move the newly introduced builder factory instance VectorReusableCBF from the Vector module to the IndexedSeq module.

      Indeed, I think it would be sufficient, instead of creating a new class, to ensure a fresh instance of ReusableCBF, e.g.

      object IndexedSeq extends SeqFactory[IndexedSeq] {
        override lazy val ReusableCBF: GenericCanBuildFrom[Nothing] = new ReusableCBF // ensure a fresh instance
        ...
      }
      

      Then, instead of checking the class using pattern matching, one could simply use eq:

        @inline override def :+[B >: A, That](elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = {
          if(bf eq IndexedSeq.ReusableCBF) {
            appendBack(elem).asInstanceOf[That] // just ignore bf
          } else {
            super.:+(elem)(bf)
          }
        }
      

      Of course, if you prefer a class type check, you may just move VectorReusableCBF to IndexedSeq and keep the pattern match as case _: IndexedSeq.VectorReusableCBF => ...


      Finally, it needs to be contemplated whether the new builder factory is safe in collection.IndexedSeq, or would have to be in collection.immutable.IndexedSeq so as not to interfere with collection.mutable.IndexedSeq? I think there is no problem – if you append an element to a Vector and expect a collection.IndexedSeq, it's correct to return another Vector.

        Issue Links

          Activity

          Hide
          Aleksandar Prokopec added a comment -

          I agree that using eq is a better idea.

          Also, given that the default implementation of the collection.IndexedSeq remains a Vector, optimizing : and : on the Vector while expecting an IndexedSeq should not cause a problem as far as I can see.

          Show
          Aleksandar Prokopec added a comment - I agree that using eq is a better idea. Also, given that the default implementation of the collection.IndexedSeq remains a Vector , optimizing : and : on the Vector while expecting an IndexedSeq should not cause a problem as far as I can see.
          Hide
          Aleksandar Prokopec added a comment -

          Although, ideally, we'd like to test if the factory produces a VectorBuilder, irrespective of where the factory came from. That, however, requires instantiating an empty VectorBuilder, which is probably prohibitive for smaller vectors.

          Show
          Aleksandar Prokopec added a comment - Although, ideally, we'd like to test if the factory produces a VectorBuilder , irrespective of where the factory came from. That, however, requires instantiating an empty VectorBuilder , which is probably prohibitive for smaller vectors.
          Show
          Aleksandar Prokopec added a comment - https://github.com/scala/scala/pull/1143
          Hide
          Sciss added a comment -

          That makes me very happy, thanks!

          Show
          Sciss added a comment - That makes me very happy, thanks!
          Hide
          Sciss added a comment -

          Should I be seeing these commits in 2.10.0-RC2? Because I still get the following horrific picture:

          Scala 2.10.0-R2:
          For Build+Compare the tests took 2:00.721s
          For Slice the tests took 2:22.187s

          Scala 2.9.2:
          For Build+Compare the tests took 0.481s
          For Slice the tests took 18.480s

          ?

          Show
          Sciss added a comment - Should I be seeing these commits in 2.10.0-RC2? Because I still get the following horrific picture: Scala 2.10.0-R2: For Build+Compare the tests took 2:00.721s For Slice the tests took 2:22.187s Scala 2.9.2: For Build+Compare the tests took 0.481s For Slice the tests took 18.480s ?
          Hide
          Jason Zaugg added a comment -

          Currently, it is only in the master branch, ie 2.11.0.

          git branch --contains 0308ae8 | egrep '(2.10|master)'
            master
          

          I agree that we should back port for 2.10.1 (it might be too late for 2.10.0).

          Show
          Jason Zaugg added a comment - Currently, it is only in the master branch, ie 2.11.0. git branch --contains 0308ae8 | egrep '(2.10|master)' master I agree that we should back port for 2.10.1 (it might be too late for 2.10.0).
          Hide
          Jason Zaugg added a comment -

          Reopening for a back-port to 2.10.1

          Show
          Jason Zaugg added a comment - Reopening for a back-port to 2.10.1
          Show
          Aleksandar Prokopec added a comment - https://github.com/scala/scala/pull/1628
          Hide
          Seth Tisue added a comment -

          That feeling when you find a bug, and find that not only is there already a ticket, there's already a fix. Thanks guys.

          Show
          Seth Tisue added a comment - That feeling when you find a bug, and find that not only is there already a ticket, there's already a fix. Thanks guys.

            People

            • Assignee:
              Aleksandar Prokopec
              Reporter:
              Sciss
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development