憂鬱な午後のひととき

Montgomery乗算

GMP版, mpn_add_nを使っていた部分をmpn_add_nとmpn_add_1に分けたら少し速くなった. mpn_add_1はマクロで書かれていてinline展開されるのか(差分).

LLVM版も用意してみる.

Montogomery乗算

しつこく測定. 教科書的なz = mont(x, y)を乗算(mul)してからreduction(red)すると一時領域が増えて少しオーバーヘッドがある. ただbit長が大きくなるとmulはKaratsubaが使えるので高速化できる.

768bit以上は効果があるかなと思ったけど駄目だった. もう少しredをがんばれば逆転するかもしれないが. LLVMはbitが大きいと加算自体がしょぼくなるのでそのせいかもしれない.

Skylake 3.4GHzでの結果.

ランニングシューズ

20カ月履いて大分へたって来たので新しいのを買う. 重心を調べてもらうと左かかとによっていて, 中敷きを入れた方がよいと言われたので勧められるままに購入. バランスよくなるかなあ.

『東京番外地』(森達也)

普段いかない, それどころか意識しない施設をめぐる. なんだか落ち着かない.

著者は監視カメラが常態化される社会が人の心に与える影響を危惧する.

日本弁護士連合会の監視カメラに対する法的規制に関する意見書によると防犯の効果は限定的だし, 昔のクローズアップ現代には防犯カメラの落とし穴　～相次ぐ誤認逮捕～という回もあった.

「守り」から「攻め」に変化する監視カメラ、その展望と課題も, うがってみれば, 役に立ってないから金儲け(=マーケティングツール)に使おうと言ってるのかも.

先日の討論会では「健康ゴールド免許」の問題点をあげる人がいた. 次はなしくずし的にライフログをとられる社会が来るのだろうか.

【公開討論会】越境データ問題について

最近秘匿計算やプライバシー保護の勉強していたのでいろいろ参考になった. 使いどころが不明確になった法律はいろいろ危ない. 改定前はちゃんと書かれていたのになぜ消したのだろう.

Re:Karatsuba

ようやくベンチマークとれた.

N = 4, 6, 8, 10は64 * N bit乗算で128 * N bit出力を意味する. gmpはmpn_mul_n, llvmはLLVM bitコードを用いたもの, gmp-k, llvm-kはそのKaratsuba版.

GMPも内部でkaratsubaを使っているので外側でCで書いたkaratsubaを使ってるgmp-kは当然遅くなる. llvmはずっと教科書乗算なのでO(N²)で大きくなる. N = 4のときは手書きasmとほぼ同じ速度. ただレジスタに乗らなくなるとLLVMの最適化がしょぼいのでそれより遅くなってる.

N = 8以上だとllvm-kが一番速いがN = 6(384ビット乗算)のときは使わない方がよさそうだな.

奇数とsqrについても測定しよう.

Karatsuba

fp_proto.hpp. ビット長が長めのときだけやりつつ, GMP/LLVMを切り替えられるように汎用に. まだ少し試行錯誤中.

『絵でわかるロボットのしくみ』(瀬戸文美)

意外ときちんと解説されていて面白かった. 最後は日本のロボット開発チームShaftに期待が寄せられていた(出版は2013年).

結局, 国内では投資を受けられずGoogleに買収されたのが, もの悲しい.

今年に入ってトヨタが買収するかもという話があったようだがどうなってるのかな.

CODE BLUE 2日目

名刺をちょっとしか持ってきていなかったのが痛い. 地デジDVB-T受信機のハッキングをしゃべってる人が楽しそうだった.

CODE BLUE 2016参加

去年は発表者で参加したけど今年は聞くだけなのでのんびりと. 去年と所属が変わってる人が結構いる. いろいろお話できてよかった.

String Labs

VSSつきBLS署名の実装を言われるままに作っていたら, なりゆきでTEAMに入ってる.

ELFバイナリのシンボルを分離したりくっつけたりする方法

