コグノスケ


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

link もっと前
2020年1月8日 >>> 2020年1月21日
link もっと後

2020年1月11日

memsetに一番効く最適化

目次: ベンチマーク

Cortex-A72でのmemsetはO2に-ftree-vectorizeと -fpeel-loopsを足すと、O3の性能とほぼイコールになることがわかりました。


gcc -O2 -ftree-vectorize -fpeel-loops -fno-builtinの測定結果(Cortex-A72)

元の処理が非常に単純なループ処理のためか、ループ系の最適化がメチャクチャ効くっぽいです。

何が効くのか?

GCCのGIMPLEを出力させ(-fdump-tree-all)眺めてみると、

オリジナル
1バイトごとにデータ処理するループが生成される。
ベクタライズ(161t.vect)
16バイトごとにデータ処理するループと、1バイトごとに残りデータを処理するループに分割される。
アンローリング(164t.cunroll, 169t.loopdone)
残りデータを処理するループが展開される。

こんな感じに見えます。正直言って、ループアンローリングなんて大したことないと思っていましたが、これほど効くとは思いませんでした。

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

編集者:すずき(2023/09/24 08:55)

コメント一覧

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



2020年1月12日

ぼくの考えた最強のmemset

目次: ベンチマーク

NEON intrinsicを使って自分でmemsetを実装してみました。ざっくりした設計方針としては、

  • NEON store (128bit) x 2で32バイトずつ書く
  • 端数25〜バイトはNEON store x 2
  • 端数16〜バイトはNEON store + uint64 store

相手は汎用実装ですし、Cortex-A72に特化した実装なら楽勝だろう、などと考えて始めましたが、甘かった。glibcのフルアセンブラ版はかなり手ごわいです。


自作memsetの測定結果(Cortex-A72)

グラフの赤い線が、自作したmemsetの性能です。

最適化レベルO3のsimple memsetにはほぼ全域で勝てますが、サイズが小さいときのmuslは強い(サイズが小さい場合から判定しているから?)です。glibcのフルアセンブラもかなり強いです。測定によって勝ったり負けたりな程度です。

全然最強じゃなかった……

設計が甘すぎたことがわかったので、下記のように見直しました。

  • 少ないバイト数の条件から判定
  • NEON store (128bit) x 2で32バイトずつ書く
  • 端数バイトはNEON store(分岐を減らした)

序盤でmusl memsetに負けていたのは、バイト数の条件判定の順序が良くなかった(大きいサイズから判定していた)ためなので、1番目で対策しています。2番目と3番目の方針は良いとも悪いとも一概に言えませんが、RK3399だとこれが一番性能が出ました。


自作memset改善後の測定結果(Cortex-A72)

設計意図通りにmuslの序盤(特に高速な1〜8バイト付近)と、glibcフルアセンブラの序盤(1〜32バイト)には勝てたものの、glibcフルアセンブラ版は中盤以降が強く、33バイト以降は全く勝てません。

私の作ったmemsetは32バイトまでは専用処理で、33バイトからループで処理するようになるので、33バイトから性能がかなり落ちます。

おそらくglibcフルアセンブラ版も同様に16バイトから性能が落ちるので、ループ処理していると思うんですが、それ以降の巻き返しが凄くて、33バイト以降はまったく勝てないですね……。どうやってんだろうね、これ?

コンパイラが変なandとかsubを出力しているのを見つけたので、アセンブラでも実装してみましたが、性能はほぼ変わりませんでした。設計の根底が違うんでしょうね。

Cortex-A53だと全く勝ち目無し

RK3328(Cortex-A53)で測ってみると、muslには勝てますが、glibcフルアセンブラ版には勝ち目無しで、ほぼ全域に渡ってボコボコにされます。


自作memset改善後の測定結果(Cortex-A53)

基本設計が「余計なwriteをしてでも、とにかく速く終われ」なので、writeを正直に実行してしまうようなヘボいプロセッサになればなるほど勝ち目が薄いです。

編集者:すずき(2023/09/24 08:55)

コメント一覧

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



2020年1月19日

バイトをコピーする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でもできますが、今日日のプロセッサだと整数乗算の方が速そうですね。

編集者:すずき(2023/09/24 08:55)

コメント一覧

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



2020年1月20日

glibcのmemsetのクセ

目次: ベンチマーク

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

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

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

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

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

編集者:すずき(2023/09/24 08:55)

コメント一覧

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



2020年1月21日

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命令を使います。コンパイラ侮りがたし。

編集者:すずき(2023/09/24 08:55)

コメント一覧

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



link もっと前
2020年1月8日 >>> 2020年1月21日
link もっと後

管理用メニュー

link 記事を新規作成

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

最近のコメント5件

  • link 24年10月1日
    すずきさん (10/06 03:41)
    「xrdpで十分動作しているので、Wayl...」
  • link 24年10月1日
    hdkさん (10/03 19:05)
    「GNOMEをお使いでしたら今はWayla...」
  • link 24年10月1日
    すずきさん (10/03 10:12)
    「私は逆にVNCサーバーに繋ぐ使い方をした...」
  • link 24年10月1日
    hdkさん (10/03 08:30)
    「おー、面白いですね。xrdpはすでに立ち...」
  • link 14年6月13日
    2048player...さん (09/26 01:04)
    「最後に、この式を出すのに紙4枚(A4)も...」

最近の記事3件

  • link 24年10月28日
    すずき (10/30 23:49)
    「[Linuxからリモートデスクトップ] 目次: Linux開発用のLinuxマシンの画面を見るにはいろいろな手段がありますが、...」
  • link 23年4月10日
    すずき (10/30 23:46)
    「[Linux - まとめリンク] 目次: Linux関係の深いまとめリンク。目次: RISC-V目次: ROCK64/ROCK...」
  • link 24年10月24日
    すずき (10/25 02:35)
    「[ONKYOからM-AUDIOのUSB DACへ] 目次: PCかれこれ10年以上(2013年3月16日の日記参照)活躍してく...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
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 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

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

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 10/30 23:49