憂鬱な午後のひととき

x86/x64最適化勉強会の昔のリンク集

資料へのリンクの一覧ページを作りました. x86opti.

GMPとLLVMの比較

ようやく一通り動くようになったので速度テスト. ちなみにLLVM版は全然チューンしてないのであくまで目安. 目的はどういう傾向があるのか観察するため.

mulPreはN bit x N bit → 2N bit. _llはLLVM版. CはGMP版. montmodは2N bit → N bitのMontgomery reduction. montはN bit x Nbit → N bitのMontgomery乗算. modCはGMPのmpz_mod. mont_XはXbyakによるMontgomery乗算.

mont = mulPre + modmod.

以前も書いたようにmulPreC(=mpz_mul)はbitが大きいところでKaratsubaか何かを使ってる. 大きいところはGMPに任せてmontmodだけLLVM版を使う手がある.

mont_llとmont_Xはアルゴリズムは同一だけどbitが大きくなるとその差が大きくなる. LLVM版のregister spillのオーバーヘッドが大きいのだろう. 521bitでXbyak版の1割のオーバーヘッド600clk程度にまで出来たら理想だろう(Xbyak版も大きいところは機械的にコード生成してるので改良の余地はあるだろうけど).

VS2015のconstexpr

#include <exception>
#include <array>

constexpr int mypow(int base, int exp) noexcept
{
    return exp == 0 ? 1 : mypow(base, exp - 1) * base;
}

int main()
{
    std::array<int, mypow(5, 3)> v = { 9, 8, 7, 6, 5, 4 };
    static_assert(mypow(5, 3) == 125, "err");
    static_assert(mypow(2, 5) == 33, "err");
    printf("%d\n", v[mypow(2, 3) - 2]);
}

みたいなコードを書いてると, ビルドしてないのに二つ目のstatic_assertに波線が引かれて感動する(一つ目は成立してるので出ない). vの型もちゃんとarray<int, 125>と表示される. すごい.

ただ実行コードを見るとmypow(2, 3)のところで関数呼び出しになってる. 規格的にはありだけど, そこは定数になってほしい. コンパイル速度の低下をを恐れてデフォルトオフになってるのかなあ. 何か強制的に計算させるオプションがあるのだろうか.

第4期サイボウズ・ラボユース成果報告会

今年は@kinugawamasatoさんにアセンブラやC++の解説をしてました. みなさん, 一人で調べてどんどん作っていく. 優秀だなあ.

LLVMでMontgomery乗算

先日のx86/x64最適化勉強会には間に合わなかったけど, やっと実装した. 結局コード生成ツールに@define, @for, @ifなどの最小限の構文を持たせた.

mul.txtを食わせると展開されたLLVMコードを出力する.

どのビット長でもGMPによるmul + modよりLLVMのmontが速い. 20日の実験よりLLVMのmulとGMPのmulは384bitを越えるとGMPが速くなってる. だからそれ以上はGMPのmulに任せて2N bit → NbitだけするMontgomeryを作ったほうがよいかも(全部自分で実装するのでなければ).

Effective Modern C++勉強会#3

メモなどは明日以降にでも. 私の勘違いで時間をとってしまって@kariya_mitsuruさん担当予定だったItem 16ができなくて申し訳なかったです.

夜ご飯を食べ損ねたのと, 寝不足で辛い.

次回のEffective Modern C++勉強会#4は4/22です. よろしくお願いします.

クラウドを支えるこれからの暗号技術

紹介記事はCybozu inside out. ようやく公開にたどり着いた. 自分が高校生の時に読んだら難しいけど面白いと思いそうなものをと, 一昨年の年末から朝5時に起きて少しずつ書いていた. レビューしてくださった方々どうもありがとうございます.

実際高校生(当時中学生?)とおぼしき方もレビューをしてくださったようで目的の半分は達せられたかな. 専門家の方にとっては題材のとり方が偏ってたりおかしなところもあるかもしれないけど, 間違ってるのでない限りはご容赦ください.

そして間違ってるところはびしばし突っ込んでくださるとありがたいです.

