Scalaが遅かったけど原因が分かった件

Scala

Project Eulerの問題44

http://projecteuler.net/problem=44

これを解こうとして、以下のようなコードを書いた

https://gist.github.com/ponkotuy/5791300

のだが、Scala版が遅くて困っている件。どれぐらいかというと、HaswellのCPUで、Dは秒も掛かってないが、Scalaは10秒待っても終わる気配が無いので最後までやったことが無いレベル。

Profileを取る

遅いだけでなくProfileもナゾで、

   1 97.58% 97.58%    2419 300545 scala.collection.immutable.Range.foreach

なんかforeachで時間食ってるとか言われる。

TRACEを見てみると、

TRACE 300545:
	scala.collection.immutable.Range.foreach(Range.scala:141)
	scala.collection.TraversableLike$WithFilter.map(TraversableLike.scala:721)
	Prob44_2$$anonfun$3.apply(Prob44_2.scala:21)
	Prob44_2$$anonfun$3.apply(Prob44_2.scala:20)
	scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
	scala.collection.TraversableLike$$anonfun$flatMap$1.apply(TraversableLike.scala:251)
	scala.collection.immutable.Range.foreach(Range.scala:141)
	scala.collection.TraversableLike$class.flatMap(TraversableLike.scala:251)
	scala.collection.AbstractTraversable.flatMap(Traversable.scala:105)
	Prob44_2$.main(Prob44_2.scala:20)
	Prob44_2.main(Prob44_2.scala:Unknown line)
	sun.reflect.NativeMethodAccessorImpl.invoke0(NativeMethodAccessorImpl.java:Unknown line)
	sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	java.lang.reflect.Method.invoke(Method.java:601)
	scala.tools.nsc.util.ScalaClassLoader$$anonfun$run$1.apply(ScalaClassLoader.scala:71)
	scala.tools.nsc.util.ScalaClassLoader$class.asContext(ScalaClassLoader.scala:31)
	scala.tools.nsc.util.ScalaClassLoader$URLClassLoader.asContext(ScalaClassLoader.scala:139)
	scala.tools.nsc.util.ScalaClassLoader$class.run(ScalaClassLoader.scala:71)
	scala.tools.nsc.util.ScalaClassLoader$URLClassLoader.run(ScalaClassLoader.scala:139)
	scala.tools.nsc.CommonRunner$class.run(ObjectRunner.scala:28)
	scala.tools.nsc.ObjectRunner$.run(ObjectRunner.scala:45)
	scala.tools.nsc.CommonRunner$class.runAndCatch(ObjectRunner.scala:35)
	scala.tools.nsc.ObjectRunner$.runAndCatch(ObjectRunner.scala:45)
	scala.tools.nsc.MainGenericRunner.runTarget$1(MainGenericRunner.scala:74)
	scala.tools.nsc.MainGenericRunner.process(MainGenericRunner.scala:96)
	scala.tools.nsc.MainGenericRunner$.main(MainGenericRunner.scala:105)
	scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala:Unknown line)

foreachが遅いの？

と思って試してみたコード

import scala.compat.Platform

object RangeTime {
  def timer(f: Unit => Unit): Long = {
    val before = Platform.currentTime
    f()
    return Platform.currentTime - before
  }

  def main(args: Array[String]) {
    val result = timer { _ =>
      var long = 0L
      for {
        i <- 1 to 1000
        j <- (i + 1) to 1000
        if (i%2 != 0 && j%2 != 0)
      } {
        long += i + j
      }
      println(long)
    }
    println(result)
  }
}

結論から言うと先程の結果が出てくるほど遅くはなかった。瞬間で終わる。

細い設定とか

hprofを取るときの設定は、-agentlib:hprof=cpu=samples,depth=30 -XX:+HeapDumpOnOutOfMemoryError

あとScalaのバージョンは2.10.2

原因

お前List（双方向リスト）にIndexアクセスしてんじゃねーよ！

val pentagonals = Stream.from(0).map(pentagonal).takeWhile(_ < (Int.MaxValue >> 2)).toList

...

val pj = pentagonals(j)
val pk = pentagonals(k)

toArrayになおしたら問題なく終わりました…。

ただしhprofさんが情報出してくれなかった点に関してはまだ調査中…。