melancholic afternoon

ようやく一通りHaswellの命令に対応した. これからリファクタリングしないといけないがテストは一通り通ってる. gather命令はやはりうっとうしかった.

浮動小数点数用vgather
	data size	addr size
vgatherdps	4	4
vgatherdpd	8	4
vgatherqps	4	8
vgatherqpd	8	8

整数用vgather
	data size	addr size
vpgatherdd	4	4
vpgatherdq	8	4
vpgatherqd	4	8
vpgatherqq	8	8

命令が8種類あって, しかもそれぞれのAVX2版の引数のとり方がYMM/VM32X/YMM, YMM/VM32Y/YMM, XMM/VM32Y/XMMの3通りのどれか. あと, xmm4やymm4のときだけespがindexレジスタに相当するので例外処理が必要という.

どれぐらいややこしいかというと, NASMやMASMもバグってた. 今回はgit format-patchを使って報告. 使うのは当分先かと思ってたらすぐだった. NASMって歴史があるわりには信頼性低いよな. MASMのバグは

vgatherqpd ymm4, [ymm4], ymm7

がコンパイルエラーになるというもの.

追加していた思ったのだけどXbyak::Reg32eというクラス設計は明らかにおかしい. 今更ながらなんでこんな作りにしたんだろう. VSIBを統合したいが若干後方互換性を壊さざるを得ないなあ.

AVX2対応続き

汎用整数演算命令, SIMD整数, SIMD浮動小数点数命令の対応ができた. 残るはgather関係. これはちょっと面倒そうだ. 終わったらリファクタリングしよう. Haswell New Instruction Descriptions Now Available!ではAVX2対応命令一覧の中にvphminposuwが入ってるけど対応してないよね. Instruction Set Extensions Programming ReferenceのvphminposuwではAVX2非サポートとあるから単なるミスかな(古い記事だし).

おっと, vperm系もあった.

nasmのvpmovsxbd命令のバグ修正

Xbyakの命令追加時にNASMやYASMの出力と比較してテストしてると, 結構NASMのバグが見つかる(YASMやMASMのバグもあった). 面倒なのでほっとくことも多かったが(手元でだけ修正とか), せっかくなのでバグ報告してみた.

以前別のパッチを送ったときは署名をつけてと言われたので, 今回はつけたのだけど, 代わりにgit format-patchを使ってくれと言われた. すんません. めったに使わないのですぐ忘れてしまうのでメモ. -sでSigned-off-byが入る. って, kernel patch作ったときもメモしてたのだが.

git format-patch -s master

「The Five-Card Trick Can Be Done with Four Cards」(T. Mizuki, M. Kumamoto, H. Sone)

ISECの招待講演の一つ, ASIACRYPT2012で発表されたもの.

AliceとBobが0か1を秘密に持つ. 二人の論理積(and)を, 互いに自分の値を知らせることなく計算せよ. ただし使えるのは3枚の黒と2枚の赤のカード(裏は区別がつかない)5枚だけ.

もちろん結果が1だったら二人とも1だったのはわかるけど, 0だったときに相手が0と1のどちらかだったか分からないようにするということ.

という問題の回答をFive-Card Trickというらしい. そしてそれは実は2枚の黒と2枚の赤のカードでできるよというもの.

全く予備知識がなくても理解できるとても楽しい問題(そして答えも小学生でも理解できる). 論文でも♡(ハート)や♧(クラブ)の記号が目立つ. へぇ, こんなパズルも暗号のトップカンファレンスに載るんだなあ.

Haswellの整数系命令

bextr, bzhi, sarx, shlx, shrx, blsi, blsr, lzcnt, tzcnt, rdrand, rorxを追加. これで一通り. rdrandはIvy Bridgeで既に入ってる. fsやgsにアクセスする専用命令も増えてるんだなあ(対応しないけど). 次はメインのAVX2系だ.

Haswellの多倍長演算命令

Haswellに向けてぼちぼちXbyakに新しいinstructionを追加し始めて気がついたのだけど, 新命令一覧の中に前回の最適化勉強会のときに話したadcxやadoxが無い.

New Instructions Supporting Large Integer Arithmetic on Intel Architectureにはそれらのintrinsic関数まで紹介されてるからてっきりはいってるのだと勘違いした. carryを変更しないmulxはHaswellからある.

『古代ローマ人の24時間』(アルベルト・アンジェラ関口英子訳)

紀元115年, ローマを1日ぶらっと散策したらどんな光景がみられるだろうという視点で書かれている. 非常に映像的で楽しい. 建て増しされた6, 7階の建物がところせましと並ぶ集合住宅のインスラや超巨大な闘技場や公衆浴場. よくそんなものが作れたなあと.

