Modegramming Style: [SDN]List性能問題

懸案だったMonadic Programming、Functional Reactive Programmingもある程度目処がついてきたこともあり、要件定義で作成されたモデルを実装に落とし込むという流れの中での総合的なScalaプログラミングの方法論をScala Design Noteという切り口で考察していこうと思います。

大昔にJava World誌で「Java Design Note」という連載を書いていましたが、そのScala版をイメージしています。

問題

Scalaを実務に使う場合に注意が必要なのがListの性能問題です。

Scalaでは関数型言語の伝統を踏襲してLispのList由来のListを基本データ構造としています。システムの各種デフォルトもListを使う方向になっていますし、文法を説明する場合にもListを使用するケースが多いと思います。

Listは関数型プログラミングとの相性はとてもよいので妥当な選択ではあるのですが、要素の後方追加が致命的に遅いという問題を持っています。この問題があるためListの使い方には注意が必要です。

致命的に遅いといっても小さなプログラムではほぼ問題はありませんが、プログラムの処理が本格化し、扱うデータ規模が大きくなってくると顕在化してきます。

ListはScalaの基本データ構造であり、普通にScalaを使っていると色々な所でListが自然に使用されますが、これがプロダクションコードとしてはアンチパターンという点がScalaプログラミングのハマりどころとなっています。

きっかけ

前回「Scalaへの道」で以下のcase class Wordsを実装しました。

この実装を行う中で、このように復数のオブジェクトを保持しているcase classを足し込んでいくような処理におけるListの危険性が判明したのが、今回の記事のきっかけになっています。

package sample

case class Words(
  smalls: Vector[String],
  middles: Vector[String],
  larges: Vector[String]
) {
  def +(word: String): Words = {
    if (word.length <= 3)
      copy(smalls = smalls :+ word)
    else if (word.length > 7)
      copy(larges = larges :+ word)
    else
      copy(middles = middles :+ word)
  }

  def +(words: Words): Words = {
    copy(
      smalls ++ words.smalls,
      middles ++ words.middles,
      larges ++ words.larges
    )
  }

  def ++(words: Seq[String]): Words = {
    words.foldLeft(this)(_ + _)
  }

  override def toString() = s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
}

object Words {
  val empty = Words(Vector.empty, Vector.empty, Vector.empty)

  def apply(word: String): Words = empty + word

  def apply(words: Seq[String]): Words = empty ++ words

  def getTokens(s: String): Vector[String] =
    s.split(" ").filter(_.nonEmpty).toVector
}

問題

性能測定のため前述のcase class Wordsを単純化し、測定パターンごとに復数の実装を用意しました。以下は、宣言にIndexedSeq、実装にVectorを採用した実装であるWordsIVです。これを含めて16パターンの測定を行いました。(後述の表参照)

