firstWhereのパフォーマンス

コードを書いていると、このコードは内部的にどの程度オプティマイズされるのだろうかと疑問に思うことがあります。
そこで最適化されそうなコードを書いたら実際に最適化されるのか試してみようと思います。

お題

idをキーに大量の行同士（下記クラスを一万個ランダムに並べたリスト）を結合するスピードを計測します。
（SQLのJOINです。）

class

class Row {
  int id;
  double number;

  Row(this.id, this.number);
}

ルール

1. １万行のRowを二つ用意
   1. idは1~9999
   2. numberは0.0<n<1.0のランダムな小数
   3. 表はランダムにソート
2. 二つの表の同じidのRowを見つけ出しnumber同士を掛け算
3. １万個の2.をすべて加算する
4. 1.-3.をそれぞれ100回ずつ変わりばんこに実施する

試したコード

1. 手作りfor文を使う
2. list.firstWhereを使う
3. 一度Mapに展開する

狙いとして

• 1.と2.は本質的に同じコードだが、2.はプリミティブなメソッドを使っているため1.より良いスコアを出して欲しい
• 3.は僕でも思いつく最適化方法だが、コンパイラがこれに思い至るか見たい

があります

main.dart

import 'dart:math';

const max = 10000;

void main() {

  var t1 = 0 , t2 = 0 , t3 = 0;
  for(var x = 0 ; x < 100 ; x ++) {
    t1 += time(firstWhere);
    t2 += time(forStatement);
    t3 += time(createMap);
    print("$x $t1 $t2 $t3");
  }
}

int time(Function f){
  var t1 = new DateTime.now();
  print(f());
  var t2 = new DateTime.now();
  return t2.millisecondsSinceEpoch - t1.millisecondsSinceEpoch;
}


double firstWhere() {
  var l1 = getSampleList();
  var l2 = getSampleList();

  for (var r1 in l1) {
    r1.number = cal(r1.number, l2
        .firstWhere((r2) => r1.id == r2.id)
        .number);
  }


  return getResult(l1);
}

double forStatement() {
  var l1 = getSampleList();
  var l2 = getSampleList();

  for (var r1 in l1) {
    for (var r2 in l2) {
      if (r1.id == r2.id) {
        r1.number = cal(r1.number, r2.number);
        break;
      }
    }
  }
  return getResult(l1);
}

double createMap() {
  var l1 = getSampleList();
  var l2 = getSampleList();

  var map = <int, Row>{};
  for (var r1 in l1) {
    map[r1.id] = r1;
  }

  for (var r2 in l2) {
    var r1 = map[r2.id];
    r1.number = cal(r1.number, r2.number);
  }
  return getResult(l1);
}

double getResult(List<Row> l1) {
  var result = 0.0;
  l1.forEach((r) => result = result + r.number);
  return result;
}


List<Row> getSampleList() {
  var r = new Random(new DateTime.now().millisecondsSinceEpoch);
  var list = <Row>[];

  for (var x = 0; x < max; x ++) {
    list.add(new Row(x, r.nextDouble()));
  }

  list.sort((r1, r2) => r.nextDouble().compareTo(r.nextDouble()));

  return list;
}

double cal(d1, d2) {

  return d1 * d2;
}

class Row {
  int id;
  double number;

  Row(this.id, this.number);
}

結果

	1.手書きfor文	2.firstWhere	3.Map
WebStorm上で実行	98539ms	100232ms	1697ms
jsに変換してChromeで実行	19005ms	16856ms	9158ms
ターミナル上で実行	44408ms	16484ms	1083ms

ちなみに「ターミナル上で実行」を試した理由として、
何も考えずにWebStorm上で実行したらChromeの方が圧倒的に速かったことにビビったからです。

考察

WebStorm上で実行

なぜか1.の方が早いという結果になりました。ラムダ式に入る時にファンクションコールオーバーヘッドというものが発生するのかなと思いました。
また、3.は他のやり方に比べてかなり速く、まだまだコンパイラの改善の余地があると思いました。コントリビュートチャンスかもしれません。

jsに変換してChromeで実行

JSでは3.がとても遅くなっています。JSのMapは遅いのでしょうか。
また、予想通り1.より2.が速くなっています。Dartはまだコンパイラの最適化が進んでいないが、V8は最適化チャンスに敏感なのかもしれません。

ターミナル上で実行

こちらも1.より2.が速くなっています。
じゃあWebStormは何だったのか。

結論

手書きでfor文を書くよりfirstWhereを使った方が速い。
速さが必要な場所では、まだまだ最適化用のコードを書くベネフィットは大きい。