まず適当にC/C++ソースを-gオプションをつけてコンパイルし, a.outを作っておく.

a.outからdebug情報を取り出すにはobjcopyを使う.

objcopy --only-keep-debug a.out a.debug
cp a.out a.stripped
strip -s a.stripped

これでa.outをa.stripped(stripされた実行ファイル)とa.debug(シンボルファイル)に分けられる.

もちろんgdbで単にa.strippedを読むだけではシンボルは見えない.

gdbのsymbol-fileコマンドを使うとシンボルを読み込める.

gdb ./a.stripped
...
// シンボルがないのでmainが見つからない
Reading symbols from ./a.stripped...(no debugging symbols found)...done.
(gdb) b main
Function "main" not defined.

// シンボルを読み込む
symbol-file a.debug
Reading symbols from a.debug...done.
(gdb) b main
Breakpoint 1 at 0x40089a: file t.cpp, line 6.

実は, 実行ファイルに分離したシンボルファイルを設定できる. こうすればgdbは自動的にシンボルを読みに行く. 設定するにはobjcopyで.gnu_debuglinkセクションを作る.

cp a.stripped a.linked
objcopy --add-gnu-debuglink=a.debug a.linked
gdb ./a.linked
Reading symbols from ./a.linked...Reading symbols from /home/herumi/a.debug...done.

さて, ubuntuでは分離されたシンボルファイルは/usr/lib/debug/.build-id/<XX>/<YY..ZZ>.debug という名前で保存されている. ここでXX YY..ZZは実行ファイルのBuild IDを表す.

Build IDはreadelf -nで取得できる.

% readelf -n a.out

Displaying notes found at file offset 0x00000254 with length 0x00000020:
  Owner                 Data size       Description
  GNU                  0x00000010       NT_GNU_ABI_TAG (ABI version tag)
    OS: Linux, ABI: 2.6.24

Displaying notes found at file offset 0x00000274 with length 0x00000024:
  Owner                 Data size       Description
  GNU                  0x00000014       NT_GNU_BUILD_ID (unique build ID bitstring)
    Build ID: 43da1d48d450a937cd52b1a18344c7040bb923b8

この場合は/usr/lib/debug/.build-id/43/da1d48d450a937cd52b1a18344c7040bb923b8.debugという名前になる.

stripされた実行ファイルと分離されたdebugファイルをくっつけるにはどうするか. 少し調べた限りではobjcopyではできなさそうだった(ご存じの方, 教えてください).

探してみるとelfutilsというツールがあった. apt install elfutilsで入る. この中にあるeu-unstripを使うとくっつけられた.

eu-unstrip <exe> <debug>

くっついたファイルは<debug>という名前になるので注意(逆にしてほしい).

実はubuntuのパッケージではdebugシンボルは圧縮されている. ツールによってはそういうシンボルは読めないことがあるのでくっつける前に展開する必要がある.

objcopyの--decompress-debug-sectionsを使えばよい. 圧縮するには--compress-debug-sectionを使う.

実行バイナリの.gnu_debuglinkにはdebugファイルのCRCが入っているのでdebugファイルを変更する場合は一度削除してつけなおす必要がある.

./a.out ; シンボルつき実行ファイル
addr2line -e ./a.out 40089a
/home/herumi/t.cpp:6 ; 正しく表示される

; 圧縮シンボルファイルを作る
objcopy --compress-debug-sections --only-keep-debug a.out a.debug

; a.outをstripするとaddr2lineは正しく表示しない
strip -s a.out
addr2line -e ./a.out 40089a
??:0

; a.outに圧縮シンボルファイルを指定すると正しく動かない

objcopy --add-gnu-debuglink=a.debug a.out
addr2line -e ./a.out 40089a
BFD: Dwarf Error: found dwarf version '0', this reader only handles version 2, 3 and 4 information.

; 圧縮シンボルファイルを展開するがまだ動かない
objcopy --decompress-debug-section a.debug
addr2line -e ./a.out 40089a
??:0

