link もっと前
   2019年 12月 13日 -
      2019年 12月 4日  
link もっと後

link 未来から過去へ表示(*)
link 過去から未来へ表示

日々

link permalink

link 編集する

musl の memset 関数

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

こんなコードです。

musl 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 から転記しておくことにした。大幅に追記。

[編集者: すずき]
[更新: 2019年 12月 15日 23:01]

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2019年 12月 13日 -
      2019年 12月 4日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 6/6 18:42

カレンダー

<2019>
<<<12>>>
1234567
891011121314
15161718192021
22232425262728
293031----

最近のコメント 5件

  • link 20年05月02日
    すずき 「ちょっと調べたところ、コアが焼けると騒ぎ...」
    (更新:05/08 15:43)
  • link 20年05月02日
    すずき 「結構、怖い制御に見えますね&hellip...」
    (更新:05/08 15:23)
  • link 20年05月02日
    hdk 「デスクトップ用のNVIDIA Quadr...」
    (更新:05/07 20:30)
  • link 20年01月27日
    すずき 「詳細は調べていないので、コード中のコメン...」
    (更新:04/18 23:05)
  • link 20年01月27日
    superzeros 「少し気になったのでglibcの履歴を調べ...」
    (更新:04/16 21:07)

最近の記事 3件

link もっとみる
  • link 20年06月06日
    すずき 「[Kindle Fire の本が消える病] 割と昔からですが Ki...」
    (更新:06/06 18:42)
  • link 20年06月05日
    すずき 「[FSF Copyright Assignment] FSF (F...」
    (更新:06/06 16:02)
  • link 20年06月04日
    すずき 「[GCC を調べる - その 14-2 - genopinit] ...」
    (更新:06/04 12:18)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報