初めてのAndroidプログラミング
Hello Android Worldを見ながら試すのだけどどうしても
adt\appcompat_v7\res\values-v21\styles_base.xml:75: error: Error retrieving parent for item: No resource found that matches the given name 'android:Widget.Material.ActionButton'.
というようなエラーが大量に出る. いろいろクリックして[Properties]→[Android]→[Project Build Target]で [Google APIs]を選ぶといいことがわかった. どういう意味かはまだ分からないけど.
エミュレータはいつまでたっても起動しないので数年前に買ったNexus 7で試す. と思ったけど[開発者向けオプション]が見当たらない. タブレット情報のビルド番号を7回押すと出るらしい, とかいう情報をいろいろ数年遅れ(?)で調べる.
C++WG
transactional memory周りの調査の担当だったがまとめきれず(すいません). しかし, どうにも無理筋な気がする. 個人的にはstatic変数の初期化が問答無用で全てスレッドセーフになるのではなく[[thread_safe]]みたいな属性を付けたものだけなるようにすべきだったなあと改めて思う.
mergeしてもらった. picohttpparserのベンチマークによると1.7倍程度にはなったらしい. 自動ベクトル化とは異なるこういうピンポイントなSIMDの使い方はコンパイラがするのはもうちょっと先かなあ.
会場はビッグサイト. 昼御飯はイートインで食べたけど, 白玉団子みたいなもの凄まじくまずいうどんだった. そういえば以前来たときも食べ物事情が悲惨だったのを思い出した.
12時会場でとても混んでいる. 一つ一つをゆっくり見ていられない. もうちょっと会場が広いとありがたいな. 3Dプリンタを使った工作や, scratchを使ってハードウェアをいじっているものが意外と多く目についた.
休憩がてらに隣で開催していた豆腐&大豆食品フェアを覗くとこちらも面白かった.
『無限解析のはじまり ─わたしのオイラー』(高瀬正仁)
オイラーの時代の数学がどのようなものだったのかを描く. ライプニッツやベルヌーイによって微積分が始まったとき, まだ「関数」の概念はなかったらしい. 曲線がまずあって, それがある一定の規則に従っているときを考えていたのだ. オイラーが初めて変化量を考えて関数の概念が登場したそうな. 面白い.
ところで大学入試で使っていいのかどうかとよく話題になるロピタルの定理のロピタルは ベルヌーイの講義録をまとめたものを本にして有名になったもので, ロピタルが考えた定理ではないそうな. なんだってー.
SSEレジスタのbyteシフト
16byte全体のシフト命令pslldqしかなくてこれはimm8のみ受け付ける. だからシフト数が可変なときはこの命令を使うならswitchするしかない.
inline __m128i shr_byte(__m128i v, size_t shift)
{
switch (shift) {
case 0: return v;
case 1: return _mm_srli_si128(v, 1);
case 2: return _mm_srli_si128(v, 2);
case 3: return _mm_srli_si128(v, 3);
case 4: return _mm_srli_si128(v, 4);
case 5: return _mm_srli_si128(v, 5);
case 6: return _mm_srli_si128(v, 6);
case 7: return _mm_srli_si128(v, 7);
case 8: return _mm_srli_si128(v, 8);
case 9: return _mm_srli_si128(v, 9);
case 10: return _mm_srli_si128(v, 10);
case 11: return _mm_srli_si128(v, 11);
case 12: return _mm_srli_si128(v, 12);
case 13: return _mm_srli_si128(v, 13);
case 14: return _mm_srli_si128(v, 14);
case 15: return _mm_srli_si128(v, 15);
default:
#ifdef _MSC_VER
__assume(0);
#else
__builtin_unreachable();
#endif
}
}
Intelの最適化マニュアルにも載ってるけどこれは分岐予測が外れると全然速くない. シャッフル命令のpshufbを使ってシフトパターンをshiftに応じて選択したら分岐しないから速いかもと試してみた.
一瞬テーブルは16個必要と思うが, よく考えたらテーブルを32byteにして読み出すオフセットをずらせば1個のテーブルで16パターン作れる.
inline __m128i shr_byte(__m128i v, size_t shift)
{
static const unsigned char MIE_ALIGN(16) shiftPtn[32] = {
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80,
0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80
};
return _mm_shuffle_epi8(v, *(const __m128i*)(shiftPtn + shift));
}
単純なループで実験したところHaswellでshiftがランダムなときは20clkの差が出て shiftが固定でもこちらの方が速かった.
文字列比較
14日のtoLowerを使って変換した後文字列比較をする. 殆どが16byte以下の文字列なのでpcmpeqbで比較してpmovmaskbで取り出して値の比較.
// xと[key, key + keyLen)が一致しているかを返す
inline int is_same_short_str(__m128i x, const char *key, size_t keyLen)
{
__m128i k = _mm_loadu_si128((const __m128i*)key);
x = _mm_cmpeq_epi8(x, k);
uint32_t m = _mm_movemask_epi8(x);
uint32_t mask = (1 << keyLen) - 1;
return (m & mask) == mask;
}
簡単なベンチマークを取ると速くなってることが確認できた. しかし, 何故かベンチマーク全体の時間はオリジナルより遅くなっていた. よく分からない. どこかメモリアクセスでストールしているのか.
asm出力を見ていてわかった. 14日のtoLowerだとgcc(4.8.2)では余計なコードを生成していた.
gcc t.c -march=native -S -masm=intel -O3 -o -
toLowerSSE:
movabs rax, 4629771061636907072
push rbp
mov rbp, rsp
and rsp, -32
add rsp, 16
mov QWORD PTR [rsp-32], rax
mov rax, QWORD PTR [rsp-32]
vmovdqu xmm0, XMMWORD PTR [rdi]
mov QWORD PTR [rsp-24], rax
movabs rax, 6582955728264977243
mov QWORD PTR [rsp-48], rax
vpcmpgtb xmm2, xmm0, XMMWORD PTR [rsp-32]
mov rax, QWORD PTR [rsp-48]
mov QWORD PTR [rsp-40], rax
movabs rax, 2314885530818453536
mov QWORD PTR [rsp-64], rax
vmovdqa xmm3, XMMWORD PTR [rsp-48]
mov rax, QWORD PTR [rsp-64]
vpcmpgtb xmm1, xmm3, xmm0
mov QWORD PTR [rsp-56], rax
vpand xmm1, xmm2, xmm1
vpand xmm1, xmm1, XMMWORD PTR [rsp-64]
vpaddb xmm0, xmm0, xmm1
leave
.cfi_def_cfa 7, 8
ret
なんじゃこりゃ. constつけるとエラーになったから外したのに. でもstaticをつけても変わらない. いろいろ試してenum使うと意図通りのコードになることがわかった.
enum {
factor = 0x0101010101010101ull,
Am1 = ('A' - 1) * factor,
Zp1 = ('Z' + 1) * factor,
amA = ('a' - 'A') * factor
};
static MIE_ALIGN(16) uint64_t Am1Tbl[2] = { Am1, Am1 };
static MIE_ALIGN(16) uint64_t Zp1Tbl[2] = { Zp1, Zp1 };
static MIE_ALIGN(16) uint64_t amATbl[2] = { amA, amA };
これだともともと期待していたコードを生成した.
toLowerSSE:
vmovdqu xmm0, XMMWORD PTR [rdi]
vmovdqa xmm1, XMMWORD PTR Zp1Tbl.6793[rip]
vpcmpgtb xmm2, xmm0, XMMWORD PTR Am1Tbl.6792[rip]
vpcmpgtb xmm1, xmm1, xmm0
vpand xmm1, xmm2, xmm1
vpand xmm1, xmm1, XMMWORD PTR amATbl.6794[rip]
vpaddb xmm0, xmm0, xmm1
ret
C++だとstatic変数の初期化はスレッドセーフになってしまったのでやっぱり余計なコードが生成されてしまうこともあるし難しい.
って単に私が定数の扱いを分かってなかっただけか?
# 大昔も似たようなミスをした記憶が….
clangだともとのコードでも上記のasm出力をしてくれるのだが.
SIMD版のtoLower
@kazuhoさんのHTTPサーバH2Oの文字列操作で高速化できないかためすために久しぶりに触る. 結果的にそれほど速くなってないが作業メモ. ターゲットはlib/token_table.h. len byteのnameが56個の固定文字列のどれかに一致してるか探す関数. ただし大文字小文字は除く.
最初に入力文字列を最大16byte tolowerしてしまう.
#ifndef MIE_ALIGN
#ifdef _MSC_VER
#define MIE_ALIGN(x) __declspec(align(x))
#else
#define MIE_ALIGN(x) __attribute__((aligned(x)))
#endif
#endif
inline __m128i toLowerSSE(const char *p)
{
uint64_t factor = 0x0101010101010101ull;
uint64_t Am1 = ('A' - 1) * factor;
uint64_t Zp1 = ('Z' + 1) * factor;
uint64_t amA = ('a' - 'A') * factor;
MIE_ALIGN(16) uint64_t Am1Tbl[2] = { Am1, Am1 };
MIE_ALIGN(16) uint64_t Zp1Tbl[2] = { Zp1, Zp1 };
MIE_ALIGN(16) uint64_t amATbl[2] = { amA, amA };
__m128i x, t0, t1;
x = _mm_loadu_si128((const __m128i*)p);
t0 = _mm_cmpgt_epi8(x, *(const __m128i*)Am1Tbl);
t1 = _mm_cmpgt_epi8(*(const __m128i*)Zp1Tbl, x);
t0 = _mm_and_si128(t0, t1);
t0 = _mm_and_si128(t0, *(const __m128i*)amATbl);
x = _mm_add_epi8(x, t0);
return x;
}
ところでCで
const int a = 3; const int b = a * 4;
ってできないんだっけ(C++だともちろんできる). しばらくどうしていいのか悩んでしまった.
Fpクラス
今まで作ってたのはあまりにtemplateしすぎてデバッグ時に何かと見にくかったので, もっと簡潔に書き直すことにした. それから使いやすさのためにGMPを使うか使わないか, Montgomeryにするかそうでないかもクラスでわけないで単一のものにしよう. バッファのサイズだけは妥協してtemplateパラメータにする. 小さいサイズのときは多少メモリが無駄になるけど動的にすると結局ヘッダの分必要になるので殆ど変わらないだろうという見積もり.
健康診断
風邪が治り気味で受けるので朝御飯なし. お腹へって辛い. こういうときって血液の検査の結果は悪くなるのかな.
グアテマラ
パズルの答えがそれになって, 意味が分からなくていろいろやってもどうしてもこれになる. 検索したら本当にある(失礼)国の名前だった. メキシコの右隣. 4年ほど前にすごい陥没があったらしい. 嘘みたいな写真だな.
gccで-march=nativeとしたときにどのフラグが有効になったか見る方法.
すぐ忘れるのでメモっとく.
gcc -march=native -Q --help=target
clangだとどうするのだろう. -###の出力で-target-cpuを見ればnativeが何になったかはわかるようだが.
optコマンド
6日のllcしてopt -O3で最適化してllvm-disしたものはllを直接cppとリンクして-O3 -march=nativeでobj作ったものと同じコードが生成されるようだ. だから普段はこのやり方で見ておけば十分と思われる.
本社移転
来年, 東京日本橋のビルに引っ越すらしい. 「にっぽんばしやて」って言ってたらそれは大阪, 東京は「にほんばし」と言われてしまった.
体調はまだ戻らない. 胃のあたりの痛みは大分減ったけどご飯を食べるとしばらく痛い.
gmpの中身
mpz_classのget_mpz_t()で取れる中身はメンバーがint _mp_alloc, int _mp_sizeとポインタ. 乗算で2倍に膨れた後すぐmodする場合は, これらのメンバを自分で設定すれば中間変数はstackにとれそうだな. 後で試す.
風邪
一昨日から耳鳴りするなあと思ってたら昨日の夕方から胃のあたりが痛くなってきて鼻水が酷い. 今日はダウン.
gdb
apt-get upgradeでgdbのバージョンがあがっていた. 試したらgdbが落ちるプログラムでgdbが落ちなくなっていた.
LLVMで192bit x 192bit乗算続き
>スタックへの退避が2回ほど行われている.
これはnoaliasをつけたら直るかと思ったけどうまくいかなかった.
metadataの指定がうまくできてないのかもしれない. 使い方がよくわからない.
ただ明示的にloadとstoreの順序を入れ換えてやるとスタックへの退避がなくなった. 乗算と加算の回数も最小限になった. ただやはり32bitは別に作らないといけないようだ.
LLVMで192bit x 192bit乗算
とりあえず64bit環境前提で作ってみる. まず192bit x 64bit乗算のmul192x64を作る. 値の再代入ができない(SSA)なので, ちょっとかくだけでも変数の数が増えて名前の付け方が困る. だから細かいサブルーチンを沢山作ったほうがやりやすい感じだ.
define i128 @mul64x64(i64 %x, i64 %y) {
%x0 = zext i64 %x to i128
%y0 = zext i64 %y to i128
%z = mul i128 %x0, %y0
ret i128 %z
}
callを使っても最適化の段階で埋め込まれるので気にしなくてよい. そうやってmie::mul192x192を作ってみた.
実際にどういうコードに落ちるかはllcだけでは関数は全て呼び出しになってしまうので分からない(何かよいオプションがある?). 仕方がないので
ll → bc(ビットコード) → optによる最適化 → bc逆アセンブル → llcによるnativeコードへの変換
というフェーズをとることにした.
llc -o -o | opt -O3 -o - | llvm-dis -o - | llc - -mattr=bmi2
出力はこんな感じ.
_ZN3mie10mul192x192EPmPKmS2_: # @_ZN3mie10mul192x192EPmPKmS2_
# BB#0: # %entry
push rbp
push r15
push r14
push r13
push r12
push rbx
mov r9, qword ptr [rsi + 16]
mov r10, qword ptr [rsi]
mov rax, qword ptr [rsi + 8]
mov r8, qword ptr [rdx + 16]
mov rsi, qword ptr [rdx]
mov rcx, qword ptr [rdx + 8]
mov rdx, rsi
mulx r11, rdx, r10
mov qword ptr [rsp - 8], rdx # 8-byte Spill
mov rdx, rax
mulx r12, rbx, rsi
mov rdx, rsi
mulx r15, rsi, r9
add rbx, r11
mov qword ptr [rsp - 16], rbx # 8-byte Spill
adc rsi, r12
mov rdx, rcx
mulx r11, r12, r10
mov rdx, rcx
mulx r13, rbp, rax
mov rdx, rcx
mulx r14, rcx, r9
adc r15, 0
add rbp, r11
adc rcx, r13
adc r14, 0
mov rdx, r8
mulx r10, r13, r10
mov rdx, rax
mulx r11, rax, r8
mov rdx, r8
mulx rbx, rdx, r9
add rax, r10
adc rdx, r11
adc rbx, 0
add r13, rsi
adc rax, r15
adc rdx, 0
adc rbx, 0
add r12, qword ptr [rsp - 16] # 8-byte Folded Reload
adc r13, rbp
adc rax, rcx
adc rdx, r14
adc rbx, 0
mov rcx, qword ptr [rsp - 8] # 8-byte Reload
mov qword ptr [rdi], rcx
mov qword ptr [rdi + 8], r12
mov qword ptr [rdi + 16], r13
mov qword ptr [rdi + 24], rax
mov qword ptr [rdi + 32], rdx
mov qword ptr [rdi + 40], rbx
pop rbx
pop r12
pop r13
pop r14
pop r15
pop rbp
ret
スタックへの退避が2回ほど行われている. 自分で作ったときは256x256ですらレジスタを使い回してうまくできたので, その辺りちょっと甘いかもしれない. あるいは依存関係の都合上こちらのほうがよいのか.
LLVMのmul
32bit環境だとmul i64, i64もSEGVする. 結局CPUが持つnativeにもつ乗算命令のサイズを越えられない.
LLVMでかけばハッピーなのかと思ったけどx64/AArch64はともかく, AArch32用のコードは別に書かないといけないのか(ある程度は共用できるが). VC用はまた別途書かないといけないし, 旨みが少ない.
llcがSEGVする続き
このコードがアウト.
define i192 @fff(i128 %px, i64 %py) {
entry:
%x = zext i128 %px to i192
%y = zext i64 %py to i192
%z = mul i192 %x, %y
ret i192 %z
}
mulじゃなくてaddならちゃんといくのでmulもうまくいくと思ったのになあ. これができないなら戦略は大幅見直しか. にしてもSEGVするのはバグだろうな. 最新版で直ってるだろうか.
LLVM続き
今度は192bit x 192bit → 384bit乗算を書いてみる.
define void @mie_mul192x192(i384* %pz, i192* %px, i64* %py) {
entry:
%x192 = load i192* %px, align 64
%py1 = getelementptr i64* %py, i64 1
%py2 = getelementptr i64* %py, i64 2
%x = zext i192 %x192 to i384
%y0_64 = load i64* %py
%y1_64 = load i64* %py1
%y2_64 = load i64* %py2
%y0 = zext i64 %y0_64 to i384
%y1 = zext i64 %y1_64 to i384
%y2 = zext i64 %y2_64 to i384
%xy0 = mul i384 %x, %y0
%xy1 = mul i384 %x, %y1
%xy2 = mul i384 %x, %y2
%xy1s = shl i384 %xy1, 64
%xy2s = shl i384 %xy2, 128
%t = add i384 %xy0, %xy1s
%z = add i384 %t, %xy2s
store i384 %z, i384* %pz
ret void
}
でコンパイル.
llc-3.5 modp.ll -o - -x86-asm-syntax=intel
.file "modp.ll"
0 libLLVM-3.5.so.1 0x00002b52c1c6c7e2 llvm::sys::PrintStackTrace(_IO_FILE*) + 34
1 libLLVM-3.5.so.1 0x00002b52c1c6c5d4
2 libc.so.6 0x00002b52c2a59c30
3 libc.so.6 0x00002b52c2aac56a strlen + 42
4 libLLVM-3.5.so.1 0x00002b52c1b9effa llvm::SelectionDAG::getExternalSymbol(char const*, llvm::EVT) + 42
5 libLLVM-3.5.so.1 0x00002b52c1c03b0e llvm::TargetLowering::makeLibCall(llvm::SelectionDAG&, llvm::RTLIB::Libcall, llvm::EVT, llvm::SDValue const*, unsigned int, bool, llvm::SDLoc, bool, bool) const + 526
6 libLLVM-3.5.so.1 0x00002b52c1b41697
7 libLLVM-3.5.so.1 0x00002b52c1b49385
8 libLLVM-3.5.so.1 0x00002b52c1b567fe
9 libLLVM-3.5.so.1 0x00002b52c1b56ecf llvm::SelectionDAG::LegalizeTypes() + 943
10 libLLVM-3.5.so.1 0x00002b52c1bf0ac4 llvm::SelectionDAGISel::CodeGenAndEmitDAG() + 164
11 libLLVM-3.5.so.1 0x00002b52c1bf3d02 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) + 1170
12 libLLVM-3.5.so.1 0x00002b52c1bf50dc llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) + 940
13 libLLVM-3.5.so.1 0x00002b52c160bd57 llvm::FPPassManager::runOnFunction(llvm::Function&) + 471
14 libLLVM-3.5.so.1 0x00002b52c160bddb llvm::FPPassManager::runOnModule(llvm::Module&) + 43
15 libLLVM-3.5.so.1 0x00002b52c160e375 llvm::legacy::PassManagerImpl::run(llvm::Module&) + 693
16 llc-3.5 0x000000000040fad4
17 llc-3.5 0x000000000040af60 main + 368
18 libc.so.6 0x00002b52c2a44ec5 __libc_start_main + 245
19 llc-3.5 0x000000000040afb9
Stack dump:
0. Program arguments: llc-3.5 modp.ll -o - -x86-asm-syntax=intel
1. Running pass 'Function Pass Manager' on module 'modp.ll'.
2. Running pass 'X86 DAG->DAG Instruction Selection' on function '@mie_mul192x192'
clangがSEGVしてる…. さてどうしたもんか.
今のメインマシン(128GB SSD)の残り容量が10GBぐらいになってきたのでPLEXTORのPX-256M6Pro SSDを買う. 1万8千円ちょい. True Imageでコピーしたら容量だけ増えてすぐ使える. 便利だ.