Scala Streams Performance

Question

A canonical example of the usefulness of recursive algebraic data types and the lazy evaluation is a game algorithm, e.g. as shown in the famous WhyFP paper by John Hughes (Comp. J., Vol. 32, No. 2, 1989).

Implementing it with Scala, and using lazily evaluated Stream[Tree[A]] for each subtree of a game leads to trait Tree[A] with a definition:

sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]

Now a lazily evaluated, possibly infinite, game can be presented as:

gameTree(b: Board): Tree[Board] = 
  if (b.isAtEndPos) Leaf(b) 
  else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))

and you can implement a pruning, scoring and parallelization strategy to the the actual algorithm, that is for example minimax which does the job, and evaluates the parts of the tree which are necessary:

def maximize(tree: Tree[Board]): Int = tree match {
  case Leaf(board) => board.score
  case Branch(subgames) => 
     subgames.map((tree: Tree[Board]) => minimize(tree)).max
} ...
def minimize // symmetrically

However, the infinite stream introduces a significant performance penalty, and solving identical game tree using eager list (ts: List[Tree[A]]) is 25 times more efficient.

Is there any way to use Streams or lazy structures in Scala effectively in similar situations?

Edit: added some performance results, and actual code: In link is the lazy version.

Lazy version (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.

No conversions in the tree creation, i.e. mapping over sets in minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.

Converting to list in the gameTree creation Time for gametree creation: 4.438s and for finding the solution 5.601s.

"is 25 times more efficient" -- care to post a project with both variations and the benchmarking rig? — retronym
Can't reproduce on my machine. I get, for creation/solution: Streams: 0.024s/6.568s, Lists: 4.189s/5.382s. So Streams are faster for me (when you add up both times). — Philippe
I get very similar results as Philippe; Stream: 0.23s/6.12s vs List: 4.07s/5.16s. So it seems as if Streams actually perform better in this case. I'm also using scala 2.9.1, so the only differences I can think about are either a different JVM, different JVM settings, or some strange hardware-dependent issues. — nomad
I did not pinpoint the actual problem yet, but running the performance tests and the question was sloppy, since with a different cleanly installed environment, and reasonable gc opts set, I did not stumble into streams performance. I did have same kind of problem earlier about one year ago (in a different environment, and hw), with a simple implementation of folding a stream instead of a range, (although continuation passing was clearly the slowest). Thus I did not suspect, that env would be the root cause. Sorry about that. Thanks to all for your effort! — jrosti

Philippe Philippe · Accepted Answer · 2012-02-20T18:32:47

If you want to get a quick and rough idea of where the time goes, you can try to run:

JAVA_OPTS="-Xprof" scala TicTacToe

As stated in the comments, I for one cannot reproduce your experience.

Scala Streams Performance

1 Answers