Why does this array element reach an order of magnitude than the view \ slice array?

I am writing a simple application to check the balance of a parenthesized string as part of a parallel programming course. I have two implementations of a sequential piece of application - one that goes through Array[Char]

using the index and the other using the head \ tail methods.

I can't figure out why, for my test data (array of 100,000,000 length), index access is an order of magnitude faster than the head \ tail alternative.

Scalar reports (# of items in test collection: 100000)

• Sequential array :: average execution time: 0.10ms + no GC
• head \ tail + (chars.view (idx, before)): average execution time: ~ 949.07ms + average GC
• head \ tail + (chars.slice (idx, before)): average execution time: 603.42ms + average GC
• Head \ tail list (chars.slice (idx, before)): average execution time: 3.41ms + average GC
• Head \ tail list (chars.view (idx, before)): I completed the test in more than 45 seconds (!) + Many GC batches

I understand that the view method has to create a lazy view of the collection, and the slice method actually implements chunks of the collection - this explains the differences in the GC calls. However, I cannot figure out the differences in runtime.

• What is the reason for the runtime differences between the index approach and the head \ tail approach?
• Why does the head \ tail slice version perform better than the preview? I expected the result to be the other way around.

Full code of the method under test (for the version of the list of tests, the collection was converted to a list outside the measured time):

  def parBalance(chars: Array[Char], threshold: Int): Boolean = {

    def traverse(idx: Int, until: Int, initialUnmatchedLeft: Int, initialUnmatchedRight: Int): (Int, Int) = {

      def traverseChunkSeq(chars: Seq[Char], unmatchedLeft: Int, unmatchedRight: Int): (Int, Int) =
        if (chars.isEmpty) (unmatchedLeft, unmatchedRight)
        else chars.head match {
          case '(' => traverseChunkSeq(chars.tail, unmatchedLeft + 1, unmatchedRight)
          case ')' =>
            if (unmatchedLeft > 0) traverseChunkSeq(chars.tail, unmatchedLeft - 1, unmatchedRight)
            else traverseChunkSeq(chars.tail, unmatchedLeft, unmatchedRight + 1)
          case _ => traverseChunkSeq(chars.tail, unmatchedLeft, unmatchedRight)
        }

      def traverseChunk(i: Int, unmatchedLeft: Int, unmatchedRight: Int): (Int, Int) =
        if (i < until) (unmatchedLeft, unmatchedRight)
        else chars(i) match {
          case '(' => traverseChunk(i + 1, unmatchedLeft + 1, unmatchedRight)
          case ')' =>
            if (unmatchedLeft > 0) traverseChunk(i + 1, unmatchedLeft - 1, unmatchedRight)
            else traverseChunk(i + 1, unmatchedLeft, unmatchedRight + 1)
          case _ => traverseChunk(i + 1, unmatchedLeft, unmatchedRight)
        }


//      traverseChunk(idx, initialUnmatchedLeft, initialUnmatchedRight)
      traverseChunkSeq(chars.view(idx, until), initialUnmatchedLeft, initialUnmatchedRight)
//      traverseChunkSeq(chars.slice(idx, until), initialUnmatchedLeft, initialUnmatchedRight)
    }

    def reduce(from: Int, until: Int): (Int, Int) = {
      if (until - from <= threshold) traverse(from, until, 0, 0)
      else {
        val medium = (until + from) / 2
        val ((lo, lc), (ro, rc)) = parallel(reduce(from, medium), reduce(medium, until))
        (math.max(0, lo - rc) + ro, lc + math.max(0, rc - lo))
      }
    }

    reduce(0, chars.length) == (0, 0)
  }