no-image

Dartで三角関数ルックアップテーブルのパフォーマンスを調べる

一般に、超越関数の計算にはコストがかかる。処理能力が乏しい環境では、ルックアップテーブルを作成するなどして、計算の高速化を図ることがある。特に三角関数は入力値の範囲を限定でき、ルックアップテーブルを容易に実装することができるので、様々な場面で活用されている。Flash時代にお世話になった人も多いのではないだろうか。

さて、そんな泥臭い最適化法は現代でも通用するのだろうか。超越関数の相対的な計算負担の高さは変わらないが、プロセッサや仮想マシンは年々高性能・高機能化している。全く効果が無いとまでは言わないが、かつてほどの効果は得られないのではないだろうか。可読性を確保するための処理のオーバーヘッドがかさんで無意味になってしまうことも考えられる。

少し気になったので、Dartおよびdart2jsで変換されたJavaScriptで計測してみた。

単純なルックアップテーブル

以下を用いてそれぞれsinの値を求め、計算にかかる時間を比較した。

  • 標準ライブラリのsin関数
  • sin関数の値を保持したルックアップテーブル

また、ルックアップテーブルには以下の3種類を用意して、それぞれ計測した。

  • 可変長List
  • 固定長List
  • Map

計測条件

  • 角度は0度から359度の間の整数値を使用する
  • sin関数での計算の際は、角度からラジアンへ変換する処理が入る

時間の計測にはbenchmark_harnessライブラリのデフォルト設定を用いた。以下のような条件になる。

  • 関数を10回実行するのにかかった時間を測る
  • 2秒間計測し続けて、その平均時間を結果とする

計測環境

  • iMac late 2013 (Core i7 4770S)
  • Dart SDK 1.5.3
  • Dartium 36

結果

 

trig_lookup_table_performance

いずれの場合においても、ルックアップテーブルを用いた方が大きなアドバンテージを得られた。ルックアップテーブルはsin関数に対して、DartVMでは7.6倍、JavaScriptでは3.7倍ほどの速度が出る結果となった。

次に各データ構造を比べてみよう。可変長Listと固定長Listでは、大きな差は出なかった。Mapはsin関数と比べるとはるかに速かったが、Listほどではない。基本的にはListを使えば問題ないだろう。

少し奇妙なのが、JavaScriptでのランダムアクセスだ。ルックアップテーブルを用いた方が速いのは同じだが、いずれの場合もシーケンシャルアクセスに対して著しく遅い。JSエンジンの最適化の関係だろうか。この点については、この記事の本質ではないのであまり深くは追求しないが、後ほど軽く検証する。

ソースコード

実行するにはpubspec.yamlにbenchmark_harnessを追加する必要がある。

import 'dart:html';
import 'dart:math';
import 'package:benchmark_harness/benchmark_harness.dart';

List<int> range(int begin, int end) => new List.generate(end-begin, (idx)=>begin+idx, growable:false);

