Fix some issues in parallel Ctrie.

This change resolves some issues with ParCtrie splitters and their
`remaining` method, which currently evaluates the size of the Ctrie.
Since this is still not done lazily, nor in parallel, it has a certain cost,
which is unacceptable.

Change #1: The `shouldSplitFurther` method is by default implemented by
calling the `remaining` method. This method now forwards the call to the
same method in the splitter which is by default implemented in the same
way as before, but can be overridden by custom collections such as the
ParCtrie.

Change #2: ParCtrie splitter now has a `level` member which just counts
how many times the method has been split. This information is used to
override the default `shouldSplitFurther` implementation.

Change #3: The tasks and splitters rely heavily on the `remaining` method
in the splitter for most operations. There is an additional method called
`isRemainingCheap` which returns true by default, but can be overridden
by custom collections such as the `Ctrie`.

1 files changed, 14 insertions, 6 deletions

diff --git a/src/library/scala/collection/parallel/mutable/ParCtrie.scala b/src/library/scala/collection/parallel/mutable/ParCtrie.scala
index d8c060e719..86624500fd 100644
--- a/src/library/scala/collection/parallel/mutable/ParCtrie.scala
+++ b/src/library/scala/collection/parallel/mutable/ParCtrie.scala
@@ -27,7 +27,7 @@ import scala.collection.mutable.CtrieIterator
  *  @author Aleksandar Prokopec
  *  @since 2.10
  */
-final class ParCtrie[K, V] private[mutable] (private val ctrie: Ctrie[K, V])
+final class ParCtrie[K, V] private[collection] (private val ctrie: Ctrie[K, V])
 extends ParMap[K, V]
    with GenericParMapTemplate[K, V, ParCtrie]
    with ParMapLike[K, V, ParCtrie[K, V], Ctrie[K, V]]
@@ -45,7 +45,7 @@ extends ParMap[K, V]
   
   override def seq = ctrie
   
-  def splitter = new ParCtrieSplitter(ctrie.readOnlySnapshot().asInstanceOf[Ctrie[K, V]], true)
+  def splitter = new ParCtrieSplitter(0, ctrie.readOnlySnapshot().asInstanceOf[Ctrie[K, V]], true)
   
   override def size = ctrie.size
   
@@ -76,15 +76,21 @@ extends ParMap[K, V]
 }
 
 
-private[collection] class ParCtrieSplitter[K, V](ct: Ctrie[K, V], mustInit: Boolean)
-extends CtrieIterator[K, V](ct, mustInit)
+private[collection] class ParCtrieSplitter[K, V](lev: Int, ct: Ctrie[K, V], mustInit: Boolean)
+extends CtrieIterator[K, V](lev, ct, mustInit)
    with IterableSplitter[(K, V)]
 {
   // only evaluated if `remaining` is invoked (which is not used by most tasks)
-  lazy val totalsize = ct.iterator.size // TODO improve to lazily compute sizes
+  //lazy val totalsize = ct.iterator.size /* TODO improve to lazily compute sizes */
+  def totalsize: Int = throw new UnsupportedOperationException
   var iterated = 0
   
-  protected override def newIterator(_ct: Ctrie[K, V], _mustInit: Boolean) = new ParCtrieSplitter[K, V](_ct, _mustInit)
+  protected override def newIterator(_lev: Int, _ct: Ctrie[K, V], _mustInit: Boolean) = new ParCtrieSplitter[K, V](_lev, _ct, _mustInit)
+  
+  override def shouldSplitFurther[S](coll: collection.parallel.ParIterable[S], parallelismLevel: Int) = {
+    val maxsplits = 3 + Integer.highestOneBit(parallelismLevel)
+    level < maxsplits
+  }
   
   def dup = null // TODO necessary for views
   
@@ -95,6 +101,8 @@ extends CtrieIterator[K, V](ct, mustInit)
   
   def split: Seq[IterableSplitter[(K, V)]] = subdivide().asInstanceOf[Seq[IterableSplitter[(K, V)]]]
   
+  override def isRemainingCheap = false
+  
   def remaining: Int = totalsize - iterated
 }