; 一度.gnu_debuglinkセクションを削除してつけなおすと正しく動く
objcopy -R .gnu_debuglink a.out
objcopy --add-gnu-debuglink=a.debug a.out
addr2line -e ./a.out 40089a
/home/herumi/t.cpp:6

mod pにおけるaddとsub

(x - y) mod pはadd, subをcarryを返す関数として

if (sub(z, x, y)) {
  add(z, z, p); // x < yになったらpを足す
}

でよいが(x + y) mod pは

if (add(z, x, y)) {
  sub(z, z, p); // x + yがcarryならpを引く
  return;
}
if (sub(tmp, z, p)) {
  return; // z < pなら何もしない
}
z = tmp; // z >= pならtmpをコピー

とかなりややこしい. 昔からこれなんとかならんのかと思っていろいろやってるけどうまくいかない. add(x, y, p) = sub(x, p - y, p)とすれば分岐は減るがコピーじゃなくてsubになる. なんでaddとsubで非対称なんだろう.

assume文

コンパイラに最適化のヒントを与えるためのもの. Visual Studioには10年以上前から__assumeというのがあって, これが欲しいもの. ただ残念ながらなかなか期待通りの最適化はしてくれない.

ClangにはVSのをまねたbuiltin-assumeというのが入ってきてる. こちらはよい感じ. たとえば

int f(int n)
{
    return n / 2;
}

nが正または0だと分かっていれば単に算術シフトするだけ. だけど負の数を2で割るときは奇数なら1を足さないといけない. で,

f():
  mov    eax,edi
  shr    eax,31
  lea    eax,[rax+rdi]
  sar    eax,1
  ret

こんな感じのコードになってしまう. だからnが非負だと分かっていればintじゃなくてunsigned intを使うべき. ところが__builtin_assumeを使って

int g(int n)
{
    __builtin_assume(n >= 0);
    return n / 2;
}

 shr    edi,1
 mov    eax,edi
 ret

というコード生成をしてくれる.

C++の規格に「Generalized Dynamic Assumptions」というのが提案されたけど残念ながらrejectでした. 「契約」という形で入るのは当分先ですかね.

『データ解析におけるプライバシー保護』(佐久間淳)

差分プライバシーのあたりを読んでる. まだ新しいせいか, いろいろ表現がこなれてなかったり間違ってたりする. そのうちまとめて指摘するか.

情報幾何学の基礎 輪読会参加

5.2節. 計算が辛かった.

PVS-Studio

いろいろ試してるけどかなりよい. 自分が書いたコードで見つかったのは今のところ一つだけだが, 他の人が書いた少し大きめのものだとぽつぽつとバグが見つかる. Linuxでも動くらしいのでこちらも試したいが, バイナリがどこにあるのか分からない...

ディープラーニングを用いたコンピュータ囲碁 –Alpha Go の技術と展望–

コンピュータAIの歴史の話は面白かったけど, 主題はもう少しつっこんだものを期待した.

『「分かりやすい表現」の技術―意図を正しく伝えるための16のルール』(藤沢晃治)

久しぶりに読み直してみた.

『数学セミナー 測度とは何か』2016年10月号

何度か読み返してみたが, 「ZFC + 強到達不可能基数の存在」と「ZF + 従属選択公理 + 実数の全ての集合がルベーグ可測」の公理の同値性のあたりから巨大基数に入ってくると何を言ってるのか分からなかった.

よく分からないけどとても難しいらしいということだけ分かった.

mclの関数切り替え部分

いろいろ試してtemplateの構造体でLLVMとGMPの関数の特殊化を用意して切り替えるのが一番効率がよいことが分かった. それで進める.

『赤めだか』(立川談春)

談志がしばらく考えてから談春に落語のやりかたやその他の考え方を説明する部分がすばらしい. 何のために, どうすべきなのかがきちんと述べられている.

『雨ン中の、らくだ』(立川志らく)よりこちらのほうが読みやすかった.