link もっと前
   2020年 1月 24日 -
      2020年 1月 15日  
link もっと後

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

日々

link permalink

glibc の memset は強かった

目次です。

先日(2020年 1月 12日の日記参照)の続きです。

あまりにも glibc フルアセンブラ版 memset の実装が速くて勝てないので、観念して実装を見たのですが、序盤(1バイト〜32バイト)が弱い理由と、以降(33バイト〜)で勝てない理由がわかりました。

他の実装と違って glibc はサイズの大きい方から条件を見ています。どうしても条件分岐命令を通る回数が増えるため、序盤に弱いです。

中盤は 96 バイトまでは NEON store x 4 と分岐で捌いていて、ループを使いません。分岐も cmp して branch ではなく、ビットセットされていたら分岐する命令(tbz, tbnz)を使っています(※)。

つまり私が書いた memset はループで処理している時点で、ほぼ勝ち目がなかったということです。

グラフでは 63バイトまでしか測っていなかったから気づかなかったのですが、ループの 2週目に入る 65バイトから、さらにボロ負けです。いやはや、これは勝てないですね……。

(※)cmp, branch の 2命令を tbz 1命令にする辺り、AArch64 アセンブラならではの実装に見えますが、実は C でも if (a & 0x10) とか書くとコンパイラが tbz 命令を使います。コンパイラ侮りがたし。

[編集者: すずき]
[更新: 2020年 1月 26日 17:19]
link 編集する

コメント一覧

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



link permalink

glibc の memset のクセ

先日 memset を書いていたとき(2020年 1月 12日の日記参照)に気づいたのですが、glibc のフルアセンブラ版 memset の性能が 2通り(遅い、速い)あることに気づきました。だいたい 1割くらい性能が変わります。

遅いときと比較すると、自作の memset の方が速いですが、速いときと比較するとボロ負けします。割と性能が迫っているためか、影響が大きいです。

何が違うんでしょうね?コードは当然同じですから、違いは memset 関数のロードされるアドレスくらいです。まさかなと思って、スタティックリンクしたら安定して速くなりました。

ダイナミックリンクだと、アプリ側は 0xaaaac4fba560 で、glibc だけ 0xffffbf2dce00 のような遠いアドレスに飛ばされます。ベンチマーク中は、アプリのコード ←→ glibc のコードを頻繁に行き来することになるので、TLB ミスヒットの影響が出ているんですかね……??

真因はわかりませんが、アドレスが関係している可能性は高いです。今後、似たようなことをやるときは、スタティックリンクで測った方が良さそうです。

[編集者: すずき]
[更新: 2020年 1月 26日 17:09]
link 編集する

コメント一覧

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



link permalink

バイトをコピーする SIMD 命令

最近、見かける SIMD 命令セット(AVX も NEON も)には、レジスタ下位 [7:0] の 1バイトを、レジスタ上位 ... [31:24] [23:16] [15:8] の各バイトに配る命令が用意されています。

  • AVX: vpbroadcastb
  • NEON: dup

この命令はどういう需要があるんだろうか……?memset の実装では超役に立ちましたが、他の使い道が良くわかりません。

Facebook で上記の話をしていたところ、

  • 8bit 行列演算: 8bit 行列演算ってそんな頻出かな、って思ったら、画像使えば 8bit なので十分有り得そう。
  • バイト暗号: ブロック毎に空間変換する時とか雑に言えばスカラとベクトルの演算。

と教えてもらいました。なるほど、スカラベクトル積のスカラ側を配るときに便利ですね。

SIMD 命令のない世界

ちなみに SIMD のない処理系はどうしているのか見てみると、


int a = (何かの数字);

としたときに、


a &= 0xff;
a *= 0x01010101;

のように and, mov, mul を使っていました。もちろん、


a &= 0xff;
a |= a << 8;
a |= a << 16;

のように and, shift, or, shift, or でもできますが、今日日のプロセッサだと整数乗算の方が速そうですね。

[編集者: すずき]
[更新: 2020年 1月 26日 16:59]
link 編集する

コメント一覧

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



link もっと前
   2020年 1月 24日 -
      2020年 1月 15日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

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

最終更新: 1/26 19:04

カレンダー

<2020>
<<<01>>>
---1234
567891011
12131415161718
19202122232425
262728293031-

最近のコメント 5件

  • link 19年09月01日
    すずき 「私も正直びっくりです。間違って違う製品を...」
    (更新:09/04 23:39)
  • link 19年09月01日
    hdk 「車向けの製品の中でも、車載コンピューター...」
    (更新:09/02 23:20)
  • link 19年07月18日
    hdk 「あっ、AAMはマニュアルのオペレーション...」
    (更新:07/25 00:02)
  • link 19年07月18日
    すずき 「AAM(ASCII Adjust AX ...」
    (更新:07/24 22:22)
  • link 19年07月18日
    hdk 「加算減算は符号のありなしどちらも命令が同...」
    (更新:07/24 07:25)

最近の記事 3件

link もっとみる
  • link 20年01月26日
    すずき 「[C 言語の未定義動作と最適化] くそ長いですが、C 言語の未定義...」
    (更新:01/26 19:04)
  • link 20年01月21日
    すずき 「[glibc の memset は強かった] 目次です。ぼくの考え...」
    (更新:01/26 17:19)
  • link 20年01月12日
    すずき 「[ぼくの考えた最強の memset] 目次です。ぼくの考えた最強の...」
    (更新:01/26 17:19)

こんてんつ

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 サイトの情報