憂鬱な午後のひととき

cygwinのマルチスレッドでのmalloc/freeがやたら遅い問題は結局自力で解決できなかったので, cygwinのMLで聞いてみた. で, "serious performance problem"との返事があった. 今まで発覚しなかったんだなあ.

法事で京都に行ったので久しぶりに友達に会う. 相変わらず忙しくて毎日帰宅は23時ぐらい. 今からまた仕事だとか. ただ毎日片道12kmの自転車通勤で去年は医者にいってないらしい. すごい元気だ.

去年Linux kernel MLに投稿した一行パッチが本体に取り込まれた. ちょっとうれしい.

Succinct Vector Wavelet Matrix implementation

社内勉強会でしゃべったスライド. まだ勉強中なので中身保証無し. 今のところwavelet-matrix-cppの1.5～2倍ぐらいの速度が出てる.

最近Wavelet行列を勉強しながらちまちまと実装してる.

同じアルゴリズムでも人によって結構実装方法が違っているのが楽しい. ランダムなメモリアクセスの遅さを痛感するパターンが多くて難しいけど面白い.

簡潔ビットベクトルも 半年前にpsadbwを使ったテクニックを見つけて喜んでいたが, 結局違う方法になってしまった(テクニック自体は気に入ってるのでまた戻ってくるかもしれないけど).

tcmallocを試してみる(けど駄目だった)

TCMallocを使ったらcygwinでmalloc, freeが遅い問題は解決するのか試してみる. その前にまずLinuxでベンチマーク. コードは16日のOpenMPを使ったやつでnを1 * 2 * 3 * 4 * 20000にしたもの.

>sudo apt-get install libgoogle-perftools-dev
>g++ t.cpp -Ofast -fopenmp -ltcmalloc_minimal
   -fno-builtin-malloc -fno-builtin-calloc
   -fno-builtin-realloc -fno-builtin-free

確かに速いな. 効果がありそうなのでcygwinでbuildしてみよう. でもconfigure && makeだと警告がでまくるなあ. そしてtcmalloc_unittest.ccを試すと途中でSegmentation fault.

Testing threaded allocation/deallocation (10 threads)
  Test 50000 out of 50000: allocate
  Test 50000 out of 50000: free
Check failed: object.ptr[i] == expected

SIGSEGV received when using gperftool 1.10 built with cygwin on x64には同じ症状で困ってる人がいた. config.hのHAVE_TLSを消してみたらもう少しテストが進んだけどまた落ちた. 難しそうだな. cygwinは主題ではないし放置するか. でもcygwinをサポートしてるっぽいしまだ何かポカしてるのかなあ.

cygwinのマルチスレッドでのmalloc, freeがやたら遅い.

OpenMPを使ったプログラムがWindows, Linuxでそれなりにスケールしてたのにcygwin上で実行すると全然速度が出ない. 出ないどころかシングルスレッドよりも恐ろしく遅い. コードを削っていろいろ試したら次のコードが駄目だった.

// g++ t.cpp -O3 -fopenmp -lpthread
// cl t.cpp /Ox /openmp
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <omp.h>

void task(int idx)
{
    const int size = 100;
    for (int i = 1; i < size; i++) {
        char *p = (char*)malloc(i);
        memset(p, idx, i);
        free(p);
    }
}

int main(int argc, char *argv[])
{
    const int threadNum = argc == 1 ? 1 : atoi(argv[1]);
    omp_set_num_threads(threadNum);
    printf("thread %d\n", omp_get_max_threads());
    const int n = 1 * 2 * 3 * 4 * 1000;

    #pragma omp parallel for
    for (int i = 0; i < n; i++) {
        task(i);
    }
    puts("ok");
}

このコードをcore i3上でLinux(ubuntu 12.10)のgcc 4.7.2, cygwin(1.7.17)のgcc 4.5.3, Windows 7のVC 2012で実行してみた. 一応cygwinに合わせてLinux, Windowsも32bit binaryで測定. またアセンブリ出力を見て最適化でmalloc, freeが削除されていないことを確認する.

core i3は物理コア2でHyperTheadingで4コアに見えてるだけなのでthreadNum = 1と2のときしかあまり意味がないかもしれないけど, cygwin上の値が明らかにおかしい.

OpenMPの使い方が悪いのかとpthreadを使って同様のことをやってみたmalloc-free-pthread.cpp. でもやはりcygwin上ではthreadを生成すると10倍以上遅い. またmalloc, freeを使わない計算だとcygwin上でもそこそこスケールする.

タスクマネージャでみるとkernelのCPU使用率が高いのでmalloc, freeをマルチスレッドで動作させるためのロックの部分がおかしいんじゃないかという気がする. ただ昔からあるシステムのそんな基本的な部分が悪いとも思えないので何か私の使い方が間違ってる可能性が高いと思うのだけど何をミスってるんだろう.

@sinya8282さんと『tensor geometry and applications』の読み始め

まあどこまでいけるか分からないけどぼちぼちと. ベクトル空間V, Wのテンソル積の定義に双対空間を使ってる. そんなやりかたもあるんだな. でも見た目が対称性をもってないし無限次元でうまくいくのか微妙でいまいちな(本は有限次元限定だからいいけど).

