O’REILLYの「JavaScriptグラフィックス」１章効率化についてメモ。
O’REILLYの書籍サイトではサンプルとして以下が掲載されている。
http://www.oreilly.co.jp/pub/9784873115283/ch01/ex0100.html
サインカーブを描くシンプルなもの。
特徴は
- Canvasを用いず、ブロック要素(div)をhtml側に記述しcssで幅・高さを指定
- ブロック要素内に幅1pxの縦線を幅の分の数描画する（この場合480本)
- 描画の開始位置と高さはJavaScriptで変動させアニメーション化する
効率化のメインは
- ルックアップテーブル
- ビット演算
の２つ。
１つ目のルックアップテーブルは、都度sinを計算するのではなく、前もってsinを計算し、配列に格納することにより速度向上を図るということ。wonderFL(flash)でもスクリプトで絵柄をビットマップ描画し、それを配列に格納することで超高速化していたサンプルがあった（http://wonderfl.net/c/c0Gi）。
一方、２つ目のビット演算は少々わかりづらい。
なんの前置きも無く、
drawGraph(x * 50, 32 - (sinTable[(x * 20) & 4095] * 16),
50 - (sinTable[(x * 10) & 4095] * 20));
とか
bars[i].style.top = 160 - height +
sinTable[(ang + (i * freq)) & 4095] * height + 'px';
など唐突に4095という数字が出てくる。
結局
配列の生成数4096は16の3乗、0×1000
配列範囲(添字）の最大値 4095は16の3乗-1 0xFFF
ということにさえ気づければなんということは無かったのだけれど。
このサンプルでは360度（Math.2PI)を4096分割し、そのsin値を配列に格納している。
タイマー内の変数xを単純な足し算(x++)でどんどん増やしているため、このxから0～4095（配列範囲）の添字を算出する必要がある。そこでビット単位のAND(&)計算を用い
0×1000 （＝4096)
0x FFF（＝4095) ＆
———————————–
0X 000（＝０ 配列の先頭の添字）
などと計算し、範囲溢れを防ぎつつ添字を求めている。
私はこういう場合、余り（%、MOD）を求めて算出するのが通常だった。
余りで計算する場合、配列数（length=４０９６）を用いる。
上記の例だと
4096%4096=0 余り0 配列の先頭
4097&4096=0 余り1 配列の2つ目
となる。
ところがこの「余り」の計算は四則演算の中で最も遅いらしい
(参考にさせていただきました http://ufcpp.net/study/algorithm/col_circular.html) 。
このサンプルでは高速化のため、これをAND演算に切り替えている。
なるほど。
確かにカーブを書く都度「余り」計算を行なっているので計算回数も多い。ここの高速化は全体への影響も大きいだろう。
これを流用したサンプルはまた後日。