憂鬱な午後のひととき

年明けまでネットから遠ざかります. ではよいお年を.

・boost::lexical_cast<int>
C++で「遅い」のは死活問題とか言うなら一番よく使うであろう10進整数と文字列の変換に対してぐらいは専用関数が欲しいなあ. 少なくともstringstreamは無いだろうと. あと, 同じ戻り値の型推論するなら数値まで持っていってくれたほうが個人的には好み. というわけでmie_atoi.hppとテストコード(atoi_test.cpp).

// 変数の型に自動cast
int a = mie::atoi("-123");
short b = mie::atoi("32767");
int64_t c = mie::atoi("12345678901");

// 不正な値なら例外を出す
unsigned int d = mie::atoi("-123");
short e = mie::atoi("32768");
uint64_t f = mie::atoi("abc");

// 例外出さない
bool b;
int g = mie::atoi(&b, "999");
if (b) {
    ...
}

Boost.LexicalCastの改良案のベンチマーク使って比較.

    int sum = 0;
    for( int i = 0; i < c; ++i )
    {
        bool b;
        int x = mie::atoi(&b, s);
        if (b) {
            sum += x;
        }
    }

Coreduo 1.8GHz 32-bit Linux; gcc 4.4.0 -O3 -fomit-frame-pointer

	正常値	エラー値
f1()	1.05	17.57
f2()	2.31	11.9
f3()	2.31	2.03
mie::atoi()	0.06	0.01

なんというか, LL vs Cですかみたいな.
・cygwinのgccをupdateしてみた. logは多少ましになったが, expはあんまし変わってない.

Core2duo 1.8GHz 32-bit Xp; unit:cpu clock

	gcc 4.3.2	gcc 4.3.4	VC10
std::exp	147.138	134.606	79.931
fmath::exp	16.459	15.651	12.656
std::log	104.582	73.609	61.216
fmath::log	12.321	13.376	11.283
std::exp2	409.081	402.277	-
fmath::exp2	19.582	19.318	18.084

fmathにfmath::log()を追加. fmath.cppは無しにしてfmath.hppをインクルードするだけで使えるようにした(諸般の都合で結構やらしいコード:整理できたらしたいな). 32bit環境ではlog()は5～8倍速い. 64bit環境だと3～8倍. 面倒でSISDはやってない.

Core2duo 2.6GHz unit:cpu clock

	VC10@32-bit Xp	gcc 4.3.2@32-bit cygwin	VC10@64-bit Xp	gcc 4.1.2@64-bit Linux
std::logf	69.153	114.535	23.295	79.737
fmath::log	12.450	14.152	6.118	9.522

今回はテーブルを使ったので大昔に考えた方法よりは2倍ぐらい速い.
0の近傍付近で最適な近似を求めたかったのでcを固定したときに∫₀^c (log(1 + x) - (ax + b))² dxが最小となるa, bを手計算したけど誤差の扱いの都合上, 結局使わなかった.
あと, 使ったことないけどlog2やexp2も追加した. cygwinだとlog2がglobalに定義されてるので定義できなかった. しかもcygwinのexp2()は遅いexpに輪をかけて遅い. 一体何をやってんだか.

あれ, VC10のexpは/fp:fastをつけると遅くなるのか? ベンチマークのコードが問題なんだろうか. でもlogはそれなりに速くなってるしなあ. あとで調べる.

bench on Core2Duo 1.8GHz, 32bit Xp : 単位 clk

	/Ox /Oy /Ob2 /GS-(共通)	+/arch:SSE2	+/fp:fast	+/arch:SSE2 + /fp:fast
std::exp	88.473	84.458	131.846	133.310
my_exp	14.552	13.246	15.278	13.866
std::log	100.007	99.001	62.859	63.149
my_log	21.002	17.687	11.516	11.196

VC10とcygwinのgcc 4.3で比較してみた.

log bench on Core2Duo 1.8GHz : 単位 clk

	32bit VC10	32bit gcc 4.3
std::log	63.450	114.604
my_log	11.545	13.364