void main() {
  var sinList      = new List<double>();
  var sinFixedList = new List<double>(360);
  var sinMap       = new Map<int, double>();

  for(var idx in range(0,360)) {
    var value = sin(idx/180*PI);
    sinList.add(value);
    sinFixedList[idx] = value;
    sinMap[idx]       = value;
  }

  var sequential = range(0,360);

  const SEED = 42;
  var   random = new Random(SEED);
  var   randomList = new List<int>(360);
  range(0,360).forEach((idx)=>randomList[idx]=random.nextInt(360));

  const CONVERTER = PI/180;

  var benchRawSeq       = new Benchmark("[Sequential] sin", ()=>sequential.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListSeq      = new Benchmark("[Sequential] list",()=>sequential.forEach((idx)=>sinList[idx]));
  var benchFixedListSeq = new Benchmark("[Sequential] fixed list",()=>sequential.forEach((idx)=>sinFixedList[idx]));
  var benchMapSeq       = new Benchmark("[Sequential] map",()=>sequential.forEach((idx)=>sinMap[idx]));

  var benchRawRnd       = new Benchmark("[Random] sin", ()=>randomList.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListRnd      = new Benchmark("[Random] list",()=>randomList.forEach((idx)=>sinList[idx]));
  var benchFixedListRnd = new Benchmark("[Random] fixed list",()=>randomList.forEach((idx)=>sinFixedList[idx]));
  var benchMapRnd       = new Benchmark("[Random] map",()=>randomList.forEach((idx)=>sinMap[idx]));

  print("Sequential");
  benchRawSeq.report();
  benchListSeq.report();
  benchFixedListSeq.report();
  benchMapSeq.report();

  print("Random");
  benchRawRnd.report();
  benchListRnd.report();
  benchFixedListRnd.report();
  benchMapRnd.report();

  print("done.");
}

class Benchmark extends BenchmarkBase {
  Function func;
  Benchmark(String name, this.func) : super(name);

  @override
  void run() => func();
}

関数を介したルックアップテーブル

ルックアップテーブルを利用する場合、現実的には関数などを介してアクセスすることが多いだろう。その際のオーバーヘッドを考えると、わずか数十μsしかないアドバンテージは消え去ってしまう可能性がある。そこで、関数を介した場合の処理速度についても計測を行った。

結果

trig_lookup_table_performance_func

リストに直接アクセスする場合と関数を介してアクセスした場合との間に大きな差は見られなかった。

ソースコード

import 'dart:html';
import 'dart:math';
import 'package:benchmark_harness/benchmark_harness.dart';

List<double> sinList;

List<int> range(int begin, int end) => new List.generate(end-begin, (idx)=>begin+idx, growable:false);

double sinDeg(int deg) => sinList[deg];

class Math {
  static sinDeg(int deg) => sinList[deg];
}

void main() {
  sinList = new List<double>();

  for(var idx in range(0,360)) {
    var value = sin(idx/180*PI);
    sinList.add(value);
  }

  var sequential = range(0,360);

  const SEED = 42;
  var   random = new Random(SEED);
  var   randomList = new List<int>(360);
  range(0,360).forEach((idx)=>randomList[idx]=random.nextInt(360));

  const CONVERTER = PI/180;

  var benchRawSeq        = new Benchmark("[Sequential] sin", ()=>sequential.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListSeq       = new Benchmark("[Sequential] list",()=>sequential.forEach((idx)=>sinList[idx]));
  var benchFuncSeq       = new Benchmark("[Sequential] func",()=>sequential.forEach((idx)=>sinDeg(idx)));
  var benchStaticFuncSeq = new Benchmark("[Sequential] static func",()=>sequential.forEach((idx)=>Math.sinDeg(idx)));

  var benchRawRnd        = new Benchmark("[Random] sin", ()=>randomList.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListRnd       = new Benchmark("[Random] list",()=>randomList.forEach((idx)=>sinList[idx]));
  var benchFuncRnd       = new Benchmark("[Random] func",()=>randomList.forEach((idx)=>sinDeg(idx)));
  var benchStaticFuncRnd = new Benchmark("[Random] static func",()=>randomList.forEach((idx)=>Math.sinDeg(idx)));

  print("Sequential");
  benchRawSeq.report();
  benchListSeq.report();
  benchFuncSeq.report();
  benchStaticFuncSeq.report();

  print("Random");
  benchRawRnd.report();
  benchListRnd.report();
  benchFuncRnd.report();
  benchStaticFuncRnd.report();

  print("done.");
}

class Benchmark extends BenchmarkBase {
  Function func;
  Benchmark(String name, this.func) : super(name);

  @override
  void run() => func();
}

角度を任意の整数で受け付ける関数

角度を0度から359度の間でしか指定できないのは不便だ。よって普通は任意の整数を受け取り、0から359の整数へと変換する処理を行うだろう。この場合のパフォーマンスについても計測した。

なお、計測は-180度から179度までの間で行った。

結果

trig_lookup_table_performance_func_arbitrary

依然ルックアップテーブルが優位だ。

ソースコード

import 'dart:html';
import 'dart:math';
import 'package:benchmark_harness/benchmark_harness.dart';

List<double> sinList;
List<int>    sequential;
List<int>    randomList;

List<int> range(int begin, int end) => new List.generate(end-begin, (idx)=>begin+idx, growable:false);

double sinDeg(int deg) => (deg >= 0 && deg < 360) ? sinList[deg] : sinList[deg%360];

class Math {
  static sinDeg(int deg) => (deg >= 0 && deg < 360) ? sinList[deg] : sinList[deg%360];
}

void main() {
  sinList = new List<double>();

  for(var idx in range(0,360)) {
    var value = sin(idx/180*PI);
    sinList.add(value);
  }

  sequential = range(-180,180);

  const SEED = 42;
  var random = new Random(SEED);
  randomList = new List<int>(360);
  range(0,360).forEach((idx)=>randomList[idx]=(random.nextInt(360)-180));

  const CONVERTER = PI/180;

  var benchRawSeq        = new Benchmark("[Sequential] sin", ()=>sequential.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListSeq       = new Benchmark("[Sequential] list",()=>sequential.forEach((idx)=>(idx >= 0 && idx < 360) ? sinList[idx] : sinList[idx%360]));
  var benchFuncSeq       = new Benchmark("[Sequential] func",()=>sequential.forEach((idx)=>sinDeg(idx)));
  var benchStaticFuncSeq = new Benchmark("[Sequential] static func",()=>sequential.forEach((idx)=>Math.sinDeg(idx)));

  var benchRawRnd        = new Benchmark("[Random] sin", ()=>randomList.forEach((idx)=>sin(idx*CONVERTER)));
  var benchListRnd       = new Benchmark("[Random] list",()=>randomList.forEach((idx)=>(idx >= 0 && idx < 360) ? sinList[idx] : sinList[idx%360]));
  var benchFuncRnd       = new Benchmark("[Random] func",()=>randomList.forEach((idx)=>sinDeg(idx)));
  var benchStaticFuncRnd = new Benchmark("[Random] static func",()=>randomList.forEach((idx)=>Math.sinDeg(idx)));

  print("Sequential");
  benchRawSeq.report();
  benchListSeq.report();
  benchFuncSeq.report();
  benchStaticFuncSeq.report();

  print("Random");
  benchRawRnd.report();
  benchListRnd.report();
  benchFuncRnd.report();
  benchStaticFuncRnd.report();

  print("done.");
}

class Benchmark extends BenchmarkBase {
  Function func;
  Benchmark(String name, this.func) : super(name);

  @override
  void run() => func();
}

結論

超越関数のルックアップテーブルは、今でも高い効果を発揮する。ただし、10回あたり数十μsの差という非常に小さい物なので、一般のアプリケーションで役に立つことはない。しかし、数千回・数万回の処理を短い時間で終わらせなければいけない場面においては大きな効果があるだろう。

また、今回はサンプル数が360の場合のみを扱ったが、よりサンプル数が多い場合についても検証の余地があるだろう。

なお、こういった枝葉の部分の最適化は、システム全体のボトルネックとなる部分をきちんと把握し、本当に必要なのかどうか見極めてからにしよう。

余談:JavaScriptの配列へのランダムアクセス

いろいろな数字があった方が賑やかになるだろうというだけの理由で、別段意味があるわけでもなくランダムアクセスについても計測したが、まさか遅くなるとは思っていなかった。配列の要素には定数オーダーでアクセスできるだろうし、データ量も十分小さいのでシーケンシャルアクセスと結果は変わらないと考えていた。

dart2jsの生成したコードを軽く覗いてみたが、シーケンシャルとランダムで違いがあるようには見えなかった。また、メモリアクセスの問題であればDartでも同様の現象が起こるはずだが、確認できなかった。よってJSエンジン側の問題なのだろう。

面倒な検証を行いたくはないが気にはなるので、各ブラウザで配列へのシーケンシャルアクセスとランダムアクセスの比較を行ってみた。計測したのは空ループとリストアクセスの2つになる。

結果

js_rnd_seq_access

やはりランダムアクセスは遅い。Safariを除いては。Chromeでは空ループの段階から既に大きな差が出ている。ランダムが遅いというよりもシーケンシャルが速い(最適化されている)と考えれば説明は付くが、根拠がない。もう少し詳しく調べれば何かがわかるのかもしれないが、今のところ調べる気もない。真面目に調べようとすると、きっと生のJavaScriptを書くはめになるので、遠慮したい。

単に実行環境依存であるとか、たまたまJS実行エンジンの機嫌が悪かったとか、そもそもベンチの取り方が悪いといったことも考えられる。

気になる人は各自で調べてみよう。いわゆる「この問題は読者への練習問題とする」というやつだ。

ソースコード

import 'dart:html';
import 'dart:math';
import 'package:benchmark_harness/benchmark_harness.dart';

List<int> range(int begin, int end) => new List.generate(end-begin, (idx)=>begin+idx, growable:false);

void main() {
  var list = range(0,360);
  var sequential = range(0,360);

  const SEED = 42;
  var   random = new Random(SEED);
  var   randomList = new List<int>(360);
  range(0,360).forEach((idx)=>randomList[idx]=random.nextInt(360));

  const CONVERTER = PI/180;

  var benchForEachSeq = new Benchmark("[Sequential] forEach", ()=>sequential.forEach((idx)=>null));
  var benchForEachRnd = new Benchmark("[Random] forEach", ()=>randomList.forEach((idx)=>null));
  var benchSeq        = new Benchmark("[Sequential] list", ()=>sequential.forEach((idx)=>list[idx]));
  var benchRnd        = new Benchmark("[Random] list", ()=>randomList.forEach((idx)=>list[idx]));

  benchForEachSeq.report();
  benchForEachRnd.report();
  benchSeq.report();
  benchRnd.report();
  print("done.");
}

class Benchmark extends BenchmarkBase {
  Function func;
  Benchmark(String name, this.func) : super(name);

  @override
  void run() => func();
}