こちらに移動しました．
http://hpcgi1.nifty.com/herumi/bbs.cgi

> URL入力覧と同一のURLがメッセージ覧に入っているとNGにする、とか。
いや，これはniftyが提供するcgiなので何もカスタマイズできんのですよ．適当によさそうなのを探してみます．

URL入力覧と同一のURLがメッセージ覧に入っているとNGにする、とか。

不真面目解答の一つ
#define issigned(x) ('u' != 0[#x])

もう少し真面目に
#define issigned(x) ((x)-2<0)
を考えたんだけど、us/ucでコケますね。さらに大真面目に、

int is_type(char const *s) {
return
(!strcmp(s, "char")) || (!strcmp(s, "signed char")) || (!strcmp(s, "unsigned char")) ||
(!strcmp(s, "short")) || (!strcmp(s, "signed short")) || (!strcmp(s, "unsigned short")) ||
(!strcmp(s, "int")) || (!strcmp(s, "signed int")) || (!strcmp(s, "unsigned int")) ||
(!strcmp(s, "long")) || (!strcmp(s, "signed long")) || (!strcmp(s, "unsigned long"));
}

#define issigned(x) (is_type(#x)? ((x)-1<0): (※※※))

を考えているんですが※※※が埋まらん。

> 結果はdiskの性能に律速されるという味気ない結果に終わりましたが(笑)．
本当に500GBの情報にフルにアクセスしたい話じゃぁキャッシュも効かんだろうし、それはしょうがないかと。

> > メモリマップドファイルという手はいかがでしょうか。
> > って、書き込みの高速化の話じゃなかったですね（笑）
> 500GBではRAMディスクは無理でしょうね...。

わかりにくい表現ですみませんでした。
「mmap()を使えば」ということを言いたかったのです。

で、実際に試してみましたが芳しくありませんでした。
（x86 Linux機の調子が悪くて、
CygwinとDebian 玄箱HGでしか試してませんが）

コードの書き方が悪いような気もしますが、
素直にwrite()やfwrite()を使ったほうが速いという結果に。

やっぱりmmap()とmunmap()は繰り返して使うようなものでは
なかったみたいでして…。

64 bits CPU/OSなら500GBでも1回でマップできるのでしょうかね。

> O_RDWR以外にメモリマップドファイルという手はいかがでしょうか。
> って、書き込みの高速化の話じゃなかったですね（笑）

いえ，一番速く書き込めるのはどういう手法か?というのがそもそもの発端だったので，それは正しいのです．
結果はdiskの性能に律速されるという味気ない結果に終わりましたが(笑)．
データはまた近い内にでも．

> O_RDWR以外に
O_RDWRしてもopen時かread/write時に待たされるには違いないでしょうね。

> メモリマップドファイルという手はいかがでしょうか。
> って、書き込みの高速化の話じゃなかったですね（笑）
500GBではRAMディスクは無理でしょうね...。

> > あまり詳しくないですが，FATだと先頭のフラグだけ落とせばよいから速いんでしょうね．
本件はFATでもversion1.0(MS-DOS1.0くらいの最初のバージョン：階層ディレクトリのないやつ)、とかMFS(Macintosh File System -- フォルダがディレクトリではなく単なるUIであった時代)とかの階層ディレクトリのない原始的なファイルシステムを実装するのが良いかと思います。
結論は結局同じですが....。

> 返事が遅れてすいません．

いえいえ、お気になさらずに。

> これも最初に試していたのですがopen時にremoveするようで，そこで待たされてしまいます．

やっぱりそうですか。残念。

> 改めてopen()のオプションを見直したのですけど，ファイルを切り詰めずにデータの内容だけ変更する方法ってないんですね．

O_RDWR以外にメモリマップドファイルという手はいかがでしょうか。
って、書き込みの高速化の話じゃなかったですね（笑）

> あまり詳しくないですが，FATだと先頭のフラグだけ落とせばよいから速いんでしょうね．

FATの場合は管理領域が固まって配置されてますしね。

付け焼刃的知識でいうと
ext2の場合はブロックグループごとに管理情報が点在しているので、
単一の巨大ファイルには弱いみたいです。

＃他のFSではReiserFSが削除に強いというのを見かけました。

> > O_RDWRじゃだめ？

本当ですね．えらいお馬鹿なことを書いてしまいました．
#普通に使ってたはずなのになんでそんな勘違いをしてしまったか．

> > 改めてopen()のオプションを見直したのですけど，ファイルを切り詰めずにデータの内容だけ変更する方法ってないんですね．
> O_RDWRじゃだめ？
% echo '0123456789' > a.txt
としておいて、
#include <fcntl.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>

int
main() {
int fd = open("a.txt", O_RDWR, 0644);
write(fd, "ab", 2);
close(fd);
return 0;
}
こんなプログラムを走らせると、
% cat a.txt
ab23456789

こんな風になりますが、違いますか？

> 改めてopen()のオプションを見直したのですけど，ファイルを切り詰めずにデータの内容だけ変更する方法ってないんですね．
O_RDWRじゃだめ？

> もう試されているような気もしますが、
> 0バイトファイルを上書きコピーとかもダメですかね。

返事が遅れてすいません．
これも最初に試していたのですがopen時にremoveするようで，そこで待たされてしまいます．
改めてopen()のオプションを見直したのですけど，ファイルを切り詰めずにデータの内容だけ変更する方法ってないんですね．

あまり詳しくないですが，FATだと先頭のフラグだけ落とせばよいから速いんでしょうね．

もう試されているような気もしますが、
0バイトファイルを上書きコピーとかもダメですかね。

ext2にこだわらないなら
ReiserFSとかXFSとかJFSとかを試してみるとか
いかがでしょうか。

うーん、ファイルシステムはFATくらいしか
内部構成をしらないのでお役に立てなそうです。

FAT系なら一瞬で消せるような気がするんですが。

＃いい機会なのでFSに関してちょっと勉強してみようかな