gccはlogも遅い. 超越関数全般苦手なんだろうか. 流石に下のコードだとSISDの意味が(特に32bitでは)あんましなさそう. 4個並列版はどうかな.

最近夜中に目が覚めてしゃあない. 一昨日は5時前に目が覚めてしかたがないので走った. 暗いので道に迷った. 今日はあまりに寒いのでランニングは嫌だからlogのテーブル引き版作ってみた. とりあえずCバージョン.

void init()
{
    for (size_t i = 0; i < (1U << LEN); i++) {
        fi fi;
        unsigned int idx = i << (23 - LEN);
        fi.i = static_cast<unsigned int>((127U << 23) | idx);
        tbl[i].app = ::logf(fi.f);
        tbl[i].rev = 1 / float((1 << 23) + idx);
    }
}

static inline float log(float x)
{
    using namespace local;
    const LogVar<>& logVar = C<>::logVar;
    const size_t logLen = logVar.LEN;

    fi fi;
    fi.f = x;
    int a = ((fi.i >> 23) & mask(8)) - 127;
    unsigned int b = fi.i & mask(23);
    unsigned int b1 = b & (mask(logLen) << (23 - logLen));
    unsigned int b2 = b & mask(23 - logLen);
    float f;
    int idx = b1 >> (23 - logLen);
    f = a * logVar.c_log2 + logVar.tbl[idx].app;
    float t = float(b2) * logVar.tbl[idx].rev;
    f = f + t;
    return f;
}

ベンチマークと簡易精度チェック.

range=[0.00, 2.00], d=1.000000e-006, N=30
   std::log sum=-604024.666667 ave=110.158clk(x1.00)
 fmath::log sum=-604024.666667 ave= 19.676clk(x5.60)

いい感じ. 次はSISD使ってコード整理してみる.

サーバに検索を依頼するとき暗号化したまま検索できるというFHE(fully homomorphic encryption)の話. 格子を使わないバージョン. ただまあ1bit送るのに一体何bit必要なのかよーわからんというか触れたくないというか. googleのcloudに使えるというプレゼンをしてたけど, 提案方式をそのまま実装してくれと言ったらgoogleの人怒るだろうなあ.

CANS 2009に来た. 飛行機の出発がやや遅れてバスの乗り継ぎ大丈夫かと思ったが待ってくれていた. で会場に着いたらみんな兼六園に行ったというので小走りで追いかける. 兼六園って, 昔来たときも台風のせいで急遽閉園になってダッシュで駆け抜けた気がする.
DNS cache poisoning attackを解決するというDepenDNSが面白そうだったけど, 質問にあったように, アカマイのサービス(先日の苦手の会で教えていただいた!)のようなDNSの結果が頻繁に変わりえるものだと前提か崩れて厳しそう.

似鳥さんにラボに来ていただいてこないだのゴードン・ベル賞の受賞内容について話していただいた. GPUとCPUの分担とか, 何も考えずにデータを流すとネットワークがパンクするとか, GPUは少しぐらい壊れてても交換してもらえないとか, 今回はやってないけどTCPプロトコル全部すっとばして直接パケットをやりとりすることもあるとか面白い話が多かった. どうもありがとうございました.

Xbyakとfmathをcygwinに対応した. ついでにmingwもと思ったけど, こちらはそもそもSIMDに対応してない?

common.mkを入れ忘れてたので追加(ご指摘ありがとうございます). cygwin対応は…, そのうちやるかなあ.

遅くなりましたが資料作りました(fmath). 酷い英語ですいません. logもそのうち整理して追加したい. 会場提供, 運営ありがとうございました.

情報科学苦手の会に参加. 豪華なメンツだったので, 行きの電車の中で資料作って空気も読まずに発表してしまった. 資料は明日置く.

ついうっかり『岩波数学辞典第4版』を注文してしまった. ちょっと楽しみ.

本社でプレゼンとデモ. すぐ続きがあるけど一応一段落. 受け付けで「ラボの光成です」と言ったら発音が悪かったか「ナガノ ミツナリさん」になってしまった.