憂鬱な午後のひととき

↓ソース更新しておいた.

今日はこまかい実装の話. 飛行機で帰る前に2時間ほど車で観光案内をしていただいた. 坂の上に教会がたくさんあるところ(場所どこだっけ?). 印象としては洋風京都(特に哲学の道付近, 大文字山からの風景)でちょっとうれしくなってしまう.

・へー(Visual Studio)
Visual Studioの括弧ジャンプはデフォルトでtemplateの<>にも対応してるのでviより使いやすいと思う.
・はこだて未来大学へ. 疲れたけど面白かった. 先生も学生の人たちもパワフルだ. 素晴らしい. 建物が7段雛飾りを箱詰めしたような, 京都駅みたいな解放感のある形. 高所恐怖症の人には辛いかも.
・GF₃上の加算演算の論理命令による最適化
をホテルに帰ってから0, 1, 2の表現を変えないパターンで試してみる. レジスタが全て壊されるので最初やったときはもとのよりも1個論理演算が減って代わりに2個movapsが増えた. 結果として(グローバルで)5%ほど遅くなった. もう一度考え直してレジスタを使い回すようにしてmovを減らしたら5%ほど速くなった.

加算方式の違いによる速度

	7命令版	6命令版その1	6命令版その2
論理演算数	7	6	6
mov数	1	2	0
ペアリング速度	-	5% speed down	5% speed up

movなんてμOPレベルで消えて関係ない, 論理演算数が減る方がよいと思っていたがそういうわけではないようだ. 結果を見る限り, このクリティカルパスではmovすら減る方がよい(その1で遅いのは依存関係が複雑になったから?), 今回は(レジスタが破壊されても)たまたまmovが減らせたけれども, もしmov数が増えてしまうなら単純に6命令版がよいとは限らないのかも. Core2Duoのデコーダが律速してるのかなあ(詳しいことはよく知らない).
cf Core 2のアーキテクチャを追求する・その4
きょうはぼやくぞ、別件だけど。(Core 2 Duoのデコード能力)

3乗根の代わりに3乗を使ってぐるっと回すってのは考えてみたのだが, うまくいかなくて13日のペアリングフォーラムではそう発言してたんだが, 「できるよ. 既にやってるよ」ってJean-Lucさんに教えていただいた. というわけで恥ずかしいのでその部分のpdfを修正. 速度的にはペアリングが1%速くなるかどうかという程度だった.

amachangさんがC++のtemplateでλ計算してるのを横目で見ていたとき, 変数に$を使っていたので驚いた. [迷信] 識別子に使える文字は英数字と下線のみによるとありなのか. 全然知らなかった. VC2008で試してみた. 面白い. gcc 4.3.0だと$はOKだが日本語はソースファイルの文字コードをUTF-8/cp932/EUCと変えて --input-charset で設定しても駄目だった. ちなみに本当の無名関数を作ってみようと全角スペースを使うとVC2008でも「使えません」. 残念, Whitespaceもどきができると思ったのに.

#include <stdio.h>
#include <boost/bind.hpp>
#include <boost/function.hpp>

struct 犬 {
    void 吠える() const { puts("わん"); }
};

int main()
{
    犬 チワワ;
    チワワ.吠える();
    boost::function<void ()> λ = boost::bind(&犬::吠える, &チワワ);
    λ();
}
---
>わん
>わん

文字列処理の勉強. boost::xpressiveはboost::regrexより速いことが多いとあったが, ごく簡単なベンチでは2.5倍ほど遅くなった. もちろんケースバイケースなんだろうが, 無条件にxpressiveというわけにはいかんようだ. それから正規表現も基礎からきちんと勉強してみよう.

Microsoft が提供する C/C++ ヘッダファイルにおける事前条件・事後条件の充実っぷりは異常
そうなんだよな. 今のところどの程度の意味を持ってるのか不明だけどstd::fill(first, last, val)のプロトタイプ宣言にも_Out_capcount_x_(last - first)といういかにもなヒントが入ってる. 他にもいろいろあって見てると面白い.

ドラマ『監査法人』
野球なんかに70分も延長するなよー. 最後の10分見られへんかったやんか.

memset()とstd::fill()だと後者の方が型情報が多い分, コンパイラはより効率のよいコードを生成するのか. 凄いなあ.

急遽, 来週の金土に, はこだて未来大学に行くことになった. 観光の時間は殆ど無いんだろうなあ.

C++のlocaleは遅くて複雑そうだし使いたくないよな, と敬遠していたが勉強してみるか.

Why not C++?(in Write gcc in C++)
の「The FSF doesn’t like it!」に対する回答が「The FSF is not writing the code.」てのが笑った.

『初恋』(トゥルゲーネフ 沼野恭子訳)
実は読んだの初めてだったりする. なかなか新鮮だった. ちょっとお気に入りの『十八の夏』(光原百合)の表題作って実はこれをベースにしたものだったのだろうか. それとも単なる偶然?