case class WordsIV(
    smalls: IndexedSeq[String],
    middles: IndexedSeq[String],
    larges: IndexedSeq[String]
  ) {
    def +(word: String): WordsIV = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsIV {
    val empty = WordsIV(Vector.empty, Vector.empty, Vector.empty)
  }

case class WordsVは以下のようにして積算した時の実行時間を計測しました。

go("WordsIV") {
      inputs.foldLeft(WordsIV.empty)(_ + _)
    }

測定のパターン

性能測定パターンは以下になります。この中の「WordsIV」のプログラムは前述しました。その他のパターンのプログラムは一番最後に一括で置いておきます。

測定名	性能(ms)	宣言	実装	追加場所	備考
WordsJ	30	ArrayBuffer	ArrayBuffer	後
WordsV	33	Vector	Vector	後
WordsL	27717	List	List	後
WordsVP	32	Vector	Vector	前
WordsLP	28	List	List	前
WordsSV	19840	Seq	Vector	後
WordsSVV	32	Seq	Vector	後	ロジック工夫
WordsS	27620	Seq	Seq	後
WordsSP	31	Seq	Seq	前
WordsIV	30	IndexedSeq	Vector	後
WordsIA	614	IndexedSeq	Array	後
WordsI	29	IndexedSeq	IndexedSeq	後
WordsIP	29	IndexedSeq	IndexedSeq	前
WordsBuilderV	25	Vector	ArrayBuffer	後	Builder
WordsBuilderL	29	List	ArrayBuffer	後	Builder
WordsBuilderS	25	Seq	ArrayBuffer	後	Builder

考察

性能測定の結果をまとめると以下のような結果が得られました。

Listに追記する処理は圧倒的に遅い (WordsL, WordsSV, WordsS)
ArrayBuffer、Vectorへの追記、List、Vectorへの前置挿入はほとんど同じ性能 (WordsJ, WordsV, WordsVP, WordsLP)
SeqとVectorの組合せはロジックを工夫しないと非常に遅くなることがある (WordsSV)
Vectorへの前置挿入はほとんどListと変わらない (WordsVP, WordsLP)

Seqのデフォルト実装はListなのでWordsSも事実上Listの追記処理のパターンになります。WordLとWordsSの結果からListの追記処理が非常に低速なのは明らかです。

また、宣言にSeq、初期実装にVectorを使うWordsSVは実装にVectorを使う意図なのですが、ロジックの綾で実際はListが使われるようになるらしく非常に低速です。

ただWordsSVと同じパターンのWordsSVVは宣言Vector、実装VectorのWordsVなどと同じ性能が出ています。宣言にSeq、初期実装にVectorのパターンは実装時のロジックの綾で非常に低速になったり、通常性能になったりしてリスクが高い処理パターンといえます。

コンテナの選択

まずコンテナの候補としてはVector一択かなと考えています。

Listは追記性能が非常に遅いので、使い方に注意が必要な点がデメリットです。また、単方向リストによる実装方式からメモリも多目に消費することが推測されます。

VectorとListの性質を比較した場合、Listは前置挿入が得意で追記が苦手、Vectorは追記が得意で前置挿入が苦手、という整理の仕方がありますが、Vectorは追記が得意で前置挿入も大丈夫、というの実際のところです。

Vectorは万能で用途を選ばないのに対して、Listは追記が苦手という弱点があるので、利用局面に応じて意識して使用する必要があります。

このためコンテナの選択は弱点がないVectorの一択と考えてよいと思います。

Listは関数型言語の伝統的なデータ構造なので変な話ですが、ScalaにおけるListはHashSetなどと同様の特殊用途向けコンテナとして割り切って使うぐらいがベストプラクティスではないかと思います。

Listの長所

Listが向いている「特殊用途」は何かという話ですが、伝統的な関数型プログラムということになります。

関数型プログラミングでよく出てくる再帰呼び出しでの利用は、専用の文法が用意されていて便利です。たとえば、以下のようなコーディングパターンです。

def f(a: List[Int]): Int = {
  a match {
    case Nil => 0
    case x :: xs => x + f(xs)
  }
}

ただVectorを始めとするSeqでも以下のように書けるので使えないと困るという程ではありません。

def f(a: Vector[Int]): Int = {
  a.headOption match {
    case None => 0
    case Some(x) => x + f(a.tail)
  }
}

補足：末尾再帰呼び出し

念のために補足です。

「Listの長所」で取り上げたコードはList処理を分かりやすく提示するのが目的なので再帰呼び出しは自然な方法を用いていますが、実はこの「自然な方法」はプロダクションコードとしては適切ではありません。というのは、このコードでは末尾再帰の最適化が得られないのでスタックオーバーフローのリスクがあるためです。

今回の場合は実務的には以下のようなコーディングになります。

def f(a: List[Int]): Int = {
  @annotation.tailrec
  def go(b: List[Int], sum: Int): Int = {
    b match {
      case Nil => sum
      case x :: xs => go(xs, x + sum)
    }
  }
  go(a, 0)
}

def f(a: Vector[Int]): Int = {
  @annotation.tailrec
  def go(b: Vector[Int], sum: Int): Int = {
    b.headOption match {
      case None => sum
      case Some(x) => go(b.tail, x + sum)
    }
  }
  go(a, 0)
}

宣言の選択

オブジェクトの集まりを実現する場合に使用するコンテナとして概ね以下の4つを日常的に使用します。

コンテナ	種別	説明
Seq	トレイト	先頭からのシーケンシャルアクセス
IndexedSeq	トレイト	ランダムアクセスに適したシーケンス
List	具象クラス	List構造のSeq
Vector	具象クラス	配列をベースとしたIndexedSq

SeqとIndexSeqはトレイトなので、それぞれ復数の具象クラスに対応します。関数の引数やオブジェクトのインスタンス変数にSeqやIndexSeqを指定することで、プログラムの実行時に具象クラスを使い分ける事ができるようになります。

ListとVectorは具象クラスなので、引数やインスタンス変数の型として指定すると型を最終決定してしまうことになります。逆に明確な決定が行われるので、予想外の動きによる性能劣化という事態は避ける事ができます。

一般的には、できるだけ抽象度の高いものを選択するのが得策です。その一方で、Seqを使うと前述のListの性能問題が発生する可能性があるので、一定のリスクがあります。

つまり汎用性と性能リスクのバランスを勘案して実装戦略を考えることになります。

実装戦略

case classの属性としてオブジェクトの集まりが必要になった時の実装戦略です。

以下が論点になります。

case class内での宣言
実装に使用するコンテナの選択

まず実装に使用するコンテナの選択は前述した通りVector一択としました。

つまり、実装の選択はVectorのみなので、残る選択は宣言に何を使うのかになります。

シンプル戦略

アプリケーション内で閉じた範囲で使用するcase classであれば、あまり凝ったつくりにしてもメリットは少ないので、宣言と実装の両方にVectorを使うのが簡明です。

性能測定パターンではWordsVが対応します。

安全戦略

宣言にSeqまたはIndexedSeq、実装にVectorを使うのが本格的な戦略です。

用途に応じてSeqとIndexedSeqを使い分けることができれば理想的ですが、Seqは前述のList性能問題が発生する可能性が出てくるので、安全策を採るのであれば常にIndexedSeqを使う戦略が有効です。

性能測定パターンではWordsIVが対応します。

上級戦略

対象となるcase classを操作する時のアクセスパターンが先頭からのシーケンシャルアクセスのみである場合、宣言には一番汎用性の高いSeqを使うのが理想的です。

性能測定パターンではWordsSVVが対応します。

Seqを使うことで、以下のように他のSeqコンテナをそのまま設定することとができるようになります。

WordsSVV(List("a"), List("abcde"), List("abcdefghijk"))

設定されたListをアクセスする場合は、そのままListでよいですが、後方追加の積算をそのままListで行うと性能問題が出てきます。

そこで、前出の「SeqとVectorの組合せはロジックを工夫」が必要になってきます。

具体的にはWordsSVで使用している以下のロジックでは不適切です。

def +(word: String): WordsSV = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

WordsSVVで使用している以下のロジックにする必要があります。このロジックのポイントは後方追加の演算の前にSeqをVectorに変換しているところです。こうすることによって、以降の計算に使用されるコンテナはVectorになるのでList性能問題は発生しなくなります。

def +(word: String): WordsSVV = {
      if (word.length <= 3)
        copy(smalls = smalls.toVector :+ word)
      else if (word.length > 7)
        copy(larges = larges.toVector :+ word)
      else
        copy(middles = middles.toVector :+ word)
    }

まとめ

case classを漫然と作っているとListの性能問題に遭遇してしまう可能性があるので、実装戦略としてまとめてみました。

結論としては以下の3パターンを適材適所で選んでいくのがよさそうです。

シンプル戦略 : 宣言 => Vector、実装 => Vector
安全戦略 : 宣言 => IndexedSeq、実装 => Vector
上級戦略 : 宣言 => Seq、実装 => Vector

上級戦略は「SeqとVectorの組合せはロジックを工夫」を意識しておく必要があるのが難点です。このような考慮が負担になるような場合は、安全戦略を基本戦略にしておくのが簡明でよいと思います。

測定プログラム

package sample

import scala.util.Try
import scala.collection.mutable.ArrayBuffer
import scalaz._, Scalaz._
import scalaz.stream._
import scalaz.concurrent.Task

object Performance {
  class WordsJ(
    val smalls: ArrayBuffer[String] = new ArrayBuffer[String],
    val middles: ArrayBuffer[String] = new ArrayBuffer[String],
    val larges: ArrayBuffer[String] = new ArrayBuffer[String]
  ) {
    def +(word: String): WordsJ = {
      if (word.length <= 3)
        smalls += word
      else if (word.length > 7)
        larges += word
      else
        middles += word
      this
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  case class WordsV(
    smalls: Vector[String],
    middles: Vector[String],
    larges: Vector[String]
  ) {
    def +(word: String): WordsV = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsV {
    val empty = WordsV(Vector.empty, Vector.empty, Vector.empty)
  }

  case class WordsL(
    smalls: List[String],
    middles: List[String],
    larges: List[String]
  ) {
    def +(word: String): WordsL = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsL {
    val empty = WordsL(List.empty, List.empty, List.empty)
  }

  case class WordsVP(
    smalls: Vector[String],
    middles: Vector[String],
    larges: Vector[String]
  ) {
    def +(word: String): WordsVP = {
      if (word.length <= 3)
        copy(smalls = word +: smalls)
      else if (word.length > 7)
        copy(larges = word +: larges)
      else
        copy(middles = word +: middles)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsVP {
    val empty = WordsVP(Vector.empty, Vector.empty, Vector.empty)
  }

  case class WordsLP(
    smalls: List[String],
    middles: List[String],
    larges: List[String]
  ) {
    def +(word: String): WordsLP = {
      if (word.length <= 3)
        copy(smalls = word :: smalls)
      else if (word.length > 7)
        copy(larges = word :: larges)
      else
        copy(middles = word :: middles)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsLP {
    val empty = WordsLP(List.empty, List.empty, List.empty)
  }

  case class WordsSV(
    smalls: Seq[String],
    middles: Seq[String],
    larges: Seq[String]
  ) {
    def +(word: String): WordsSV = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsSV {
    val empty = WordsSV(Vector.empty, Vector.empty, Vector.empty)
  }

  case class WordsSVV(
    smalls: Seq[String],
    middles: Seq[String],
    larges: Seq[String]
  ) {
    def +(word: String): WordsSVV = {
      if (word.length <= 3)
        copy(smalls = smalls.toVector :+ word)
      else if (word.length > 7)
        copy(larges = larges.toVector :+ word)
      else
        copy(middles = middles.toVector :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsSVV {
    val empty = WordsSVV(Vector.empty, Vector.empty, Vector.empty)
  }

  case class WordsS(
    smalls: Seq[String],
    middles: Seq[String],
    larges: Seq[String]
  ) {
    def +(word: String): WordsS = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsS {
    val empty = WordsS(Seq.empty, Seq.empty, Seq.empty)
  }

  case class WordsSP(
    smalls: Seq[String],
    middles: Seq[String],
    larges: Seq[String]
  ) {
    def +(word: String): WordsSP = {
      if (word.length <= 3)
        copy(smalls = word +: smalls)
      else if (word.length > 7)
        copy(larges = word +: larges)
      else
        copy(middles = word +: middles)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsSP {
    val empty = WordsSP(Seq.empty, Seq.empty, Seq.empty)
  }

  case class WordsIV(
    smalls: IndexedSeq[String],
    middles: IndexedSeq[String],
    larges: IndexedSeq[String]
  ) {
    def +(word: String): WordsIV = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsIV {
    val empty = WordsIV(Vector.empty, Vector.empty, Vector.empty)
  }

  case class WordsIA(
    smalls: IndexedSeq[String],
    middles: IndexedSeq[String],
    larges: IndexedSeq[String]
  ) {
    def +(word: String): WordsIA = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsIA {
    val empty = WordsIA(Array[String](), Array[String](), Array[String]())
  }

  case class WordsI(
    smalls: IndexedSeq[String],
    middles: IndexedSeq[String],
    larges: IndexedSeq[String]
  ) {
    def +(word: String): WordsI = {
      if (word.length <= 3)
        copy(smalls = smalls :+ word)
      else if (word.length > 7)
        copy(larges = larges :+ word)
      else
        copy(middles = middles :+ word)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsI {
    val empty = WordsI(IndexedSeq.empty, IndexedSeq.empty, IndexedSeq.empty)
  }

  case class WordsIP(
    smalls: IndexedSeq[String],
    middles: IndexedSeq[String],
    larges: IndexedSeq[String]
  ) {
    def +(word: String): WordsIP = {
      if (word.length <= 3)
        copy(smalls = word +: smalls)
      else if (word.length > 7)
        copy(larges = word +: larges)
      else
        copy(middles = word +: middles)
    }

    override def toString() = {
      s"small:${smalls.length}, middle:${middles.length}, large:${larges.length}"
    }
  }

  object WordsIP {
    val empty = WordsIP(IndexedSeq.empty, IndexedSeq.empty, IndexedSeq.empty)
  }

  class WordsBuilderV {
    private val smalls = new ArrayBuffer[String]
    private val middles = new ArrayBuffer[String]
    private val larges = new ArrayBuffer[String]

    def +(word: String): WordsBuilderV = {
      if (word.length <= 3)
        smalls += word
      else if (word.length > 7)
        larges += word
      else
        middles += word
      this
    }

    def toWords = WordsV(smalls.toVector, middles.toVector, larges.toVector)
  }

  class WordsBuilderL {
    private val smalls = new ArrayBuffer[String]
    private val middles = new ArrayBuffer[String]
    private val larges = new ArrayBuffer[String]

    def +(word: String): WordsBuilderL = {
      if (word.length <= 3)
        smalls += word
      else if (word.length > 7)
        larges += word
      else
        middles += word
      this
    }

    def toWords = WordsL(smalls.toList, middles.toList, larges.toList)
  }

  class WordsBuilderS {
    private val smalls = new ArrayBuffer[String]
    private val middles = new ArrayBuffer[String]
    private val larges = new ArrayBuffer[String]

    def +(word: String): WordsBuilderS = {
      if (word.length <= 3)
        smalls += word
      else if (word.length > 7)
        larges += word
      else
        middles += word
      this
    }

    def toWords = WordsS(smalls, middles, larges)
  }

  def go[T](label: String)(body: => T) {
    val start = System.currentTimeMillis
    try {
      val r = body
      val result = r match {
        case x: Try[_] => x.toString
        case x: Task[_] => x.toString
        case x => x.toString
      }
      val end = System.currentTimeMillis
      println(s"$label (${end - start}): ${result}")
    } catch {
      case e: Throwable =>
        val end = System.currentTimeMillis
      println(s"$label (${end - start}): ${e}")
    }
  }

  import scalax.io.{Resource, Codec}

  def main(args: Array[String]) {
    import Words.getTokens
    implicit val codec = Codec.UTF8
    val filename = "PrincesOfMars.txt"
    val inputs = Resource.fromFile(filename).lines().
      map(getTokens).
      foldLeft(new ArrayBuffer[String])(_ ++ _)
    go("WordsJ") {
      inputs.foldLeft(new WordsJ)(_ + _)
    }
    go("WordsV") {
      inputs.foldLeft(WordsV.empty)(_ + _)
    }
    go("WordsVP") {
      inputs.foldLeft(WordsVP.empty)(_ + _)
    }
    go("WordsL") {
      inputs.foldLeft(WordsL.empty)(_ + _)
    }
    go("WordsLP") {
      inputs.foldLeft(WordsLP.empty)(_ + _)
    }
    go("WordsS") {
      inputs.foldLeft(WordsS.empty)(_ + _)
    }
    go("WordsSP") {
      inputs.foldLeft(WordsSP.empty)(_ + _)
    }
    go("WordsSV") {
      inputs.foldLeft(WordsSV.empty)(_ + _)
    }
    go("WordsSVV") {
      inputs.foldLeft(WordsSVV.empty)(_ + _)
    }
    go("WordsI") {
      inputs.foldLeft(WordsI.empty)(_ + _)
    }
    go("WordsIP") {
      inputs.foldLeft(WordsIP.empty)(_ + _)
    }
    go("WordsIV") {
      inputs.foldLeft(WordsIV.empty)(_ + _)
    }
    go("WordsIA") {
      inputs.foldLeft(WordsIA.empty)(_ + _)
    }
    go("WordsBuilderV") {
      inputs.foldLeft(new WordsBuilderV)(_ + _).toWords
    }
    go("WordsBuilderL") {
      inputs.foldLeft(new WordsBuilderL)(_ + _).toWords
    }
    go("WordsBuilderS") {
      inputs.foldLeft(new WordsBuilderS)(_ + _).toWords
    }
  }
}

諸元

Mac OS 10.7.5 (2.6 GHz Intel Core i7)
Java 1.7.0_75
Scala 2.11.6

Modegramming Style

2015年7月27日月曜日

[SDN]List性能問題

問題

きっかけ

問題

測定のパターン

考察

コンテナの選択

Listの長所

補足：末尾再帰呼び出し

宣言の選択

実装戦略

シンプル戦略

安全戦略

上級戦略

まとめ

測定プログラム

諸元

0 件のコメント:

コメントを投稿

MathJax

Twitter

ブログアーカイブ

ラベル

フォロワー

メール購読

自己紹介

Blogger Syntax Highliter

Modegramming Style

2015年7月27日月曜日

[SDN]List性能問題

問題

きっかけ

問題

測定のパターン

考察

コンテナの選択

Listの長所

補足：末尾再帰呼び出し

宣言の選択

実装戦略

シンプル戦略

安全戦略

上級戦略

まとめ

測定プログラム

諸元

0 件のコメント:

コメントを投稿

MathJax

Twitter

ブログ アーカイブ

ラベル

フォロワー

登録

メール購読

自己紹介

Blogger Syntax Highliter

ブログアーカイブ