ローマ人の男性の平均身長は165cmで結構低いというのも知らなかった. 少し前に映画の「テルマエ・ロマエ」を見たので, それと比較しながら見るとより親しみやすい.

難点は地図が一つも無いこと. 作中どういうところに行ったのかとか, どの場所に何があるのかが全然分からないので困ってしまう.

多様な働き方

なぜサイボウズは、働く「時間」と「場所」の制約をなくせたのか？<前編>
育児休業「男女で３年」では

育児休業の制度があっても、それを取得する風土がなければ無駄な制度になります。風土は経営者が作るものです
男性勝りの働き方をする女性を昇進させる例がありますが、そういう働き方をしなさいというメッセージになってしまいます

なるほどなあ. 内部にいるとそんなものかと思うことも, トップの対外的な発言を見ると改めて社内の風土が分かる.

在宅勤務は去年末ぐらいから, 月4回までという制約が外されたウルトラワークというスタイルが試験運用されている. 休むほどじゃあないのだけど, ちょっとだけ用事があるとか, しんどくて満員電車に揺られるのが嫌だなあというとき丸一日休まなくてもよいのでありがたい.

# 結果的に, 電車の中での読書時間が減るというのが難点だが(^^;

育自分休暇制度 : 社員には「これでサイボウズを辞めやすくなりました。」と嬉しいのか悲しいのかわからないことを言われているという。 cf. 「育自分休暇制度」で海外ボランティアへ
副業も許可 : サイボウズが潰れたときには、それぞれの所に転職してもらえるかもしれませんし（笑）。

こんなことも書いてる. ええのか.

GMPの16進数入力

出力をやったので今度は入力. ただこちらはGMPも結構速かった. とはいえ, string → mpz_class → 固定配列 → Montgomery変換という流れでmpz_classを経由しないようにしたら2～4倍は速くなった. Montgomery変換が入るのでその分だけはGMPに勝てない(16進数出力の場合はそのハンディを加味しても勝っていた).

GMPの16進数出力

内部的には64bit(あるいは32bit)進数として保持してるのだから高速だろうと思っていたけどベンチマークをとってみたら意外と遅かった. 任意進数に対応しているため毎回割り算をしてるのかな. 16進数専用ルーチンとか用意しているかと思ってたけどそうでも無いみたい.

多少多めの16進数出力をすることがあったのでFpクラスやMontFpクラスでは専用ルーチンを用意した.

素朴なC++関数だけどもGMPのそれより5～6倍は速い.

Montgomery乗算

内部でMontgomery乗算を使う有限体のクラスがそこそこ動くようになったのだけど, なんかたまにテストに失敗する. 何かなあと思ったら素数pの長さが64の倍数だったときだけたまにおかしくなるようだ.

調べたらたとえばpが256bit素数のときは計算途中で321bitになることがあるのだった. 320bitしか用意していなかったのでたまにおかしくなっていた. もともと今回流用したもとのate-pairingの実装で使っていたやつは素数が254bitで, 絶対に320bitで収まることを仮定した最適化をしていたのを忘れていた.

というわけでfullBitのときだけ最後のcarryを扱うコードを生成するように修正したら, テストがパスするようになった.

「壊れゆく日本という国」(内田樹)

朝日新聞5/8の寄稿. 国民国家(生活や文化を共有する集団がそこに帰属意識をもっている共同体とその政府)という形態は約400年続いている政治の基本単位だそうな. それが今, グローバル企業によって破壊されつつある. グローバル企業は利益の最大をはかるために一つの国の事情なんてしったこっちゃないから.

著者はグローバル企業が「悪い」とは言っていないが, 合理化の際のコストを国家に押しつけるのはやめろと主張する.

たとえばコスト削減のために原発が必要とは言うが, 除染作業のためのコストは払わない. もしまた問題が出たら日本から出て行くだけ. 大学に対して英語ができて交渉力もあって即戦力になる人材を育てよというのは自分のところで人材育成コストを払いたくないから.

いくら働いても年収100万だったり, 過労で倒れたり鬱になる人を「個人の問題」と切り捨てるのも同類なんだろう. 企業はコストダウンになるが, その人たちの生活保護費や医療費の負担は国がするのだから.

一番の問題は政府がそれに同調していることで, メディアもそれを無批判に垂れ流しすることに驚愕するという.

なるほど, だから国も生活保護費を減らし, まるで江戸時代の五人組のような相互監視制度を取り入れ, ナショナリズムを亢進するのか.

「無批判に垂れ流すメディア」といえば, これとは別の件だがPC遠隔操作で逮捕された容疑者を4度連続逮捕してるのもどうかと思う. 「取り調べの可視化」や「冤罪」にはやたら声が大きいのに, これに関して批判的な記事はあまりみられない.

@takehiro_tさんのx86判っている人ほどはまるARM

3月末に開催したx86/x64最適化勉強会5のときの資料がアップされたらしい.