ややせこいが二桁台に突入記念で very fast etaT pairing for Core 2 Duo更新.
今日のペアリングフォーラムでのプレゼン資料も置きました.
Linux用のmulti thread版は単にWin32のEvent相当のものをMIE::MIE_EVENTクラスとして実装するだけ. やってないのは速いはずのbusy loopで遅かったから, というかVMwareでしか手元に環境が無いので試せないから.
秋葉原の帰りで間違えて千葉方面の電車に乗っちゃった. 満員でなかなか降りられず大変だった.

明日明後日は予定が詰まってる. てことは金曜日のペアリングフォーラムの資料はいつ作るんだろう.

Intel Coreのメモリアクセスについて
本題からはずれるが元のコードでstep=0のとき速かったのは, divの処理時間が入力値によって変わるからかなと思ってたが, 実際のところどうなんだろうとベンチをとってみた.

int divloop(int offset, int step, int dividend, size_t count)
{
  int ret = 0;
  int x = offset;
  for (size_t i = 0; i < count; i++) {
    ret += x / dividend;
    x += step;
  }
  return ret;
}

これを各種パラメータを変更しながら実行する(memtest.cpp).

1回あたりのループの処理時間比(Core2Duo 2.6GHz + Xp)

step	dividend	offset
		0	1	4	17	1025	524288
0	1	4.53	4.53	4.53	4.53	7.65	10.62
1	1	13.12	13.13	13.13	13.12	13.13	13.13
0	17	4.53	4.53	4.53	4.54	7.65	10.62
1	17	13.13	13.13	13.12	13.12	13.13	13.13
0	1024	1.87	1.87	1.88	1.88	4.53	7.65
1	1024	10.16	10.16	10.15	10.15	10.16	10.16
0	1029	1.87	1.87	1.88	1.88	4.53	7.65
1	1029	10.16	10.16	10.16	10.15	10.15	10.16
0	1234567	1.88	1.87	1.87	1.88	1.88	4.53
1	1234567	7.18	7.19	7.19	7.19	7.19	7.19

stepが0と1で明らかに違う. step=0でも524288/1や524288/17は重たいことからやはり大きい数の割り算は時間がかかることがわかる. stepがあるとき遅くなるのはxが段々大きくなるから(ベンチとるとき平均化されてる)だろう.

またやな事件が起こったな. 被害者やその家族のことを考えるとやりきれない. こういうのは気をつけていて防げるというものでもないから恐ろしい.

昨日は降車駅を寝過ごしてしまった. かなりのお疲れモードだった模様. といいつつやってしまった(fast strlen and memchr by SSE2)
ベンチとるまでまさかgccのstrlen()が遅いとは思わなかった. やってみるもんやね.
少しコードの説明. SIMDにはbyte単位ごとに(x ? 0xFF : 0)を実行することができるので16, 32byteごとにそれを実行し, ターゲットのbyte(strlenなら0)を見つける戦略をとる. その後_mm_movemask_epi8を用いてbyte単位ごとにその最上位ビットを通常のレジスタaに集約する. 最後にbsf命令を使いaを下位から眺めて初めて0になった場所を見つければ完了. これは常套手段.
(参考)
・Range Coder の展開速度を SSE で高速化
・SEA & FSIJ 合同フォーラムでの発表資料

・Xbyak
mov(ptr[eax],1);などのオペランドサイズ不定な場合に正しくエラーを出すように修正. ご指摘ありがとうございました&はまらせてすいません. > shinhさん
・期待はずれ
やや強気で言うなら, どんな手段であろうと速くなるなら(ことライブラリにおいては)正義だと思うが(アルゴリズムの改良で10%速くなるより実装技術で2倍速くなる方がいい), もとのアセンブリ言語が酷すぎる. K6の頃に既に「86時代の過去の遺物だ, 使うな」と言われていたloopnzなど使ったものと比較するなんて.
Lists of instruction latencies throughputs and micro-operation breakdowns for Intel and AMD CPU'sとか見た方がいい. 最初見たときは, どこぞの古い記事みたく発掘されたものかと思った.

ラボでは21インチUXGA+ノートPCで満足, デュアルはあまり好きやないので自宅では24インチワイドWUXGA使ってるとか話してたら, 若干伝言ゲームになったのか本社に行ったら27インチワイド?の巨大モニタが調達されていた. なんてでっかい. ありがたいことだが, でかすぎて机の奥行きが足りない(自宅ですら机とモニタ置き場は離れてる). 隣はトリプルモニタしてたよ.

一段落した. 今度は暫くstrstrをいじってみる. うまくいけば一般化を狙う.

Yajit
ちょっと遅くなりましたがユーザが指定したメモリ上にコード生成できるようにXbyakを修正しました. 後CodeArray::protect()とCodeArray::getAlignedAddress()をpublicにした. x86_64で確認したいが, そもそもVC x86でもruby/signal.hが無いとかでエラーになったところで時間が無くなった. 週末遊べたらいいなあ.