C# 高速化のヒント : プログラミング指南

現在私が制作中のマップエディタで、部分消去という処理があります。この部分消去は、同じパーツが隣接していた場合に、それを間引くという機能も実装しようとしてました。そのとき、最初のコードからは 40% 程度までは高速化できたのですが、それをTwitterでもっと速くならないかと、フォロワーの皆さんに提示したところ、様々な提案がありまして、そちらを試していったところ、50%まで高速化する事が出来ました。今回はその手法について、具体的に説明していきたいと思います。

どう変わったのか
一番最初はこんな状態でした。
最初の実行速度

処理時間はむ 186ms です。ここから自力である程度は高速化していたのですが、私のTLにいるフォロワーの皆様は流石は百戦錬磨です。こういうのはどうかと次々と提案してもらい、試しているうちに完成したのが、次のコードです。
高速化対応済みコード

コードサイズは一気に大きくなりました。ですが、処理速度は一気に 97ms と 100の大台を切ってきました。それでは一つずつ、高速化の理由について解説していきます。

プロパティ参照をローカル変数参照とした
最初はループの終端チェックで Size 構造体変数の CharaSize の Width と Height を参照していました。これはプロパティ参照のオーバーヘッドが入るため、若干ですが遅くなります。そこでループの開始前に Width と Height をそれぞれスコープ内のローカル変数に置き換えて、そちらを終端判定に使用するようにしました。

速度向上は数msでしたが、確実に速くなりました。

【Amazon】
プラスキッチンバサミ料理ばさみ分解食洗機対応フィットカットカーブマッシュルームホワイト紙箱包装 35728

PLUS(プラス)

2020-11-24
※ 妻が使ってます。切れ味も良く分離するとペーパーナイフのような使い方が出来るためとても重宝しています。

zero 定数参照をローカル変数参照とした
これはこんなの効くかなと思いながら試してみたところ、数msながら意外にも確実に速度アップに繋がりました。正確な理由は不明ですが、定数参照よりローカル変数参照の方が速いという事なのでしょうか…

ループ内の範囲内判定を無くした
これは効果としてはかなり大きかったです。今回のテストケースでは、9,801,000 という巨大な要素数をもつ二次元配列でしたが、その相当数のループ内に存在する if 判定を減らす事になったので、効果が大きいのも当然と言えます。

0 からスタートすると -1 したら配列範囲外アクセスになってしまうので、範囲内判定を入れていましたが、この範囲外が発生するのは、最上部の1行と最左端の1列だけと、例外発生タイミングは確定しています。そのため、ループの開始を 0 ではなく 1 からとしてしまえば、ループは必ず範囲内で走るようになるので、範囲内判定は不要になります。

ただ、そのままだと最上部と最左端が隣接判定されませんので、最上部と最左端だけ別途専用のループを走らせる必要が出ます。結果、一気にプログラムコードの長さが3倍近く大きくなりますが、元々そんなに大きい処理ではないので、この程度のサイズアップは許容範囲と考えました。

ループ内から判定を外すのは効くんですよねw

二次元配列の参照ループを連続的に参照できるようにした
最初は Y → X とループしていますが、これを X → Y とループの方向を変更しています。これ、そこそこ高速に変わるんです。理由ですが、後述のループは C言語のポインタ的にはインクリメント一発で参照が出来るようになるためのようです。つまり、コンパイラがより最適な変換を行いやすいというわけです。

二次元配列の次元別要素数の受け取りに GetLength() というメソッドがありますが、その第一要素、第二要素とループを構築するようにすると、最適化が掛かりやすいようです。覚えておくと良いですね。

対象を消去したら次は隣接ではない
これに気がついた人は少なかったのですが、= zero; と代入した、つまりはその場所を消去したら次は絶対に隣接ではないです。そのため、ポインタ的に次のアドレスになるよう、内側の添え字カウンタを余分に +1 してやります。

これで、データの隣接が多いほど効果が高くなります。これは疎の時も zero が隣接しますので処理速度の向上に繋がったりします。この効果は絶大でした！

意外と効果が薄かった対応は
まず、修正したときに isModift = true; を毎回しているのを、なんとかして一度だけで済まそうと試みました。これ、効き目が薄く、かつ、実装方法によっては逆に遅くなりました。この態度の処理は最適化で無視できると言う事なのでしょうか。

また、ループ内で x - 1 とあるのを、第2ループが始まる直前に var zx = x - 1; 等と格納しておき、x - 1 を zx に置き換えるアイディアは、試してみたところ、殆ど変わらないか、場合によっては遅くなってしまいました。想像ですが、CPU にとっては -1 はデクリメント一発なので大した負荷にはならないのに対して、zx と作ってしまうと毎回変数の内容を拾ってくるため遅いのかなあと思いました。

以上、意外に盛り上がったのでしたw