憂鬱な午後のひととき

7月31日_

オーバーロードされた関数の呼び出し(解決案)

@pepshisoさんがさくっと答えてくださった. 

#include <stdio.h>

void f(int) { puts("f:int"); }
void f(double) { puts("f:double"); }

template <class P>
struct call_ {
    explicit call_(P p) : p(p) {}

    void operator()(void (*func)(P)) const {
        func(p);
    }

    P p;
};

template <class P>
call_<P> call(P p)
{
    return call_<P>(p);
}

int main()
{
    call(5)(f);
    call(5.3)(f);
}

なるほど, 引数と関数を同時に決めようとすると関数をキャストしないとあいまいと言われてしまうけど, 先に引数の型を確定させておくとうまくいくのか. どうもありがとうございます.

7月30日_

オーバーロードされた関数の呼び出し

#include <stdio.h>

void f(int) { puts("f:int"); }
void f(double) { puts("f:double"); }

template<class P>
void call(P p, void (*func)(P))
{
    func(p);
}

int main()
{
    call(5, (void (*)(int))f); // ***
    call(5.3, (void (*)(double))f); // ***
}

の***の関数のキャストをかかないですむ一番楽な方法ってなんだろう. 引数(この場合は5や5.3に応じて適切なものが選ばれてほしいのだが). 

  #define CALL(x, f) call(x, (void (*)(decltype(x)))f)

はC++03で使えないしなあ. なるべく黒魔術を使わない方法希望.

7月29日_

Makefileでプロジェクトのルートディレクトリを設定する

コンパイラやリンカにソースやヘッダファイル, ライブラリなどのパスを指定したいとき, そのプロジェクトのルートディレクトリからの相対パスで記述したいことがある.

たとえば共通設定ファイル(ex. common.mk)にTOPDIRという変数を定義して, いろんなディレクトリのMakefileから参照する. TOPDIRをたとえば 

TOPDIR=$(shell pwd)

と定義すると, includeしたディレクトリごとに変わってしまってうまくいかない. あこぎなやり方(トップディレクトリのところまでをsedで切り出すとか)をしていたのだが, 今日, うまい方法を教わった. 

TOPDIR:=$(realpath $(dir $(lastword $(MAKEFILE_LIST))))/

MAKEFILE_LISTは最初本来のMakefileの名前が入ってる. includeするとそれらのファイル名が追加される.

lastwordで最後のやつをとってくる. dirでそのファイルがあるディレクトリ, realpathでそのパスを絶対パスに置き換える. 最後に/をつければ出来上がり. realpathはabspathでもよい(後者はファイルの存在をチェックしない).

正直なところ, こういうmakeのバッドノウハウには近づきたくないのだけどありがたい. どうもありがとうございます.

7月28日_

Xbyakのリファクタリング

Haswellのgather命令は[base + index * scale + dsip]の形のアドレッシングで, indexにXMM, YMMレジスタを指定できる. 以前のバージョンアップではそれに対応するためにごちゃごちゃしてしまった.

で, そこの部分を統合中. 一気にかなりのコードを変更しないといけないので苦戦する. その途中で 

struct E {
    inline friend void func(const E&){}
};

と 

struct E {
};
inline void func(const E&){}

とは違うのに気がつかずはまってしまった.

7月27日_

VCのバグ報告のつづき

23日のやつは, 当面放置に決定らしい. 残念.

7月25日_

『はるひのの、はる』(加納朋子)

このシリーズ, あんまり好きじゃないんだよなーと思いつつ, 本屋でみかけたらつい買ってしまった. 「はるひのの、なつ」ぐらいの単純なやつ(定番の定番)は分かりやすくてよかったけど, 他は捏ね繰り回してなんだかよく分からない. そのうち人物相関図を書きながら読み直すかもしれない.

叙述トリック系も大半は置いてけぼりになってしまう. 多分頭の中のスタックが小さすぎるんだろうな.

7月23日_

VCのバグ報告

今日も見つけたので登録してみた. 

namespace ns {

void f() try {
} catch (...) {
}

struct X {
    template<class T>
    void g(const T&) { }
};

}

int main()
{
    ns::X().g("test");
}

がコンパイルエラーになる. 名前空間とtry/catchとtemplateが同時に起こらないと発生しないようだ. コードを小さくするのに結構手間取ってしまった.
以前見つけた 

#include <stdio.h>

template<class T>
struct A {
    static const int tbl[];
};

template<class T>
const int A<T>::tbl[] = { 1, 5, 9 };

int main()
{
    printf("%d\n", (int)sizeof(A<int>::tbl));
}