ファイルの大きさが決まっててなおかつ1個限定なら、ファイルシステムを作らないでHDDを使っちゃったらダメですか？
そのHDDのデバイス特殊ファイルは /dev 以下に置く必要もなくて、置きたいところに mknod すればいいし。

500GB分のファイルを、という話ならmke2fsしたほうが速いです。i-node数を減らすなどの調整で、もっと速くなると思うし。

以前投稿した時の前提条件が逆だったようです。
xが前回と異なった場合基本的には1、例外1 or 4では0を返すように動作させたかったということです。

int ans2(int x)
{
static const uint32 D = (1 << 4) | (1 << 1);
static uint32 s = 0;
uint32 m = 1 << x;
s ^= m;
s &= m;
uint32 r = (s ^ (D & m));// (1)
return r;
}

これが私のたどりついた形でした。
D の条件が無ければ (1)は消えて r = s のすっきりした形になります。

へるみさんのコードからアイデアを盗むとこんな感じですかね。

void onColumnHeaderPressed(int sort_column)
{
　　const unsigned DEFAULT = (1 << 4) | (1 << 1);

　　static unsigned state = DEFAULT;
　　unsigned mask = 1 << sort_column;

　　unsigned a = state & mask;
　　state = ~a & (DEFAULT | mask);

　　SortbyColumn(sort_column, a);
}


なにやら、正解にかなり近づいた感じがします。
（違ってたりして…）


あと、いまさらですが、1751の
> unsigned mask = 1 << x;
は
> unsigned mask = 1 << sort_column;
です。見事にコピペーミスですね。


さて、2度寝、2度寝（笑）

> s = (s | ~pm) & (D | pm);

は、その回のxに依存していないので、
前の回に先行して計算しておけると思います。
（と考えて、私は
state = a | (DEFAULT & (~mask));
としてました）

これで static 変数へのアクセスが2つ減るので、
ちょっとは早くなる…はず…かな…といいなぁ…とか思ってます。
実測はしてません（笑）


しかしなるほど、全体ビットを反転させればいいんですね。

私の場合、xに依存したビットだけ反転させようとする分、
無駄が多かったみたいです。

私も作ってみました．

int mie(int x)
{
static uint32 D = ~((1 << 4) | (1 << 1));
static uint32 s = 0;
static uint32 pm = 0;
uint32 m = 1 << x;

s = (s | ~pm) & (D | pm);
s = ~s & m;
pm = m;
return s;
}

