憂鬱な午後のひととき
LLVM
久しぶりにLLVMでコードを書いてみる.
LLVMならx86/x64/armに対応できるかなと思ったけどVisual Studio用x64コードは生成できないのか.
残念. VCだけ別に書く? どうしよう.
とりあえずp = (1 << 192) - (1 << 64) - 1のときの384bit→192bit剰余算を書いてみる.
384bitのxをx = [H:L]とする. H, Lはそれぞれ192bit.
H = [H2:H1:H0]とする. Hiは64bit.
(1 << 192) % p = (1 << 64) + 1だから
mod pで
x = L + (H << 192)
= L + H + (H << 64)
= L + H + [H2:H1:H0:0]
= L + H + [H1:H0:0] + (H2 << 192)
= L + H + [H1:H0:0] + H2 + (H2 << 64)
[e:x] = L + H + [H1:H0:H2] + [H2:0] ; 2bit(e) over
= x + e + (e << 64)
あってるのかな, これ.
とりあえず昔自分が書いたllvm入門を眺めながら試してみる.
carry操作を避けるためにLLVMが持つ192bit整数などにどっぷり依存する戦略.
上の式で一時的に192 + 2bitまで増えるので変数をi194にゼロ拡張する.
define void @modp192(i64* %px) {
entry:
; pxを192bit整数へのポインタにキャスト
%pL = bitcast i64* %px to i192*
; &px[3]を192bit整数へのポインタにキャスト
%pH64 = getelementptr i64* %px, i64 3
%pH = bitcast i64* %pH64 to i192*
; LやHを192bit整数として読み込む
%L192 = load i192* %pL
%H192 = load i192* %pH
; その後194bit整数にゼロ拡張する
%L = zext i192 %L192 to i194
%H = zext i192 %H192 to i194
; t1 = L + H
%t1 = add i194 %L, %H ; %t1 = L + H
%px3 = getelementptr i64* %px, i64 3
%px4 = getelementptr i64* %px, i64 4
%px5 = getelementptr i64* %px, i64 5
; 64bit整数H0, H1, H2を読み込む
%H0_ = load i64* %px3
%H1_ = load i64* %px4
%H2_ = load i64* %px5
; 194bit整数にゼロ拡張して
%H0 = zext i64 %H0_ to i194
%H1 = zext i64 %H1_ to i194
%H2 = zext i64 %H2_ to i194
%H0_1 = shl i194 %H0, 64
%H1_1 = shl i194 %H1, 128
%H10 = or i194 %H1_1, %H0_1
; H102 = [H1:H0:H2]を作る
%H102 = or i194 %H10, %H2 ; [H1:H0:H2]
; %t2 = L + H + [H1:H0:H2]
%t2 = add i194 %t1, %H102
; (H2 << 64)を作ってt2に加える
%H2_1 = shl i194 %H2, 64
; %t3 = L + H + [H1:H0:H2] + [H2:0]
%t3 = add i194 %t2, %H2_1
; t3の上位2bitを取り出すために192bit右シフトする
%e = lshr i194 %t3, 192
; それを64bit左シフトして足す
%e64 = shl i194 %e, 64
%t4 = add i194 %t3, %e
%t5 = add i194 %t4, %e64 ; t3 + e + (e << 64)
; t5は実質192bitになったので194bitから192bitにキャストする
%t6 = trunc i194 %t5 to i192
; 元の場所にかき込む
store i192 %t6, i192* %pL
ret void
}
結構長くなってしまった. やりたいことに対して型情報を冗長に書かないといけないのが苦痛.
AやBがi192で定義してるのだからor i192 A, Bでなくてor A, Bでいいだろうみたいな.
llcでネイティブコードを生成する.
; llc-3.5 -o - modp.ll -x86-asm-syntax=intel
modp192:
mov rax, qword ptr [rdi + 8] ; L1
mov rcx, qword ptr [rdi + 16] ; L2
mov r8, qword ptr [rdi + 24] ; H0
mov rsi, qword ptr [rdi] ; L0
add rsi, r8
mov r9, qword ptr [rdi + 32] ; H1
adc rax, r9
mov r10, qword ptr [rdi + 40] ; H2
adc rcx, r10
sbb rdx, rdx
and rdx, 1
add rsi, r10
adc rax, r8
adc rcx, r9
adc rdx, 0
add rax, r10
adc rcx, 0
adc rdx, 0
and rdx, 3 ; ***
add rsi, rdx
adc rax, 0
adc rcx, 0
add rax, rdx
adc rcx, 0
mov qword ptr [rdi], rsi
mov qword ptr [rdi + 8], rax
mov qword ptr [rdi + 16], rcx
ret
おお, かなり優秀だ.
64bitシフトなどは全てレジスタ移動ですませている(そうなっていることを期待してコードを書いた).
ただよく見ると***の部分が冗長だな. 194bitじゃなくて256bitにすればいいのかな.
→ そうだった. i194をi256に変えれば***は無くなった.
理想的なコード生成だ.
試しに-march=x86を付けてみると4-byte Spillや4-byte Folded Reloadが結構入った.
これが絶対必要なのかうまくやればいいのかは調べていない.
-march=aarch64だと
modpP192:
ldr x1, [x0]
ldr x2, [x0, #8]
ldr x3, [x0, #16]
ldr x4, [x0, #24]
ldr x5, [x0, #32]
ldr x6, [x0, #40]
adds x1, x1, x4
adcs x2, x2, x5
adcs x3, x3, x6
adcs x7, xzr, xzr
adds x1, x1, x6
adcs x2, x2, x4
adcs x3, x3, x5
adcs x4, x7, xzr
adds x2, x2, x6
adcs x3, x3, xzr
adcs x4, x4, xzr
adds x1, x1, x4
adcs x2, x2, xzr
adcs x3, x3, xzr
adds x2, x2, x4
adcs x3, x3, xzr
str x1, [x0]
str x2, [x0, #8]
str x3, [x0, #16]
ret
ARM64のことは知らないけどx64にほぼ対応して最小のadd回数なので問題なさそう.
-march=armだとx86ほどではないけどSpillやReloadが発生した.
x64やarmのタイトなコード生成から想像するとそれらは必要なものなのかな.
ここまでくるとVCのx64 asmコードを生成しないのが残念だなあ.
対応させるのは難しいんだろうか.
ランニング
流石に朝5～6時台はTシャツだとさぶくなってきた.
『デバッガによるx86プログラム解析入門【x64対応版】』(うさぴょん)
たいしてお役に立ってないのに謝辞に記載していただいてとても恐縮.
個人的には6章の「ゼロからはじめるデバッガ自作」が興味深かった.
以前, DLLインジェクションと自己書換え系の処理をしたときに, それ系のAPIをいくつか調べながら使ったことがある.
手さぐりだったのでなんだかよく分からないコードになってしまった.
それらが一歩一歩説明されているのはよい案内図になる.
ただ私の作った奴は64bit版に対応させようとしていろいろはまった.
今回のはx64対応版とあるので, そのあたりの話がもう少しつっこんであるとよかったかもしれない.
あと, 単なる技術的な解説だけでなくそれをとりまく社会や法律についても言及されているのが興味深かった.
『ある日、アヒルバス』(山本幸久)
高卒入社5年目のバスツアーガイドの人が主人公.
研修をする側のてんぱい具合とか, 吹っ切れる人とか, 男社会に対して革命を目指そうと思ってる人とか.
みながんばっててよい.
終盤, 思わぬところで社歌を歌うシーンはぐっとくる. やや気の抜けた社歌なのがより効果的だ.
『PSYCHO-PASS サイコパス』
アニメ. 2が始まったらしいが私がみたのは1の新編集版. 大分遅れてるな.
犯罪をしそうな精神を持った人が完全に管理された社会.
後半の首謀者マキシマの行動がすごいな. 『MONSTER』のヨハンみたいだ.
ラストのヒロインの選択が現実路線なのも, 単純な勧善懲悪でないのがいい.
debug debug
ひたすらtestとdebug.
test中にエラーが見つかって, その原因を探しているうちに別のエラーが見つかる.
これはなんだろうと調べたらつい最近本家Linuxのバグだと分かる.
そのパッチを取り込んでテストしていたらまた別のエラー(今度はこちらの責任)が見つかって.
あれ, 今なんのエラーを見てたのだっけみたいな.
自分がメインで手げがけたものは殆どsmall startの「確かに大丈夫」なものを組み合わせるスタイルだったが,
こういうある程度の規模になってしまったのものをちゃんとするというのはなかなか大変.
charに対するnew-placement
バッファ操作のためにnew-placementを使うことがあって
for (size_t i = 0; i < n; i++) {
new(&p[i]) T();
}
みたいなコードを書いていた.
T = charのときはp[i] = 0となるので単なるmemsetに置き換えられるだろうと思ったけどそうならない.
new(p) char();はif (p) *p = 0;という挙動をするようだ.
ループの外でpがNULLになるかをチェックしてくれてもいいように思うが, VC, gcc, clangどれもループ内で毎回チェックしていた.
_addcarry_u64続き
残念ながら今のVCはintrinsicにたいては保守的な最適化しか効かないので
template<size_t N>
void add(uint64_t *z, const uint64_t *x, const uint64_t *y)
{
unsigned char c = _addcarry_u64(0, x[0], y[0], &z[0]);
for (size_t i = 1; i < N; i++) {
c = _addcarry_u64(c, x[i], y[i], &z[i]);
}
}
みたいな固定長ループを展開してくれないのだった. どうしよう.
_addcarry_u64
おお, ちょっと見ない間にVCで使えるIntrinsicにこんなものが.
carryつきaddじゃないか.
Intelの人にも入れてくれって言ってみたことあるやつだ.
sbbに相当する_subborrow_u64やHaswellのmulxに相当する_mulx_u64もあるぞ.
試しに
void add(uint64_t *z, const uint64_t *x, const uint64_t *y)
{
unsigned char c = _addcarry_u64(0, x[0], y[0], &z[0]);
c = _addcarry_u64(c, x[1], y[1], &z[1]);
c = _addcarry_u64(c, x[2], y[2], &z[2]);
_addcarry_u64(c, x[3], y[3], &z[3]);
}
をコンパイルしてみる.
add proc:
00000 mov rax, [rdx]
00003 add rax, [r8]
00006 mov [rcx], rax
00009 mov rax, [rdx+8]
0000d adc rax, [r8+8]
00011 mov [rcx+8], rax
00015 mov rax, [rdx+16]
00019 adc rax, [r8+16]
0001d mov [rcx+16], rax
00021 mov rax, [rdx+24]
00025 adc rax, [r8+24]
00029 mov [rcx+24], rax
素晴らしい.
『論理爆弾』(有栖川有栖)
「しらみつぶしの時計」みたいなパズルっぽいのを想像していたら全く違った.
終盤のヒロインのうっかりミスと危機的状況の盛り上がりはよかったが肩すかしを食らった感もある.
このペースで進めて肝心の話にけりがつくのかなあ.
munmap
munmapは引数にmmapされたポインタだけでなくサイズも必要.
Xbyak::Allocatorのfreeはポインタしか持ってないので
munmapを使うMmapAllocatorはそのポインタを内部で管理するはめになってしまった.
カスタムアロケータなんて使ってる人はいないだろうから仕様を変更してしまおうかな.
どうしよう.
GMPをforkしたMPIRのカスタムアロケータのfreeはサイズを受け付けるようになっていて,
最初からそうすべきだったかと悔やまれる.
必要のない機能や必要のないクラスは作らない(自戒も込めて).
当たり前に思えるのだけど大規模なものになってくると様々な理由であったりする.
一度入ってしまうと削りにくいことを考えると追加するときにより慎重に考える必要がある.
とか思っていたら, 新人研修やOJTで「設計書通りのものを作らせる」という練習はよくやってるけど,
「その指示されたものは正しいのか, 必要なのか」と問わせる練習というのはしてなかった気がする.
自分に照らせばベンチャーでの受託開発なんかが一番その訓練に該当するだろうか.
リソースが足りないのだから最小限の工数で先方が一番納得できるところに落とし込む必要がある.
ほんのちょっとの制約を入れればコードやロジックがすっきりするならどんどん提案して受け入れられればそれを選択する.
そうすればバグも出にくいし, メンテナンスもし易い.
研修で考えると立場上上司や先輩からの指示だからそれにたいしてどうこういうのはかなりハードルが高いし難しい.
いくつかサンプルを出して考えてみようという練習をするとよいかもしれない.
MmapAllocator
mmap版を用意してみた.
ってブランチにする必要はなかったか.
posix_memalignとmmapの違いで気になるのが一つあった.
posix_memalignが返すポインタは(それほどメモリをとってないときは)2GiBに収まってるけどmmapのは63bit目が立ってる.
コード領域とXbyakの実行領域が2GiBに入ってることを仮定したオフセットの利用をしていると困るかもしれない(Windowsはその仮定は成り立ってないけど).
mmap + mprotect
10日のコードはAlignedMalloc(posix_memalignのラッパー)ではなくmmapされた領域だとエラーにならないらしい(mprotect_test.cpp).
mmapを使うようにした場合, 何か後方互換性を壊すことはあるのかな.
そもそも数万個もJITコードを生成するのはレアケースだからカスタムアロケータで逃げてもらうか.
どうしよう.
mprotectがこける
Xbyakのissue.
へえmprotectはmap countというのを消費するのか. 全然知らなかった.
#define XBYAK_NO_OP_NAMES
#include "xbyak/xbyak.h"
int main()
{
for (int i = 0; i < 70000; i++) {
void *p = Xbyak::AlignedMalloc(4096, 4096);
printf("i=%d, p=%p\n", i, p);
if (!Xbyak::CodeArray::protect(p, 4096, true)) {
puts("ERR");
return 1;
}
}
}
確かにこのコードを走らせると32768回ループする前にエラーで落ちた.
どうやって対応しようかな.
というか3万回以上のJITコード生成って….
ループ内でメモリは解放しなくてもprotect(p, 4096, false)すれば落ちないのか.
ということは同時に3万個以上のmprotectされた領域を管理できないということか.
『カイシャデイズ』(山本幸久)
大きくはない内装業者の社員それぞれに焦点を当てた連作短編集.
やな奴や, こんな人近くにいたら困るだろというような人たちもいるけど憎めない.
統括室長の隠れた働きを描く「いつもおひとり様」や妙に自信過剰な「ガウディでよろしく」が好み.
「ショーカツデイズ」もラストで本気になるのがいい.
この著者の本は初めて. 他のも読んでみよう.
C99のdesignated initializerとC++11のinitializer list
C99のdesignated initializerはあくまで記法の省略なので構造体の順に初期化されるようだ.
しかしC++のinitializer listは左から現れた順に評価される.
それなら
#include <stdio.h>
struct A {
A(int x) { printf("A %d\n", x); }
};
struct B {
B(int x) { printf("B %d\n", x); }
};
struct C {
C(int x) { printf("C %d\n", x); }
};
struct D {
A a;
B b;
C c;
};
int f(int x)
{
printf("f %d\n", x);
return x;
}
int main()
{
D d = { .b = f(3), .c = f(2), .a = f(1) };
}
というコードを書いたら"f 3", "f 2", "f 1"という順と"A 1", "B 3", "C 2"という順で(この二つがどう混ざるかは不明だが)現れると思った.
で試すとclang 3.4でbuildしたらclangがクラッシュした.
clang 3.5では警告はでないでbuildされたけど実行しても何も表示されない.
何も表示されないというのは意外だ.
バグなのかコードが悪いのか(副作用のあるもの書いちゃ駄目なんだっけ)かわからんけど混ぜるな危険だということはよく分かった.
sorry, unimplemented: non-trivial designated initializers not supported
同僚が書いていたコードで発生した.
最小化したのは次のコード.
struct A {
int x;
int y;
};
int main()
{
struct A a = {
.y = 0
};
}
レビューとしてはC++にC99の機能を入れちゃいかんで終わりなんだがg++は表題のエラーになるけどclangは通す(ので気がついてなかった).
C99の機能は普段使わないので知らなかったけどこの初期化順序は構造体の宣言順序なんやね.
struct A {
int a;
int b;
int c;
};
に対して
struct A x = { .b = 2, .a = 1, .c = 3 };
struct A x = { .a = 1, .c = 3, .b = 2 };
はどちらもA x = { 1, 2, 3 };と書いたのと同じ.
省略されたときとか, 途中で番号にしたときとかいろいろややこしいルールがあるんだなあ.
cppts filesystem
次期C++に向けての仕様策定中のFilesystem Library Proposalのメモ.
Bootとの一番の違いはpathクラスの変換メソッドがUTF-8への変換を直接サポートするところ.
string string() const;
wstring wstring() const;
string u8string() const;
u16string u16string() const;
u32string u32string() const;
こうやってみるとやはりu8stringという型がないのが気持ち悪い.
permissionまわりはPOSIXべったりなのでWindowsには不利かな.
VCはVisual Studio 2012から既にある程度filesystemが実装されている.
ただまだまだ変更が入る可能性は高いので注意.
『真夜中の探偵』(有栖川有栖)
第2次世界大戦終了時から微妙に分岐したパラレルワールド.
この世界では私的探偵行為が禁止されている. 国家の秩序を脅かすため.
隠れて探偵をしていた17歳の少女の父親も逮捕されてしまう.
なんとも暗示の多い世界だ.
ヒロインはまだ何もできない. 探偵っぽいことをしてはたしなめられたり怒られたりする.
探偵が探偵らしく振る舞えないミステリってすごい設定だ.
今は伏線はりまくりで今後どうなっていくのか.
小説内で登場人物が過呼吸になったときペーパーバック法(使ったのは鞄だったが)で落ち着かせていた.
今はそれはしてはいけないとされているらしい(過換気症候群にペーパーバック法はいけません).
ためしてガッテンでもやっていた(窒息死を招く大誤解! 本当は怖い過呼吸SP).
K&Rスタイルで納得できないこと via ときどきの雑記帳
C++でもメソッドで改行するかどうするかちょっと迷うときはあるけど理由なんて考えたことなかったな(今はほぼ改行に統一).
理由を推測するならまさにK&Rスタイルだったからなんじゃないかと.
つまり引数をとる関数は
// K&R
int main(argc, argv)
int argc;
char *argv[];
{
...
}
という形だった.
argvのところで改行するのは自然. だったら引数が無い関数も改行するだろう.
ここで関数の定義方法がANSIスタイルに変わっても改行方法は従来の形式を踏襲した.
// ANSI
int main(int argc, char *argv[])
{
...
}
本当かどうかは知らない.
アルドノア・ゼロ
録画だけしていたアニメ. 見始めたら面白くて最後まで見てしまった.
主人公の冷静沈着で臨機応変, 卓越した洞察力がすごい. 緊迫感もよい.
ラストはどうなったんだろう. みな生きてるのだろうか.
モデルと実装
1年近く前からWalBの開発に関わってる.
当初漠然と思っていたよりずっと難しい.
何が難しいのか一言でいえないのがもどかしい程度に難しい.
最近はWalBが使ってるlogとdiffと呼ばれるパーツたちが正しく動くことを示すためにきちんとしたモデルの再定義をして振る舞いを証明しようとしてる.
実装とテストはほぼ終わって試験運用に向かう段階なのに順序が逆だろと思うけど, やってみないと気がつかない部分も多い.
気にしないといけない登場人物が一人か複数人かによって全くややこしさというのが違うのだなあと改めて思う.
普段は何か作り始めるときは極力単純なモデルになるように意識的, 無意識的にやっている.
受託開発だとそれを制御できないと死活問題だしね.
ところが今回は途中参加で既にある程度物があって動かせないから実装からモデルを抽出しないといけない.
まるっきり普段と逆の考え方をする.
頭の体操になるし, うまく定義できると楽しいものだが, それらが終わって早く実際に使ってもらえるところにもっていきたいものだ.
昔
御意見は光成滋生<herumi@nifty.com>までお願いします