がコンパイルエラーになるのはVC2013でも直ってなかった. 残念. こちらは早く直ってほしいなあ.

7月21日_

『天地明察』(冲方丁)

それまで800年使われていた暦に変わる優れた暦を作った渋川春海の生涯を描く. 測量行脚の描写については『四千万歩の男』(井上ひさし)の方が苦労が伝わったように思うけど, 関孝和や"えん"との関わりとか, ドラマ的には面白い.

#予備知識なしで読み始めたので最初"えん"が『算法少女』(遠藤寛子)みたいなのかと思ってしまった.

ただ関孝和に出した「怪問」はそれは間違いに気づくだろうとか, 最後の問題が解ける問題なのかいまいち分からなかったのがちょっと残念(作品中すごいものと言ってるだけに). あと前半愚直な性格の主人公が, 最後で政治的手腕を発揮して暦を認めさせるのがやや唐突な感じを受けた.

7月20日_

扇風機

が, 数日前から首振りで端に来るときカタカタいいだした. 先週買ったばかりなのに. うーん, 送風の音がほぼ無音でもこれでは….

7月19日_

VC2013で導入されたベクトル呼び出し規約 __vectorcall

今までWindowsで__mm128などの値を引数にする関数ではポインタ渡しになっていた. たとえば__m128iを二つ足して値を返す関数addは次のようなコードになっていた(cf. Windowsでの呼び出し既約). 

__m128i add(__m128i x, __m128i y)
{
    return _mm_add_epi32(x, y);
}
///
add:
  movdqa xmm0, ptr [rcx] // xへポインタ
  paddd  xmm0, ptr [rdx] // yへのポインタ

呼び出す側もわざわざstackにおいてから呼ぶことになる. 

  movdqa  XMMWORD PTR $T1[rsp], xmm0
  movdqa  XMMWORD PTR $T2[rsp], xmm1
  cal     ?add@@YA?AT__m128i@@T1@0@Z ; add

これは非常にばからしい. 実際には関数をインラインで書いておくと最適化されて殆どの場合はレジスタ経由になるのだが, うまくいかないこともある.

それでIntroducing Vector Calling Conventionによると, VC13では新しい呼び出し規約__vectorcallが追加されたようだ. /Gvをつけると自動的にその規約にしたがう.

ざっくり書くと__m128, __m256, __m128iなどは最大4個の引数までをxmm0やymm0などにアサインするというもの. 上記の例で試してみよう. /Gvをつけてコンパイルし直してみる. 

// 関数本体
add:
  paddd xmm0, xmm1
  ret

// 呼び出す側
  movdqa  xmm1, xmm6 // 計算結果が(xmm6, xmm7)に入ってる場合
  movdqa  xmm0, xmm7
  call    ?add@@YQ?AT__m128i@@T1@0@Z ; add

これは素晴らしい.
ただgccと違って関数の中でxmm6, ..., xmm15の値を変更するときは元に戻す必要があるのは今までと変わらない.

自分がどちらの関数か区別するには__FUNCSIG__をみればよさそうだ. 

void add(__m128i, __m128i)
{
    printf("func='%s'\n", __FUNCSIG__);
    // func='void __cdecl add(union __m128i,union __m128i)'
}

void __vectorcall addv(__m128i, __m128i)
{
    printf("func='%s'\n", __FUNCSIG__);
    // func='void __vectorcalladdv(union __m128i,union __m128i)'
}