>コラム数がたかだか10程度で
この条件からbitパターンに置き換える発想はでませんでした(^^;
ただ，なんか微妙に変数が足りてない気がします．
x =- sort_columnではなさそうですし，どうだったのかな．

厳しい意見はdskさんにお任せして（笑）、
ちょっとやってみました。

0 <= sort_column < sizeof(unsigned)で、
元ソースのsort_orderはstaticの修飾＆初期化ありと仮定してます。

void onColumnHeaderPressed(int sort_column)
{
　　const unsigned DEFAULT = ~((1 << 4) | (1 << 1));

　　static unsigned state = DEFAULT;
　　unsigned mask = 1 << x;

　　unsigned a = (state ^ mask) & mask;
　　state = a | (DEFAULT & (~mask));

　　SortbyColumn(sort_column, a);
}

なにやら、maskの出現率が高いのが気になるところ。
その辺をもうちょっとがんばれるかなと思いますが、今日はここまでで。

昇順か降順を決定することよりも、ソート自身の負荷の方が通常高いためここは速度よりも可読性を重視してビット演算は用いないのが筋だと思います。
また、通常は、sort_orderやprev_sort_columnはテーブルクラスのメンバー変数であり、void onColumnHeaderPressed(int)や、SortbyColumn()は同じくメンバー関数であるべきだと思います。
そうすると、メンバー変数はprev_sort_columnじゃなくてsort_columnとして、SortbyColumn()は引数なしで良いなど、設計を見直した方が良いと思います。

指定したコラムで表をソートする関数
SortbyColumn(sort_column, sort_order);
があって、sort_order は 0 の場合は昇順ソート,それ以外の場合は降順ソートとします。

コラムヘッダ(MS Excelで言うところの上の"A","B",..と書いてある部分)をユーザがクリックしたら、そのコラム番号を引数としてコールバック関数onColumnHeaderPressed()が呼ばれて
(a)前回クリックしたヘッダと同じだったらソート方向を前回の逆でソートする。
(b)違う場合は、1番目と4番目は降順、それ以外は昇順でソートする
という動作にしたいとします。

ここでコラム数がたかだか10程度で、ビット演算を使って下の関数を書くとすると、みなさんはどうされるでしょうか?

void onColumnHeaderPressed(int sort_column)
{
unsigned int sort_order;
static int prev_sort_column = -1;

if (sort_column == prev_sort_column) {
sort_order = (sort_order + 1) % 2;
} else {
prev_sort_column = sort_column;
if (sort_column == 1 || sort_column == 4) {
sort_order = 1;
} else {
sort_order = 0;
}
}
SortbyColumn(sort_column, sort_order);
}

> 小次郎さんだから縛りを入れてるんだろなとは思ってました．
> CPUの条件を言っておけばよかったですね．

こちらが勝手にやっていることなので気にしないでくださいね。

ちなみに同じ縛りのまま、もうちょっとがんばってみたのですが成果なしでした。
悔しい日々が続いております。

> ただ，まさか1日で答えがでてくるとは思いませんでしたが(笑)．
> 「できる」という事実がない状態(&オリジナルはもっと複雑)だったと言い訳しますが，私は3〜4日はかかりましたよ(^^;

「できる」というのが分かっているのは非常に大きいですよね。
なんといっても、やる気がおきますから。

あとは、ソースだけではなくて、
その意味も分かっていた（29日の記事があった）ことが大きかったです。
苦手なんですよね、（過去に自分の書いたのを含めて）ソースを読むこと。

でも、一番大きかったのは「仕事」じゃなくて
「クイズ」だったことかもしれません（笑）

しかし、時間的には2日分はかかってますし、その上正解には到達してませんから、
まだまだ、精進が必要なようです。

また、クイズを出してもらえることを楽しみにしてます。

> あ，すいません．"何故だろう"は"sに依存しない"ではなく"FindBit()の引数の話"のつもりでした.
でしたら、引数はsに依存しません。条件の範囲では
((Max - a)|b)^Max == 〜(〜a| b) が成立します。

> 言いたいことは分かりますが"線型な比較"って初めて聞きました．
> ただa, bの比較はちょっと違うような．
「線型な式と0との比較」と言えばよかったかも。aとbは比較されてないし、比較されていても違わないですよね。

> 私の場合、とりあえず考えやすいように
> 三角形を上下反転（ Max - a ）させていたのを
> そのまま実装してしまったので、 FindBit() の引数が
> ((Max - a) | b) ^ Max になっています。

なるほど．

> ちなみに FindBit() は勝手に
> 「FPUがないくらいでも動くポータビリティ」を
> 重視ということで、 bsr と float の使用は避けていました。

小次郎さんだから縛りを入れてるんだろなとは思ってました．
CPUの条件を言っておけばよかったですね．

> ところで、私は最適化を実際に挑戦してみたので、
> 正解の意味がわかるんですが、他の方はすぐわかるものなんですかね。

どうなんでしょうね．
ただ，まさか1日で答えがでてくるとは思いませんでしたが(笑)．
「できる」という事実がない状態(&オリジナルはもっと複雑)だったと言い訳しますが，私は3〜4日はかかりましたよ(^^;

> もとの式を見れば、Qは、1<<sであり、

あ，すいません．"何故だろう"は"sに依存しない"ではなく"FindBit()の引数の話"のつもりでした.

言いたいことは分かりますが"線型な比較"って初めて聞きました．
ただa, bの比較はちょっと違うような．

私の場合、とりあえず考えやすいように
三角形を上下反転（ Max - a ）させていたのを
そのまま実装してしまったので、 FindBit() の引数が
((Max - a) | b) ^ Max になっています。

少なくとも、左右反転（ Max - b ）すれば、
a & (Max - b) で済んだんですけどね。
（と日曜日に気づきました）

どちらにしろ、a <= b の範囲を
「無駄に」対処してしまっているのが敗因でしょうか。


ちなみに FindBit() は勝手に
「FPUがないくらいでも動くポータビリティ」を
重視ということで、 bsr と float の使用は避けていました。

まだ、C言語だけでもうちょっと早くできないものかと思ってます。

＃と思いつつ、土日は新しく手に入れたMIPS-Linuxマシンで遊んでましたが（笑）


ところで、私は最適化を実際に挑戦してみたので、
正解の意味がわかるんですが、他の方はすぐわかるものなんですかね。

私の場合、（Q2 <= a < Q3 && Q <= b < Q2）の正方形の move は
今回の場合は quit と同義であることとか、
n は b をビットシフトしたものになるとか
ちょっと考えないとわからなかったのですが。

無惨に敗退してしまったdskです。ここで挽回をば。
＞ 面白いことに s に依存してません. FindBit()の引数が異なるのですが結果は同じっぽいですね. 何故だろう.

もとの式を見れば、Qは、1<<sであり、
sが1増える毎に、関数中の、Q, Q2, Q3, a, b はどれも2倍されますね。
それで、これら5つの変数の間の線型な比較しかありませんから、sの値に
かかわらず比較結果は同じ、すなわちsに依存しない。

よって関数の戻り値はsに依存しない。

テーブル大好きdskです。

inline int FindBit(int a)
{
int const tbl[] = {
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
};
int y = tbl[(unsigned int)a >> 24];
if(y) return y+24; else y = tbl[(unsigned int)(a&0xffffff) >> 16];
if(y) return y+16; else y = tbl[(unsigned int)(a&0xffff) >> 8];
if(y) return y+8;
return tbl[(unsigned int)(a&0xff)];
}

駄目ですか？

徹夜お疲れさまです．

>「ハッシュにキャッシュする実装」（4096エントリのときに1.67倍速くらい）を超えられなかったのが

テーブル引きは意外と強いですよね．私も以前bitcount()が古典的な実装よりはbyte単位のテーブル引きの方が強いことを知ってびっくりしました．

FindBit()はもっと簡単にできますね．

29日分の記事プラス 0 < b < a < (4 << s) の前提で考えてみました。

inline int FindBit(int a)
{
unsigned x = (unsigned) a;
if (x == 0) { return 0; }
unsigned y;
int n = 1;
y = x & 0xffff0000; if (y != 0) { x = y; n += 16; }
y = x & 0xff00ff00; if (y != 0) { x = y; n += 8; }
y = x & 0xf0f0f0f0; if (y != 0) { x = y; n += 4; }
y = x & 0xcccccccc; if (y != 0) { x = y; n += 2; }
y = x & 0xaaaaaaaa; if (y != 0) { x = y; n += 1; }
return n;
}

int calc(int a, int b, int s)
{
const int Max = (4 << s) - 1;
int l = FindBit(((Max - a) | b) ^ Max);
int n = b >> l;

return n;
}

とりあえず、これで元の1.42倍くらいにはなりました。
（スペースの都合上、普段より改行してないです）

あとはFindBit()をどうにかする方向で考えてますが、
寝て起きてからの話になります。

しかし、徹夜した割りに「ハッシュにキャッシュする実装」
（4096エントリのときに1.67倍速くらい）を
超えられなかったのが非常に悔しいです。

キャッシュの有効性はsの変動やループの回数次第なので
実際のところはわからないんですけど。

9月28日のだけでちょっとやってみましたが、惨敗。

一番効果があったのが、「*2」を和にしたことだったという始末でした。
（Visual Studio .net 2003のコンパイラで）

悔しいのでハッシュテーブルにキャッシュするようにしたら、
2倍速にはなりましたが、なにやらズルイ手でしてくやしいですね。

29日分の記事を見て再挑戦してみます。

ところで、b < a以外にaとbに条件がありますでしょうか。

> 多分なし．というか「出力なし」はネタではなく，まじでして，
ということは....
昔 UCC (Ultimate C Compiler)というネタ(あなたのプログラムを最適化すると
何もなくなりました、という旨のWarningが出て何も出力されない、というもの）
がありましたが、UCCでコンパイルすれば完璧ですね。

> ところで、softwireはありなの？

多分なし．というか「出力なし」はネタではなく，まじでして，でも「精度を変えるな」(たとえばdouble->floatは不可)といい，更にオリジナルは入力が全て0なので演算結果も全て0で，更に更に足し算の順序を入れ換えることによる演算誤差などをどこまで許容するかの正当性確認手段を主催者側が明示的に提供していないという，はっきりいって駄目駄目コンテストです．

ものすごく昔でC++トランスレータとかあったころだとC++の拡張子は
大文字Cのみ、という習慣だったと思う.....。その後gcc系はcc、Windows系
はcpp、Mac系はcpというように拡張子の氾濫がはじまったような気がします。

ところで、softwireはありなの？

> というか，やはりせっかくコンテストするならなんでもありにして欲しいなあと．C++のみならsoftwireでも埋め込んでやるか(笑)．

ですねぇ。コンパイラがどんなコード吐いたかチェックしながらってのも面倒ですし。
ここは一つなんでもありな方向で(^^;ぇ

> _ASMが使えなくて_inlineでハンドアセンブルしたなぁ・・と
> 昔を懐かしんでみる（笑

3DNow!に対応してないころは自前でアセンブラ作ってました．
というか，やはりせっかくコンテストするならなんでもありにして欲しいなあと．C++のみならsoftwireでも埋め込んでやるか(笑)．

_ASMが使えなくて_inlineでハンドアセンブルしたなぁ・・と
昔を懐かしんでみる（笑

> 外部アセンブラ禁止, インラインアセンブラ禁止
うわ、・・・ひでえ。

僕がVC++の使い方をがんばって覚えたのは
アセンブラを使うためでした。
インラインという手軽な手段があったので。

> 測定に関する注意点の四つ目には「基準となる非改造プログラム・非改造ハードウェアでの実行で得られた結果と改造したもの」って書いてあるからオーバークロックもありなんじゃないのかな．
それはあり、なんだけど、その場合、先に指摘した事項により、「非改造プログラムの速度測定もオーバクロックで測らないと駄目」なんじゃないでしょうか？

測定に関する注意点の四つ目には「基準となる非改造プログラム・非改造ハードウェアでの実行で得られた結果と改造したもの」って書いてあるからオーバークロックもありなんじゃないのかな．

オーバークロックは関係ないみたい。
＞ ハードウェアのクロックを下げたものを基準にした速度向上率は、正規の結果とは認められません。
言い方がひねくれてるけど。クロックは改造前の測定と改造後の測定で同じでないとだめ、ということでは？

副作用を持つ式の値を、同じ式（正確には同一の副作用完了点間の範囲）で参照したら未定義(コンパイラはどういう動作をしても良い)です。
gcc (4.01) -Wall では「未定義である」というwarning
operation on 'i' may be undefined
が出るようです。

馬で帰ると遠回りだね

ドキュメントが足りないなぁと思ったら、そう思った人が整備するのがこういうフリーソフトウェアの世界のルールだと思っています。それで、適切な文書がいまだに無いのは、きっとだれもそんなこと思わなかったのでしょう。私も、そんなに思わないので、必要なときに必要なだけちょこちょことソースを読んでやってます。あと、新しいカーネルのほうがデバイスドライバを書きはじめるのは楽な気がします。

そういえば、ビデオキャプチャー関係のドライバは、昔(v4lよりもずっと前)からぐちゃぐちゃな気がするんですが、気のせいでしょうか。そーいうもんだと思って改造してだましだまし使ってましたけど...

> 構造の似たデバイスドライバのファイルを探しだし、それが2.4系から2.6系に移植されたときにどのように変わったかを見れば、なんとなく移植できると思います。

ええ，移植自体はそれほど難しくないとは思うのですが(それでも割り込み周りの登録関数が名前もAPIもころっと変わっていて困りますが)，何がどう変わったのかの情報が殆ど見当たらず，それが不思議でした．
#http://ezs.kr.hsnr.de/TreiberBuch/html/sec.porting01.html
#のような日本語のページが無いという意味です．

あと，今のドライバが起動時に怪しいメモリの使い方をするPCIドライバなのでarch/i386以下を少しまじめに読み始めたのですが，グローバル変数多すぎてわけわかんない(泣)．

いろいろ探している内に当時もりあがったらしい(本当に浦島だ)
「Goodby, Linux」
http://www.wnishida.com/~wmemo/?date=20040701
や「作る人、伝える人」
http://www.yamdas.org/column/technique/friction.html
に行き当たり，しみじみと読んでしまいました．

構造の似たデバイスドライバのファイルを探しだし、それが2.4系から2.6系に移植されたときにどのように変わったかを見れば、なんとなく移植できると思います。メモリとかPCIとかUSB周りが大きく変わったような気もするけど、そんなに移行は難しくないと思います。

>先日コメント書いて、こちらで消しました
> 間違って消したのではないです。。
> 勘違いさせてしまったみたいで、どうもすみません。。。

あ，いえわざわざすいません．間違って消したので
なければよいです．

友達には言ってなかったのに見たという方が
意外と多くてびっくりしました．

先日コメント書いて、こちらで消しました
間違って消したのではないです。。
勘違いさせてしまったみたいで、どうもすみません。。。
SMW の御三方がお揃いになるのは、
RSA 揃うくらい貴重かなと思いました。。
（ねむかったので、タイマー録画しておいて後で見ました）

2006年6月20日放送内容
ハイライト：”暗号”があなたの情報を守る
http://www.tv-tokyo.co.jp/wbs/

どなかたコメント書いてくださってたと思うのですが，スパム消すときに間違って消してしまってたらごめんなさい．

ご無沙汰してます．

> Caps Lockと左CTRLの入れ替えの問題ですが、多分USB-PS2変換アダプタが原因だと思います。

そうなのですか．通常使用は問題ないので仕方ないのでしょうね．

> ELECOMのKVM-U24というATENのOEMのKVM切り替え器だけは普通に動きます。

情報ありがとうございます．早速購入…と思ったら最安値で1万円ですか．おいそれとは買えないですね．

> 個人的には
>...

私も同じです．ファンクションキーに加えてWinキーも欲しかったり．

ご無沙汰しております。

Caps Lockと左CTRLの入れ替えの問題ですが、多分USB-PS2変換アダプタが原因だと思います。

FKB8744-607のほか、IBMのSpaceSaver 2でも発生します。
（詳しくは忘れたのですが、FILCOのFKB-82PROやメーカー不明の82キーキーボードでも発生した覚えも）

変換アダプタも5種類試した限り、純粋な変換アダプタ3種、KVM切り替え器内蔵1種とほとんどNGなのですが、
ELECOMのKVM-U24というATENのOEMのKVM切り替え器だけは普通に動きます。
（OSはWindows2000/Pro/Linuxで確認してます）

回避手段としてはUSBキーボードにしてしまうというのが楽なんでしょうけど、
個人的には
・日本語配列
・非パンタグラフ
・カーソルキーが独立
・ファンクションキー必須
という嗜好なので、USB接続のものだと高いRealforce91くらいしかなくて困ってます。

# USB版SpaceSaverを買っておけばよかった人

> > 手持ちで測ると7.5clk@P4, 11clk@P4Dと結構かかりました．
>
> 調べたらP4のcmovはレイテンシが6clkでした（pentoptより）。
> P4D（というかPrescott？）では更に遅いのですかね？

すいません，微妙に測定間違ってました．それぞれ6clk@P4, 9clk@P4Dでした．でもcmovbe esi, ediを2回続けると12clk@P4, 19clk@P4Dだったので，P4Dで遅いのは確かなようです．

PenMでは、decをsubにすると2.6clk、cmovebeを無くすと1.5clkでした。

> 手持ちで測ると7.5clk@P4, 11clk@P4Dと結構かかりました．

調べたらP4のcmovはレイテンシが6clkでした（pentoptより）。
P4D（というかPrescott？）では更に遅いのですかね？
なぜこんなに遅いのかわかりませんが、遅いのはcmovのせいと
思われます。

cmovbeをなくしたときのP4Dの速さ（P4の遅さ）が気になりますね。

> P4では確かに8clkかかりましたがP4Dでは4clkで済むようです．

4clkとはまた半端な速さですね。特定のシフトの高速化でしょうか。

> つまり、P4でdecが遅いのは、フラグストールのためではなく、
> 単純にdecが遅いからです。

そうでしたか．

> PentiumMで、パーシャルフラグストールのため9clk/loopもかかります。
> P4では、おそらく高速に（ストールなしに）回ると思います。

手持ちで測ると7.5clk@P4, 11clk@P4Dと結構かかりました．
ストールしているようです．ちなみにdecをsubにするとそれぞれ7, 10．cmovebeを無くすと4, 1.5でした．

> 代わりにこれが8clkもかかるらしいです。
> alとahなどが別レジスタにマップされてないと思われます。
> mov bh,al
> mov al,bh

P4では確かに8clkかかりましたがP4Dでは4clkで済むようです．
うーん，ややこしい．

>実測する限りでは私も変わらないよなあって思ってます
いや変わらないのではなくて、パーシャルアクセスが速いのです。
その代わり普段から0.5clkだけレイテンシが長いのだと思います。

つまり、P4でdecが遅いのは、フラグストールのためではなく、
単純にdecが遅いからです。

lp:
cmovbe esi,edi ;CFとZFの両方を使う
cmp eax,ebx ;CFとZFの両方を変える
dec ecx ;CFを変えずにZFを変える
jnz lp
PentiumMで、パーシャルフラグストールのため9clk/loopもかかります。
P4では、おそらく高速に（ストールなしに）回ると思います。

ちなみに以前実測した限りでは、
普通のパーシャルレジスタストールもP4では起こりません。
代わりにこれが8clkもかかるらしいです。
alとahなどが別レジスタにマップされてないと思われます。
mov bh,al
mov al,bh

>> P4M
>これはPentiumMのことですよね？

そうです．失礼しました．

>モバイル用Pen4-Mは普通のPen4と同じはずですし。
同じなんですが，メモリが遅いことが多くて実際上は(P4DやPentiumMとも)違うコードじゃないと駄目なこともあったり．

>同じコードを食わせてもP4ではストールしませんでした。

ええ，実測する限りでは私も変わらないよなあって思ってます．
でも
http://developer.intel.com/design/pentium4/manuals/index_new.htm
の一番下の『Architecture Optimization Reference Manual』の
2-75には
>inc and dec instructions should be replaced with an add or sub instruction,
って書かれているんですよね．

#メールアドレス要求は微妙にスパムが減っただけか…

> P4M
これはPentiumMのことですよね？
モバイル用Pen4-Mは普通のPen4と同じはずですし。
PentiumMではMMX→SSE2の効果が薄いですよね。

> 実際問題遅くなることってありますかね．
試したことないですが、どうせレイテンシ0.5clkの差ですからね。
依存関係も緩いでしょうし、あまり関係ないように思います。

>パーシャルレジスタストール発生
これはP6等で起こることで、P4ではパーシャルフラグストールを
起こらないようにしているからレイテンシが伸びたのだと思います。

P6では場合によってdecでパーシャルフラグストールしますが、
同じコードを食わせてもP4ではストールしませんでした。
（過去のことなので記憶違いだったらすみません。後で確認します）

P4MはP4とかなり違うのでとまどったり面倒だったりすることが多いです．こないだもある処理をSSE2化してP4Dで速くなってよろこんでいたのに，P4Mで測ったら逆に遅くなっていて困りました．

ところでP4のマニュアルにはdecは使うな(パーシャルレジスタストール発生)とあるのですが，ついつい使ってしまいます．
実際問題遅くなることってありますかね．

L2キャッシュからシーケンシャルリードするとします。
例えば、このような処理です。
（esiは64（=キャッシュラインサイズ）の倍数とする）
lp:
prefetcht0 [esi+64]
padd xmm0,[esi]
padd xmm0,[esi+16]
padd xmm0,[esi+32]
padd xmm0,[esi+48]
add esi,64
dec ecx
jnz lp

ところが、PentiumMではこちらの方が少し速いのです。
lp:
padd xmm0,[esi+64] ; ここで次のラインをプリフェッチ
padd xmm0,[esi+16]
padd xmm0,[esi+32]
padd xmm0,[esi+48]
add esi,64
dec ecx
jnz lp

上のコードで12clk/loop、下のコードで11clk/loop。
プリフェッチなしで14clk/loopくらいです。
だから何だというわけではないですが。

> s.hの最後に
> template<class T, int n>
> A<n> B<T, n>::s_;
> を追加し、s.cppをなくすのが正解のはずです。

シュリンク版でもライブラリの方でもうまく行きました．
ありがとうございます．普通のクラスのstaticメンバは*.cppを無くすのはできないのにtemplateだとできるんですね．変なの．

s.hの最後に
template<class T, int n>
A<n> B<T, n>::s_;
を追加し、s.cppをなくすのが正解のはずです。
これで、必要に応じてstaticメンバーs_をtemplateのインスタンス(すなわちclass)一つにつき一つ生成してくれるはず。明示的な特殊化も実体化も不要ですよね？

C++PL3の14.7.2/7より

The explicit instantiation of a class template specialization
implies the instantiation of all of its members not previously
explicitly specialized in the translation unit containing the
explicit instantiation.

ということで、template<class T, int n> A<n> B<T, n>::s_;さえやっとけば
class B<double, 10>が必要になった時点で、自動的にB<double, 10>::s_も生成されるということらしいです(all of its membersなのでstaticメンバ変数も例外じゃない）。

＃元sourceの作者なのに全く覚えてない... たぶん当時上記を理解していなかったので間違ったコード書いてます。後で時間作って修正します。

それにしてもgcc3で速度差が出ているのは何故でしょう？

VCやgccではsetjmpとexceptionの実装はほとんど同じだと思います。
C++のexceptionの仕様はかなりしょぼくて、exceptionを使う場合はよほど注意して作らないとメモリリークします。機能的にもほとんどsetjmpと変わりませんから。違いは、
・setjmpよりも見やすく書ける(if(setjmp(...)...よりもtry/catch構文の方が
みやすいでしょう）。
・自分でグローバル変数(jmp_buf)を定義しなくてもよい。
・setjmpの返り値はintしか許さないが、exceptionはobjectをthrowできる。
くらいのものでしょうか。throwしたオブジェクトより外側のスコープにあるauto変数のディストラクタは呼ばれますが、throwしたオブジェクト自信のディストラクタは呼ばれません。特に、
・コンストラクタでは何もnewしないこと
・コンストラクタではthrowしないこと
ということにしないとメモリリークの防ぎようがありません(ウルトラCで防げるかも知れませんが...)。

> プロテクトうんぬんもそういう処理系だったからそういうテクニックがうまれたのであって，区別しない処理計を否定する理由にはならないでしょう．
それは問題のすりかえでは？Aという書き方とBという書き方が同じか？違うか？という議論においては、それが区別される場合が一つでもあればそれは「違う」が正解ですよね。という意味で例を挙げたまでです。
プログラマが通常ならば static int const a[] と書くところを、わざわざ（CやC++においてはプログラマは賢いので、staticを書き忘れるということは仮定しません） int const a[] とした訳なんだからそれには何か理由があってしかるべきです。是非とも毎回初期化して欲しい場合が(件のPC8801の例のようなマイナーな例であったとしても）ある訳ですから、そして毎回初期化したくない場合はそれを明かに書く方法(static をつける）がある訳ですから、コンパイラとしては環境に対して勝手な仮定を立てては行けないです。

> 普通の定数伝搬による最適化は認めてるのだから，配列であっても同じだと思うのですが…
....
> がt, a, cを生成することなく return 13;ってするのも駄目なんでしょうか．
これを見て、私の言うことを理解されていないなぁ、と思いました。無論問題ないです。これは、最適化前のコードではauto/staticそれぞれのやり方で「生成」されるのでstaticのあり/なしで異なるべきですが、最適化の段階で「生成」自体が省略される訳ですから、どちらの場合もreturn 13;と同様になります。

私の言っている意味を理解されていないようです。autoとstaticを同じ扱いをしているならそれは問題だ、と言っているのです。結果的に同じコードになること(があるの)に問題はありません。件の例では定義した関数のポインタが必要になった場合など、関数の定義を最適化によって省略できない場合に違う出力が欲しいところです。もし、また件の関数に関しても、その定義が最適化により不要（実質単なる配列と代らない関数）になる場合「だけ」を議論しているなら、これまた別の話です。

> autoであっても...違わないと思います．というか「autoとして」ってどういう意味かはっきりしないし．
その違いに関しては前に書いた通りです。付け加えるならばコード内は最近のOSなら保護により他のスレッドは書換えられないですが、staticな配列なら他のスレッドから書換えられます。
「autoとして」というのは「ISOのautomatic objectsの定義の通り」に、ということです。objectsの初期化はライフタイムの最初に行なわれ、automatic objectsのライフタイムはスコープ内である、と規定されてますから、automatic objectsはスコープの最初で毎回初期化されます。

関数の定義自体が最適化によって省略可能な場合は変数はスコープごとなくなりますから、変数の生成に関しての議論すべくもありません。また、変数の生成自体が省略される場合も同様です。

> 何かもっと積極的な理由はないんでしょうか．
C/C++は他の「高級」な言語とは異なり、「プログラマは賢いからコンパイラは素直に言うことを聞く」という哲学でできているはずです。autoで宣言したものを「最適化」を理由として変数や配列の生成を「省略」するの問題ないですが、「staticに生成する」のではプログラム意味が大きく変ってしまいます。C/C++で書くからにはコンパイラには過ぎたことをして欲しくないのです。

＜つづく＞

> 一区画が学校の教室っぽい

ん？
それは単にでてきた女の子がメイド服を着ていたというだけで違う種類の店では？と思ったけど店の紹介ページの店内写真をみたら仕切られてるわけでもなく大部屋の一画がそうなんですね．なんか変な感じ．

少し聞きたいこともあるんだけど，「彼」が自分の掲示板にスレッドを立てたようなんでそっちで「彼」に聞きます．
では，またいつか．

第一印象は煙草の煙やだなーというのと，一区画が学校の教室っぽいという程度で他はインパクトなかったです．
彼と同じく店員さん目当てにというのは，なりえないかと．
あと意外に女性客がいました．
まあ自分から行こうとは思わないし，今回も提案者が男性だったら行かなかった(行けなかった)でしょうねぇ．

メイド喫茶はどうでした？
（多分同行したであろう）ある人の日記を読んで気になっただけで，
他意はありません．
光成くんのような人がどういう感想をもつのか興味があります．

「安全性が減少するからautoとして動作してほしい」というのは私にはあまり同意できないです．

autoであっても関数内で生成するための(コピー前の)配列情報はコード中にあるわけですから，それを見るのとstaticなのを見るのとはたいして違わないと思います．というか「autoとして」ってどういう意味かはっきりしないし．

何かもっと積極的な理由はないんでしょうか．

プロテクトうんぬんもそういう処理系だったからそういうテクニックがうまれたのであって，区別しない処理計を否定する理由にはならないでしょう．

普通の定数伝搬による最適化は認めてるのだから，配列であっても同じだと思うのですが…
int func()
{
int t[] = {1,2,3,4};
const int a = 3;
static const int b = 5;
int c = 2;
return a + b + c + t[c];
}
がt, a, cを生成することなく return 13;ってするのも駄目なんでしょうか．

件の記述ではコンパイラが(暗黙的に)autoと宣言してあるものをstaticとして
出力してもよいことを勝手に判定できないはずという主張です。そもそもstaticにしたい場合はstaticと書けばいい訳で、書かないからにはautoとして動作して欲しいですね。auto変数が暗黙にmalloc/freeされるような処理系があっても良いとは思いますが、staticな動作はしてほしくないです。

・他のスレッドやプロセス(OSがあまりセキュアでない場合)から関数呼び出し前に 配列の内容をのぞかれたり(のぞかれたくない場合)変更されてた場合の動作の安全性が減少します。
他のスレッドやプロセスの動作は信用しない、どういうバグや悪意のプログラムがあるか分からないという立場をとっています。
プラグインなどは、同一プロセスの他のスレッドで動作させる場合もあり、したがって他人の書いたプログラムが同一プロセスの他スレッドで動く場合もあります。
Sonyの携帯がこの手の不具合のために大量にリコールになってSonyの携帯部門がエリクソンに合併になりましたよね。

・PC8001などの古いアーキテクチャーの場合は、auto変数でとった領域がメモリマップドI/Oになっていることもあります（このようなトリックはコピープロテクトのプログラムを解析困難にするために使われていたことがありました）。

>関数起動の度に生成されるべきということです。
いえ，だから「予め生成されているもの」と「起動の度に生成されるもの」の二つが区別されうる状況があるのか，というのがもともとの疑問です．区別されないのなら予め生成しておいてよいですよね．

> 配列がどこに置かれるかなんて実装依存の話だからバグとは違うと思います．
何処におかれるかという問題ではないです。関数起動の度に生成されるべきということです。

いえいえ，みなさんパワフルな方たちでとても楽しかったです．

最近は割と広告で見かけますが，流行ってるんですかね．
私は天の邪鬼なので流行ってると聞くとやる気が減ります(笑)．

配列がどこに置かれるかなんて実装依存の話だからバグとは違うと思います．
どうしてもというのならtextセグメントに配列データを置くとか(flatモデルのOSじゃないと若干効率がが悪くなるかもしれませんが)，
リンカオプションなどで他から隠すなどすればよいわけですし．

4日はお忙しい中、どうもありがとうございました。
私は隣に座っていた者です。
せっかくの久々の再会に、関係ない変なのがくっついてって
スミマセン。

話は変わりますが、数独ってそんなに流行ってるんですね。
私もやってみようかな？

> こちらも違うと思います．実際日記に書いたようにgcc 4.0.2ではstaticありなしで同一のコード(どちらもrodataに置かれます)を生成しています．
私見ですが、これはgccの(設計の？）バグだと思います。

>1. constでもvolatileになり得る

それは違うんじゃないでしょうか．関数内localなconst配列が別スレッドからのアクセスを考慮することで挙動が変わることはないでしょうし，memory mapped I/Oに割り当てられることも無いと思います．

>2 セグメントの位置．
こちらも違うと思います．実際日記に書いたようにgcc 4.0.2ではstaticありなしで同一のコード(どちらもrodataに置かれます)を生成しています．

>classでstaticなしなら
そのケースは理解しています．でも今回はPODですし．

ttさんではありませんが。
1. constでもvolatileになり得るという系統の話。すなわち、配列tblをfuncの
外他の何か（別スレッドやmemory mapped I/Oで他の機器など） が
アクセスする場合。
2. staticだとdataセグメントに｛1,2,3,4｝のデータが入るが、staticなしだと
codeセグメント中に埋め込まれる、すなわち{1,2,3,4}が秘密なデータの場合
にバイナリからはstaticなしの方がバレにくい。
と言ったところを言っているのだと思います。

ちなみにclassでstaticなしなら、シングルスレッドでも関数が呼ばれる度に
ctor/dtorは呼ばれるべきで、ctorに副作用があれば副作用の起るタイミング
と回数が違いますね。

ごぶさたです．
同意者がいてうれしいです．
そもそも掲示板が分かれるところもありますよね．
一カ所にするならもう少し気を効かせてほしいなと．

僕はオーソドックス（なことが利点）な１番目のでもいいと思いますが、
２番目のやつはいいアイデアですね。
目当ての列車が何番線かわかってもその線がどちら側かわからないのは
何年も使っている今でもよくあります。

>ちがうっす〜
違うっすか．

どういう場合かしらん．実際，gcc 4.0では同じコードが生成されてるしなあ．
intじゃなくてclassだと，マルチスレッドのときにcstrが呼ばれる回数が違うとか???
うーん，降参．

>違うなら教えて

ちがうっす〜

どうもごぶさたです．
最近「不機嫌そうね〜」なときが多いですね．反省．

数独は，近頃頭固くなってる気がするしと，久しぶりにやってみたところだったので余計に焦ってました．

最近は大会もあるんですね．びっくり．
http://plusd.itmedia.co.jp/games/articles/0603/27/news008.html
また時々書き込んでくださいまし．

お久しぶりです。　　時々ここを覗いて「元気そうね〜」とか「不機嫌そうね〜」とか思っていました。４日の日記を見て私も行き詰まっていた「数独」の訂正を知り、ほっとしてます。（私も「脳が堅くなった」と思い込んでいた）
　実は数独の存在とやり方を私に教えてくれたのはへるみさんだって覚えてます？　今では見かけたら解かずにおれません。この前の正月イギリスへ行ったら、某有力新聞紙上で毎日レベル別に３種類のSUDOKUが掲載されていて、なかなか解き甲斐がありましたよ。
　ほかの方達とは違う方向の話で失礼しまいした！
　

> uuencodeは使わないけどishは使ってたりして。
かなり前のdistributionからishは入らなくなったので使ってないですね．それで渡しても「復号できん」って言われちゃうので．

最近はリモートでサーバを使うことが多いので(Xも入ってない)screenは重宝してます．viの分割ウィンドウとscreenの分割ウィンドウを時々混乱してしまうことはありますけど．

uuencodeは使わないけどishは使ってたりして。

screenなんて懐かしいなぁ。大学のころは常用してましたが、Xが楽々
動くようになり、networkに簡単に繋げられるようになってあまり使わ
なくなっていたんですが。（それでも昔、会社のサーバで作業するのが
重かったときには重宝しました。）それにしても便利になったものです
ね。ウィンドウ分割やマルチセッションなんて出来るようになってるん
ですね。

ええ．私は適当に検索しただけですが，dskなら知ってはるかと思ってました．

リンク先を見たらSR8000とあったのでもしや、と思ったら某K研ではないですか。しかもOB会の幹事の吉田くんのサイトとは....

お返事ありがとうございます。
一般には除算は含まれないということですね。

その方面はうといので想像ですが，多分ベクトルや行列演算の指標なんですよね．だとしたら加算とか積和演算とかで割り算は含まないんじゃないかしらん．
適当に検索…
http://www.super-computing.org/~ysd/myself/kadai2.html
によると除算以外の四則演算っぽいですね．

FLOPSは、1秒間に何回浮動小数点演算ができるかという単位というのを見かけます。
ここで言う、"演算"が何を指しているのか分かりません。
四則演算だとすると、普通に考えて除算のレイテンシは大きいので、各演算で単位時間あたりに実行できる回数が違うと思うのです。
最近のx86系のCPUを使っていると仮定して、大雑把にFLOPSを見積もりたいと思った場合、どのようにして算出すればよいのでしょうか？

そうですね．それであってます．

図を書いていたら再帰的な定義でできるというのは分かったのですが，それを再帰やループ無し(テーブルも使わない)で求める方法も欲しかったのでした．

で，さっき，ようやくできました．詳細はあまりここには書きにくいので，もし興味がございましたらメールしてくださいまし．

最初の数値を選んだ後は、残りの数値の定義を探しているようです。
11=4+7=4+(4+2+1)=4+4+2+1

11〜14の定義はどうなってますか?

11=4+4+2+1
12=8+2+1+1
13=8+2+2+1
14=8+4+1+1

class Bのフィールド（protectedでもpublicでもprivateでも良い）に
using A<T>::queue_size;
を加えても良さそうですね。

ところで 5=2+2+1, 9=4+4+1を見る限り最大から順に再帰的に一つずつ決定していくのではないことが分かりますね。

> >これは正しい動作なんでしょうか?
> VC++系だとVC6, VC7.1, VC2005, iclでコンパイルできますね．gccだと3.4.2でも駄目でした．
> http://www.comeaucomputing.com/tryitout/
> で
<中略>
> まあ，クラスの場合はなくてもよいですが，templateの場合はBの定義をコンパイルしてるときはTが何か分からないので，A<T>も分からない(インスタンス化するときに分かる)．だからその中も分からないということのようです…
> というのが『Effective C++ 3rd Ed.』のitem 43に書いてありました．

検証ありがとうございました。勉強になります。

>これは正しい動作なんでしょうか?
VC++系だとVC6, VC7.1, VC2005, iclでコンパイルできますね．gccだと3.4.2でも駄目でした．
http://www.comeaucomputing.com/tryitout/
で
template<class T>
struct A {
T t_;
};

template<class T>
struct B : public A<T> {
void setsize(int size)
{
t_ = size;
}
};

int main()
{
B<int> b;
}
というコードを(web上で)試すとstrictモードだとエラー(thisをつければOK)だけど，relaxedモードではコンパイルできました．というわけでエラーになるのが正しそうです(なんて演繹的な返事だ(^^;)．

まあ，クラスの場合はなくてもよいですが，templateの場合はBの定義をコンパイルしてるときはTが何か分からないので，A<T>も分からない(インスタンス化するときに分かる)．だからその中も分からないということのようです…
というのが『Effective C++ 3rd Ed.』のitem 43に書いてありました．