コグノスケ

muslのmemset関数

目次: ベンチマーク

musl C library（サイトへのリンク）のmemset関数の実装はかなり気合が入っており、特に先頭＆終端データの処理が面白いです。

こんなコードです。

if (!n) return dest;
s[0] = c;
s[n-1] = c;
if (n <= 2) return dest;
s[1] = c;
s[2] = c;
s[n-2] = c;
s[n-3] = c;
if (n <= 6) return dest;
s[3] = c;
s[n-4] = c;
if (n <= 8) return dest;

私はぱっと見では何をしてるのかさっぱりわかりませんでした。図を書いてみてやっと意味が分かりました。

処理開始前

領域のサイズnが1〜8の場合、このコードだけで処理が終わります。説明の都合上、ifを区切りとして、3つのかたまり（赤、緑、青）に分けました。n = 1, 2の場合は赤だけ、n = 3, 4, 5, 6の場合は赤＋緑、n = 7, 8の場合は赤＋緑＋青が実行されます。

ゴチャゴチャ説明するより、1ステップずつ、実行した結果を図示した方がわかりやすいかと思います。

s[0] = cまで

s[n - 1] = cまで、 n = 1, 2はmemset完了

s[1] = c, s[2] = cまで

s[n - 2] = c, s[n - 3] = cまで、 n = 3, 4, 5, 6はmemset完了

s[3] = cまで

s[n - 4] = cまで、 n = 7, 8はmemset完了、それ以上のサイズは処理を継続

図を見るとわかるように、同じ領域に2回以上書く場合がありますが、memsetは同じ領域に2度書いても問題ありません（書き込む値は同じなので、何度書いても結果は同じ）。

この「何度書いても良い」性質を利用して、分岐を限界まで減らす戦略のようです。

ストアより分岐を減らす方がメリットがある、とみているわけですね。イマドキのCPUに合った最適化なのでしょうね。

メモ: 技術系の話はFacebookから転記しておくことにした。大幅に追記。