__vectorcallの方は関数名と__vectorcallの間にスペースがないなあ. 多分付け忘れ(^^;

7月18日_

n個の中からk個取り出す組み合わせを生成するビット演算

たとえば5個の中から3個取り出す組み合わせとして 

uint32_t a = 0b11000; /* 5bitのうち3bitが0 */
while (a) {
    a = nextCombination(a);
}

というコードを実行するとaが 

11000
10100
10010
10001
01100
01010
01001
00110
00101
00011

というビットパターンになるようなnextCombination()を作りたい.

aが偶数のときは 

1 1 0 0 0
    ↓
1 0 1 0 0
    ↓
1 0 0 1 0
    ↓
1 0 0 0 1

と変化している. よくみれば0bitからみて初めて1になったときよりも1bit小さい値を引けばよいことがわかる.

初めて1になるところだけ1が立ってるようにするにはa & -aを計算すればよい. そしてそれを1bit右に寄せて元の値から引く. つまり 

  a ← a - (a & -a) / 2;

aが奇数のときはやや複雑. 

1 0 0 0 1 1 1 1
  ^^^^^ =======
    t個   s個
    ↓
0 1 1 1 1 1 0 0
    ======= ^^^
      s個   t-1個

下から1がs個つづき, そのあと0がt個つづいたとすると, それをs個の1と(t-1)個の0に入れ換える必要がある.

まず1が何個続いてるかを知るには1を足してbsrすればよい. ただ続いてtを求めるためにs個の1のマスクを作る必要があるので a ^ (a + 1)をつくる. それを2で割ってaから引けば下位s bitがクリアされる. 

1 0 0 0 1 1 1 1  = a
  ^^^^^ =======
 ↓    t個   s個  b = a ^ (a + 1) = 1 1 1 1 1
1 0 0 0 0 0 0 0  = c = a - b / 2

できた値cの上位bitを偶数のときと同様c & -cでクリーニングしてsbit右シフトしてcから引けばOK. つまりこんな感じ(n == 64とかn == kのときは例外処理がいると思う). 

size_t nextCombinationC(size_t  a)
{
    if (a & 1) {
        size_t b = a ^ (a + 1);
        size_t c = a - b / 2;
        return c - ((c & -c) >> bsr(b + 1));
//      return c - (c & -c) / (b + 1);
    } else {
        return a - (a & -a) / 2;
    }
}

さて, Haswellにはビット演算命令がいくつか拡張されている(前回のx86/x64最適化勉強会のフラグを愛でるの最後の方). 

  blsmsk(y, x); // y = x ^ (x-1)
  blsi(y, x); // y = x & -x

おお, まさにこういうときにつかうもんやないかということで使ってみた(combination.cpp).

n=31, k=15(300540195通り)のパターンを生成するのに掛かったnextCombination()一つあたりのクロック数を測定してみた. CPU周波数はどちらも3.4GHz.

nCkのパターン算出に掛かった平均クロック数
i7-2600K i7-4770 i7-4770 with Haswell新命令
10.43 7.93 6.64

この場合, SandyBridgeよりもHaswellが同じコードで30%ほど早く, Haswellの新命令を使うと更に20%ほど速くなった. 新命令を使ったバージョンはXbyakで書かれていてインライン展開されないのでやや不利かもしれない. そもそも, 単なるループでの比較なのでこの数値に殆ど意味はない.

とはいえ, このあたりの命令前提だとアルゴリズムをもう少し改良できそうだな. 面白そうだ.

7月17日_

Haswellベンチマーク

WindowsのVMware上にubuntu 13.04を入れてみたがまだAVX2以降はサポートしてないようだ. 残念. 

// on Windows
64bit
vendor intel
 mmx mmx2 cmov sse sse2 sse3 ssse3 sse41 sse42 popcnt aesni rdtscp
 osxsave(xgetvb) pclmulqdq avx fma avx2 gpr-group1 gpr-group2 lzcnt
popcnt ok
family=6, model=C, stepping=3, extFamily=0, extModel=3
display:family=6, model=3C

// on Linux(on VMWare)
 mmx mmx2 cmov sse sse2 sse3 ssse3 sse41 sse42 popcnt aesni rdtscp
 osxsave(xgetvb) pclmulqdq avx fma

ate-pairingは0.343msecぐらいでWindows上での-mulx 0とほぼ同じ. このプログラムは殆どアセンブラで書かれているのでコンパイラによる差は無いだろうから, VMware上でのオーバーヘッドも高々1%とみなせる.

手持ちの昔作ったetat pairingを試してみる. F397は既に破られてるし, F36 x 509も今日弱いよというtweetが流れていたので, もう小標数は辛いなという雰囲気だが, intrinsicなSIMDで書いてるのでコンパイラによる違いが出やすい. VC2013 Previewも入れてみたので最適化の具合がどう変わったかみてみよう.

VCのバージョンによる差異は殆どなく0.390msec, gcc 4.7.3では0.338msec. gccの方が速かった. 結構差があるな.

次にfmathのfastexp.cppを試してみた. と言っても見るのは標準ライブラリのstd::expとその配列実行版.

gccは61clkで配列に対するループも同じ61clkだった. gcc 4.7.3で-Ofastなので自動ベクトル化が効くかと思ったけどそうでもない(ちゃんと調べてない). VC12ではstd::expが30clk, 配列版は10clk. おお速い.VC13も同じだったが/arch:AVX2とすると更に速くなって24clk, 7.4clk.

Introducing Vector Calling ConventionによるとVC13では新しい呼び出し規約__vectorcallが追加されたらしい. XMMレジスタをメモリ経由で渡すなんておばかなことから開放される!(というかgcc並になる) 上のetat pairingの差はそれがネックになってるのかな. それらのチェックもしたいが今日はコードの見すぎで疲れたのでまた後日.

7月16日_

Haswell(i7-4770 3.4GHz)マシン

届いたのでいろいろ設定中. とりあえずate-pairingが-mulx 0で0.339msec, -mulx 1で0.300msecとなったのは確認した. 勉強会に向けていろいろ準備しなきゃ.

7月13日_

扇風機を買いに行った.

最初は日立のものにしようと思ってたのだけどタッチキーでLED表示だったのでやめた. そういうのは夜中の暗い中で半分目を閉じた状態だと使いにくそうだから.

とは言っても, 日立に限らず, 最近の家電はなんでもかんでもLED表示で夜中もずっと光ってて, うっとうしいことこのうえない. 上から紙でふさいでしまうことも多い.

光らないやつ…と探して結局D'z STYLEのLEDがついてないボタン式のがあったのでそれにした. デザインは安っぽいのだけど目をつぶってても操作できるのがよい.

7月9日_

std::functionとラムダ式の速度比較

C++11で導入されたstd::functionは従来の関数ポインタ, 関数オブジェクトやラムダ式などを統一的な形で導入できてとても便利だ. が, そのために単なる関数に比べて若干呼び出しコストが大きい. 大抵の場合はそれが問題になることはないが極めて大量に呼び出される場合は無視できないコストになることがある.

たとえばstd::sortの第3引数にラムダ式とstd::functionを渡したときの速度の違いを見てみよう. [function_vs_lambda.cpp]

std::vector<int*>に100万個のポインタを入れて 

[](const int *px, const int *py) { return *px < *py; });