Haskellで計算機代数勉強会

グレブナー基底の話が多そうだったので参加. きれいになった武蔵小杉は初めて. 立体構造がよくわからん.

@mr_konnさんの基本的な部分のサーベイはなかなかよかったと思う. @ikegami__さんのグレブナー基底の応用の小ネタ集も面白い. 初等幾何の自動証明が全然自動じゃないとか.

@masahiro_sakaiさんの代数的実数の話もよかった. 実閉体の方は疲れて半分寝てしまった. m(__)m

懇親会も参加してみたかったけど眠かったので帰宅.

ハッカソンというわけじゃないけど聞きながら有限体の実装をちまちまとしてた(mont_fp.hpp). 160～192bitあたりの素数のFpの加減乗算までできた. ざっくりベンチでGMPの4倍ぐらい速い. クラス設計をどうするか悩み中なのでがらっと変わるかも.

Xbyak::util::Packクラス

FpGeneratorを書きやすくするために試行錯誤中. コード中に192bitや256bitのレジスタをひとまとまりにして扱いたいときに, どうするか考えて作ってみた.

今までは256bit固定だったので愚直に使いたいレジスタを4個並べていたのだけど長さが可変長になると扱いにくい.

// [z3:z2:z1:z0] += [x3:x2:x1:x0]
void add4_rr(const Reg64& z3, const Reg64& z2, const Reg64& z1, const Reg64& z0,
    const Reg64& x3, const Reg64& x2, const Reg64& x1, const Reg64& x0)
{
    add(z0, x0);
    adc(z1, x1);
    adc(z2, x2);
    adc(z3, x3);
}
// [z2:z1:z0] += [x2:x1:x0]
void add3_rr(const Reg64& z2, const Reg64& z1, const Reg64& z0,
    const Reg64& x2, const Reg64& x1, const Reg64& x0)
{
    add(z0, x0);
    adc(z1, x1);
    adc(z2, x2);
}

みたいになってしまった. subやstoreなどそれぞれ作ると大変. Packを使うと

// z[] += x[]
void add_rr(const Pack& z, const Pack& x)
{
    add(z[0], x[0]);
    assert(z.size() == x.size());
    for (size_t i = 1, n = z.size(); i < n; i++) {
        adc(z[i], x[i]);
    }
}

と書いて

add_rr(Pack(z3, z2, z1, z0), Pack(x3, x2, x1, x0));
add_rr(Pack(z2, z1, z0), Pack(x2, x1, x0));

などとできるようになった. すっきり.

FpGenerator

pが160か192か256ビット程度の素数でよいので, そこそこ速いFpが欲しいなと思っていて作り始めてる.

たとえば128bitの素数を渡すと次のFp上の加算関数が生成される.

  //              rcx                 rdx                  r8
  // add(uint64_t *pz, const uint64_t *px, const uint64_t *py);
  sub   rsp,18h
  mov   rax,qword [rdx]
  add   rax,qword [r8]
  mov   qword [rcx],rax
  mov   rax,qword [rdx+8]
  adc   rax,qword [r8+8]
  mov   qword [rcx+8],rax
  mov   rdx,30F7D0h     ; pointer to p
  mov   rax,qword [rcx]
  sub   rax,qword [rdx]
  mov   qword [rsp],rax
  mov   rax,qword [rcx+8]
  sbb   rax,qword [rdx+8]
  mov   qword [rsp+8],rax
  jb    .exit
  mov   rax,qword [rsp]
  mov   qword [rcx],rax
  mov   rax,qword [rsp+8]
  mov   qword [rcx+8],rax
.exit:
  add   rsp,18h
  ret

メモリに書かずにレジスタをうまく使い回すとかいろいろあるけどそれは徐々につけていこう.

「こういうのするなら今どきLLVMだろー」という声が聞こえてきそうだが, x86/x64最適化勉強会5の発表のときにいろいろ調べてみて, 現状ではLLVMは不向きと分かったので心置きなく(?)Xbyakを使える.

Montgomery乗算もできるだけ汎用ロジックで生成させようと思ったけどメモリアクセスが増えすぎそうに思ってやめた. とりあえず256bitについてはate-pairingを実装したやつを流用して192bitはそれをシュリンクした. GMPのmpz_classで掛けて剰余をとるよりも4倍ぐらい速い感じ.

pの長さに応じた専用の関数を作らざるを得ないけどまあ, たいした量でもないし, ここが遅いと話にならないのでそれぞれに用意する(うまい方法が見つかればできるだけ汎用的な形にしたいが).

ちまちまと作ってるのは日曜大工みたいで楽しい. Haswellが出たらもっと簡潔にかけるはずなのでそれまでに新命令にも対応しとかなきゃなあ.

憂鬱な午後のひととき