LLVMのmulとGMPの比較

固定長サイズの教科書ライクな乗算のllを生成するスクリプトを書いてllcでasm出力したものとGMPとで比較してみる. N bit x N bitで出力は2N bit.

384bitあたりが分岐点. GMPはそこからkaratsubaに移行してるのかな.

LLVMのcarry

ここしばらくいろいろ試行錯誤したけど, やはり現時点のLLVMでcarryは扱わない方がよいコード生成になると思う. それでもいまいちなんだが.

define void @mie_fp_add64S(i64* %pz, i64* %px, i64* %py, i64* %pp) {
    %x = load i64* %px
    %y = load i64* %py
    %p = load i64* %pp
    %x1 = zext i64 %x to i128
    %y1 = zext i64 %y to i128
    %p1 = zext i64 %p to i128
    %t0 = add i128 %x1, %y1 ; x + y
    %t1 = sub i128 %t0, %p1 ; x + y - p
    %t2 = lshr i128 %t1, 64
    %t3 = trunc i128 %t2 to i1
    %t4 = select i1 %t3, i128 %t0, i128 %t1
    %t5 = trunc i128 %t4 to i64
    store i64 %t5, i64* %pz
    ret void
}

// x64
mie_fp_add64S:
    movq    (%rdx), %rax
    addq    (%rsi), %rax
    sbbq    %rdx, %rdx
    andq    $1, %rdx
    movq    %rax, %rsi
    subq    (%rcx), %rsi
    sbbq    $0, %rdx
    testb   $1, %dl       ; 減らせる
    cmovneq %rax, %rsi    ;
    movq    %rsi, (%rdi)
    retq

// aarch64
mie_fp_add64S:
    ldr  x8, [x1]
    ldr  x9, [x2]
    ldr  x10, [x3]
    adds     x8, x9, x8
    adcs    x9, xzr, xzr
    subs     x10, x8, x10
    sbcs    x9, x9, xzr
    tst  x9, #0x1                 ; 減らせる?
    csel    x8, x8, x10, ne
    str  x8, [x0]
    ret

xzrはzeroレジスタのようだ. x64よりarch64の方がいいコードが出てる気がする.

WindowsでLLVM

最適化勉強会でWindows用のasm出力をどうしたらいいのか分からないと言っていたら, LLVM-Windows-Binariesを教えていただいた. ありがとうございます.

opt -O3 t.ll -o -|llc -O3 -o t.asm -march=x86-64 -x86-asm-syntax=intel

とすると望みのものが得られた. ここのLLVMのバージョンは少し古いので勉強会でどなたか仰っていたように自分でbuildすればよいようだ.

Linux上で-marchを変えると他のアーキテクチャのも出力されるのでこのオプションでWindows用のも出るのだと思い込んでいた. そもそも実行バイナリを変えないといけなかったのか.

x86/x64最適化勉強会7

久々の開催です. なんと前回から1年半振り. 今回は結構前から準備していたのだけどLLVMに苦しめられて結局資料を作り始めたのが前日の夜11時. 資料が出来上がったのがそのまま朝の5時半. 少しだけ寝て資料を修正していざ秋葉原へ. 30分前に着いたのだけど間違えてダイビルに行ってしまう(頭動いてない). UDXに行ったが今度は入り口を間違えて会議室にたどり着けない(いつものことだが).

中身についてはx86/x64最適化勉強会7レポートをでごらんください. @tanakmuraさんの発表はすごくて感動してました. 後半は暗号の学会SCIS2015で実装系の発表をされていた方に無茶なお願いしていろいろお話を伺えました. ありがとうございます.

今回は久しぶりに首藤さんが参加してくださって鋭いつっこみを沢山してくださいました. Shudo's Noteではメモも公開されています.

毎回@kzmogiさんにすばらしい会場を提供していただいて本当にありがたいです. ありがとうございます. 今回は後輩の方にも会場準備を手伝っていただいたそうで申し訳ないです.

#過去のustreamがサーバから消えてしまっていますが手元には保存しています.
#最近CMが長いんですね….