雑談でVとV^*が同型にならない例を出してみる. Vを1変数多項式からなるkベクトル空間k[x]とする. Vの基底は1, x, x², x³, ... V^*:={f :V → k | fはk線形}の元として y_j(xⁱ) := δ_ijとする. 形式的な無限和y = Σy_i = (1, 1, 1, ...)はV^*の元になるけどVの元とは対応がつかない(Vの元は基底の有限和でないといけない).

Vはkの加算無限個の直和, V^*は直積になってる.

minマクロでの値の評価

よくある

#define min(x, y) ((x) < (y) ? (x) : (y))

ではxやyは2回評価されるからmin(len, strlen(str));みたいな書き方はやめた方がいいという話になった.

けれども最近のコンパイラなら1回しかstrlenを呼ばない最適化をしてるんじゃないかと試してみた.

#include <stdio.h>
#include <string.h>

#define min(x, y) ((x) < (y) ? (x) : (y))

int main(int argc, char *argv[])
{
    return min(argc, (int)strlen(*argv));
}

結論から言うと予想通りgcc 4.7.2やclang 3.0はstrlenを一度しか呼び出さなかった. たいしたもんだ. 残念ながらVCは2回文字の長さを求めるコードを出力した.

ところがgccやclangでもstrlenを自作した場合は駄目だった. つまり

#include <stdio.h>
#include <string.h>

#ifdef __GNUC__
size_t my_strlen(const char *p) __attribute__((pure));
#endif

size_t my_strlen(const char *p)
{
    size_t ret = 0;
    while (*p++) {
        ret++;
    }
    return ret;
}

#define min(x, y) ((x) < (y) ? (x) : (y))

int main(int argc, char *argv[])
{
    return min(argc, (int)my_strlen(*argv));
}

ではVCと同じくmy_strlenを2回実行した. つまりstrlenを特別扱いしているようだ. my_strlenに__attribute__((pure))をつけたらmy_strlenも1回しか呼ばれないのかなと試したけど駄目だった.

したがって一般にはやはりマクロに渡すときは関数をいれるのはやめた方がいいと思う.

ところでpureじゃなくてconstだと変わるのだろうかと再度実験. なんと1回しか呼ばれない最適化が行われた(gcc/clang共に). おもろいな. VCのdeclspecには今のところそういうオプションはなさそうだ(欲しい).

// __attribute__((pure))          __attribute__((const))
main:                             main:
    mov rsi, QWORD PTR [rsi]          mov rdx, QWORD PTR [rsi]
    mov eax, edi                      xor eax, eax
    cmp BYTE PTR [rsi], 0             cmp BYTE PTR [rdx], 0
    je  .L8                           je  .L8
    xor edx, edx                  .L9:
.L9:                                  add rax, 1
    add rdx, 1                        cmp BYTE PTR [rdx+rax], 0
    cmp BYTE PTR [rsi+rdx], 0         jne .L9
    jne .L9                       .L8:
    xor ecx, ecx                      cmp edi, eax
    cmp eax, edx                      cmovl   eax, edi
    jl  .L21                          ret
.L16:
    add rcx, 1
    cmp BYTE PTR [rsi+rcx], 0
    jne .L16
.L14:
    mov eax, ecx
    ret
.L8:
    xor ecx, ecx
    test    edi, edi
    jns .L14
.L21:
    rep
    ret

しかしstring.hのstrlenの宣言には__attribute_pure__が使われていて, それは__attribute__ ((__pure__))になってるように見えるのだがなんでstrlenが1回しか呼ばれない最適化が行われてるのだろう. やっぱり特別扱い?

ちなみにそもそも話の発端となったLinuxのkernel.hでは

#define min(x, y) ({                \
    typeof(x) _min1 = (x);          \
    typeof(y) _min2 = (y);          \
    (void) (&_min1 == &_min2);      \
    _min1 < _min2 ? _min1 : _min2; })

となっていて, gcc拡張により変数を一度保持してるので1回しか関数が呼ばれないようになっていた.

(void) (&_min1 == &_min2);は型が違う変数のminをさせないためにある. たとえばlong aとint bのminをとると異なるポインタ型の比較になって警告がでる. うまいね.

pthreadを使った簡単なテストプログラムをcygwinで走らせてみたら動かなくて結構悩んだのだけど結局 pthread_attr_init()が失敗していたせいだった. pthread_attr_init()で初期化したattrを不要になった時点でpthread_attr_destroy()で破棄したら動くようになった.

Linuxではpthread_attr_init()は失敗しないとあったのでエラーチェックをしてなかったのが敗因.

clang/VC/gccってこういうコードに対して変数の未初期化警告出さないんだな(by @nishio).

#include <stdio.h>

struct X {
    int x;
    int y;
};

void put(const X& x)
{
    printf("%d %d\n", x.x, x.y);
}

int main()
{
    X x;
    put(x);
}

VCのコード分析でも出なかった. clangのstatic analyzerを試そうとしたけどうまくインストールできなかった. あとでやり直す. valgrindだと一応わかる. 気を付けよう.

今まで何度かOpenMPを使ってみたのだけど細かい部分の制御がどうも難しくて結局threadを使うことにした. この感覚はgccのインラインアセンブラに近い. うまくやればできるのだろうけどその方法を調べるのが面倒.

現行犯でもなく, 否認もしてるのに新聞は一面に容疑者の顔写真を載せるのだなあ. 今までは容疑者なんだから当然だと思ってたけど, やっぱりおかしい気がしてきた.