をそのままsortに渡したときと, 一度std::functionに入れて渡したときのソート時間の速度比較をしてみた.

Windows 7 + VC12 + Core i7-2600Kではstd::functionの方がラムダ式より1.78倍, Linux + gcc 4.8.1 + Core i7-3930Kでは1.94倍遅いという結果になった. もちろんこの結果は単なる一例で条件や環境によって変わるだろう. それでも小さくはない差異といえる.

std::functionだと呼び出しごとに関数が0でないかのチェックが入る(0だと例外を飛ばす)のに対して, ラムダ式ではそんなチェックもないしsortの比較関数としてインライン展開されるのが大きく違う. std::functionのときのgccの生成コードの一部を見てみる. 

    cmp QWORD PTR [rsp+128], 0 ; 0かチェック
    lea rbp, [r13-8]
    mov rdx, QWORD PTR [r13-8]
    mov rsi, QWORD PTR [r12]
    jne .L435
    jmp .L433 ; throw bad functionへ
    .p2align 4,,10
    .p2align 3
.L438:
    sub rbp, 8
    mov rdx, QWORD PTR [rbp+0]
    cmp QWORD PTR [rsp+128], 0 ; 0かチェック
    mov rsi, QWORD PTR [r12]
    je  .L433 ; throw bad functionへ

あちこちで関数呼び出しの前に0チェックが入っていることがわかる. ラムダ式の場合はそのようなチェックはない(が生成されたコードは大きい). そのような違いがあることは理解しておくとよいだろう.

7月8日_

あまりに暑くて夜中エアコンを入れた. 今年初エアコン. 先週末フィルタの掃除をしておいてよかった.

7月6日_

8/31(土)開催予定のx86/x64最適化勉強会6のatndを立てました.

今回は@k_nitadoriさんに神戸からわざわざ来ていただいて発表いただける予定です. GPGPU, x64のSSE/AVX, スーパーコンピューター京と, どのプラットフォームでも素晴らしい成果をだされていて, 2009, 2010, 2012年にゴードン・ベル賞を受賞されています. とても楽しみです.

7月3日_

8/31(土)にx86/x64最適化勉強会6を開催予定

初参加大歓迎です. 発表したい方はご連絡ください. atndは近いうちにたてます.

Japanist 2003がWindows 8に対応してる!

今までも一応入力はできていたのでどこが変わったのかまだよく分かってないけど富士通えらい.

横浜から大船に行くには大船行き(根岸線)に乗ってはいけないらしい. 予定より大幅に時間が掛かってしまった. 早く出ててよかった. 2000年頃友達んちに一度だけ大船に行ったときもめちゃくちゃ時間が掛かった記憶があるのだが, そういうわけだったのか. 13年振りに納得したw

7月2日_

最近眠たい

眠たいというか, 夕方になると体が動かない. 夜9時過ぎにはもうダウンして寝てしまうのに朝起きるのも辛い. どっか悪いのかな. こないだみてもらったときは特に何も無かったのだけど.

昔
[Back]
御意見は光成滋生<herumi@nifty.com>までお願いします