それと。

ソフトウェア業界の商用ツールのピンキリ度合はどうにかならないのだろうか*1。価格と性能が比例していないどころか相関すらしていない。まあ、価格と機能数は割合と相関しているかもしれないが、それも 価格∝機能数^N, N > 1 というように見える。しかも、自社以外のツールとの連携は一切考えていないというものが多すぎる。

*1:PGReliefの話ではないけれど。

再開発≠再実装

http://d.hatena.ne.jp/tt_clown/20091228/1261996214http://d.hatena.ne.jp/monjudoh/20091228/1262023451http://d.hatena.ne.jp/Isoparametric/20091230/1262134418の話。

態度表明。

先に明言しておくと、私は「再開発はするな。再実装は考えてからしろ」という意見だ。これだけだと是々非々=単なる日和見ともとれる無意味な意見になってしまうので、以下では再実装するべき条件について書く。

STLコンテナの現状を。

STLコンテナ共通の仕様では主要インターフェースが定義されている。STLではこのインターフェースを用いて検索やソートなどの基本アルゴリズムを利用する。この仕組みはC++ templateの基本思想に沿って作られており、オーバーヘッドを最小(大抵の場合は文字通り0)にすることができる。
STLコンテナ個別の仕様ではコンテナ全体のメモリ効率や主要インターフェースの速度効率まで定義されている。大抵の場合は用途にあったスペックのコンテナを選ぶ、要求水準が高ければ複数のコンテナ・複数のSTL実装を実ベンチマークで比較して選ぶ、というように開発を効率化することができる。
このような過程を経たC++コードは大抵の手書きCコードと同程度の性能を持つ。メモリアロケータのチューニングを行えばCコードを上回る性能に至ることもしばしばある。

目的と対応を考える。

学習目的
これは実装したコードが目的ではなく実装する行為が目的なので、再実装するのも再開発するのも自由だろう。
コードサイズ削減
大抵のSTLやtemplateはコードサイズの最小化を目的としていないため、単純にSTLを使うのでは失敗する。
追加機能
この場合に再開発するのは無駄だろう。Boostなどを参考にしつつ、STLコンテナを拡張したコンテナを開発するべきだ。
性能目的
STL範囲内でのチューニングで要求性能を満たせない場合もある。この場合の再実装のみが議論の対象になっていると思う。

要求性能を満たせないなら。

STLコンテナを適切に使っても要求性能を満たせない場合、次のような可能性を疑っておく必要がある。これらが原因ならば用途に特化したコンテナを用意してオーバーヘッドを削った程度では解決できないと思われる。遡って軌道修正するべきだろう。

  • そもそも要求水準が高すぎる。
  • 不適切なアルゴリズムを利用している。
  • 排他・同期に時間をとられている。

こういった問題がないことが明らかであってコンテナの性能を高めなければならない場合に初めて再実装を行う意味があると思う。その場合にもSTLコンテナの延長として開発するべきではないだろうか。STLコンテナのテストケースの大半を流用して品質を担保できるという点も魅力である。
例えば、stl::vectorのような擬似配列であれば、要素の追加・挿入の速度を犠牲にしても平均メモリ効率を向上したいことがある。このような要望は十分考えられるものだが、insert()時などに適宜reserve()を呼ぶようにstl::vectorを拡張すれば済むはずだ。また、STLコンテナのサブセットとして開発するのもよい。要素数を増減する必要は一切ないという条件ならばstl::vectorよりも高速な擬似配列を作るのも容易だろう。ただし、そういったコンテナは大抵Boostに存在していることを忘れてはならない。

〆。

STLなど、標準ライブラリ相当のものを再実装するのは確実に無駄だと思う。それとは逆に、"社内標準"など、ローカルライブラリは大抵ゴミなので標準ライブラリで置き換えることを考えるべきだと思う。

ソートの速度を決める要因についてメモ

思いつく限りの要因をあげてみる。

  • データ内容
    • 個別比較が必要かどうか
    • 比較にかかる時間
    • 比較の分割性
    • 比較の並列度
  • データ
    • 素数
    • 読み込みにかかる時間
    • 読み込みの並列度
    • 交換にかかる時間
    • 交換の並列度
  • ワーキングメモリ
    • 素数
    • 再帰段数
    • 読み込みにかかる時間
    • 読み込みの並列度
    • 書き込みにかかる時間
    • 書き込みの並列度
  • 初期状態
    • どの程度ソートされているか
    • 事前にソートの程度を知っているか

具体例は。

スパゲティソート
個別に比較する必要がない。比較にかかる時間は定数。並列度は要素数と同じ。
辞書順ソート、多倍長数値のソート
個別に比較する必要がない。比較にかかる時間が各データ長Nに比例する。比較をN段階に分割できる。並列度は要素数と同じ。
データベース上のソート
通常、要素数は非常に大きい。読み込みにかかる時間も大きい。交換にかかる時間も大きいが、読み込みより小さい。並列度は実装に大きく依存し、それなりに高いものが多い。

〆。

通常はソートの計算量の指標として個別比較の回数を用いる。もちろんこれは大抵の場合に適切だが、交換よりも読み書きで律速される条件も多い。読み書きは特にハードウェアへの依存が大きく、同一アルゴリズムでも実装によって効率が大きく変わってくる。身近な例としてキャッシュヒット率があるだろう。

毒魔を育てる

@の溜まり場IIで「毒→妖→地はどう?」と話を振ったのだけど、「ありかもしれないが微妙」というところで終わってしまった。向こうは今更なので続きをここに書く。

毒の特徴は。

  • 利点
    • 毒針は序盤の攻撃魔法では最強だろう。
    • 悪臭の雲は序盤から中盤まで搦め手として使える。
    • 蜘蛛の躯は毒液と俊足を同時に得られる。
    • 毒の耐性を魔法で得られる。
    • サソリの召喚は複数現れて攻撃力も期待できる。
    • 毒素の矢は総ダメージが大きい。
    • (NEW!)乗り換え時の成長阻害がない。
    • (NEW!)シフ信仰時の魔法書打ち止めが早い。
  • 欠点
    • アンデッドやデーモンに対処しづらい。
    • 最上位魔法の毒素の矢・猛毒の雲がLv6しかない。
    • 以前、耐性バグ(修正済)で毒素の矢が弱くなっていた。
    • 経験値と呪文スロットが無駄になる。

というようなところだろうか。終盤はどうしようもないとしても、序盤〜中盤は十分に役立つものが多いと思う。しかし、

  • 代替手段
    • 毒針は手投げ毒吹き矢で済む。
    • 悪臭の雲より蒸散の方が強い。
    • 蜘蛛の躯より俊足の方が安い。浮遊と組み合わせればさらに良い。
    • 毒耐性も属性変異で得られる。
    • 毒素の矢より水晶槍で素早く殺したい。

というように微妙感が満載だ。これをもうちょっと何とかできないものか。

水晶槍ルート

闇エルフ、刺客、ヴェフメット信仰で進める。毒スキルを抑制し、妖術スキルを伸ばす。手詰まりに陥る前に鉄塊の矢を使えるようになればOK。

暗殺術の魔法書(初期)
毒針で経験値を稼ぐ。騒音の投射で強敵を避ける。悪臭の雲はなるべく使わない。
妖術の魔法書(下賜)
石錐の矢があれば訓練用に習得する。
力の魔法書(下賜)
鉄塊の矢に移行する。
殲滅の魔法書(下賜)
レフディブの水晶の槍を常用できるようになれば完成。

注意点は以下の通り。

  • ヴェフメットから二冊の下賜を受けるまでが長い。
  • 鉄塊の矢に移行するまではカモ以外と戦わない。
  • 悪臭の雲なしでは中盤を生き抜けないが、風スキルが地スキルの成長を阻害するので控えめに。
  • 毒素の魔術師で開始して毒液の矢を中盤の主力に据えるのは普通なので省略。

おぞまールート

泥エルフ or 水棲の民、毒素の魔術師、シフ信仰で進める。召喚スキル>妖術スキルは困難だが必須。

初級毒殺者の手引書(初期)
毒針で経験値を稼ぐ。悪臭の雲で搦め手を補う。妖術スキルを抑制し、毒スキルを伸ばす。
毒害の魔法書(下賜)
サソリの召喚を常用する。毒スキルを抑制し、召喚スキルを伸ばす。
招集の魔法書(下賜)
小動物の召換でサソリを補助する。
召換の魔法書(下賜)
解放の宣誓、招来が便利。おぞましきものを数体連れ歩けるようになれば完成。

注意点は以下の通り。

  • 泥エルフの方が召喚スキル適正が高く、水棲の民の方が白兵戦能力が高い。
  • サソリの召喚を毒スキルのみで使う期間が厳しい。反逆対策も必要。
  • 寺院前に毒害の魔法書を手に入れた場合(獲得など)はヴェフメット信仰も選べる。

刃の手ルート

泥エルフ、毒素の魔術師、シフ信仰で進める。泥エルフ変異術師よりも序盤が楽、というところが利点。

初級毒殺者の手引書(初期)
毒針で経験値を稼ぐ。悪臭の雲で搦め手を補う。妖術スキルを抑制し、毒スキルもそこそこに、徒手格闘スキルを伸ばす。
毒害の魔法書(下賜)
蜘蛛の躯を常用する。毒スキルを抑制し、変異スキルを伸ばす。
小変異の魔法書(下賜)
刃の手を常用する。

注意点は以下の通り。

  • 腕力強化がないので打撃力が不足しがち。
  • 搦め手が少ないので手詰まりに陥りやすい。呪術か召喚を加えると大幅に安定する(はず)。

〆。

実用レベルなのは刃の手ルートだけかも。

RAIIの代用

C++だとRAIIでリソースの後始末ができる。CだとRAIIが使えないが代案を考えてみた。エラーコードが雑なのは気にしないで。

ありがちなもの。

int func(char const* filename) {
  FILE *fout = fopen(filename, "a+");
  if (fout == NULL) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    fclose(fout);
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    fclose(fout);
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  fclose(fout);
  return 0;
}

リソースの後始末が面倒だよね。

もう一つのありがちなもの。

int func(char const* filename) {
  int ercd = 0;
  FILE *fout = fopen(filename, "a+");
  if (fout == NULL) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    ercd = -1;
    goto ON_EXIT;
  }
  fprintf(fout, "Logging ...\n");
ON_EXIT:
  fclose(fout);
  return ercd;
}

ercdって変数は要らないよね。

思いついたもの。

static int func_impl(FILE *fout) {
  if (fout == NULL) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  if (do_something()) {
    return -1;
  }
  fprintf(fout, "Logging ...\n");
  return 0;
}
int func(char const* filename) {
  FILE *fout = fopen(filename, "a+");
  int const ercd = func_impl(fout);
  fclose(fout);
  return ercd;
}

まともなコンパイラならfunc_implをインライン化するよね。

挿入ソートの話のまとめ

gcc4.3 -O3 on Atom, N=10000の条件で挿入ソートを測った結果(ソースコードは下に)。所要時間(time)を測っただけでは振る舞いが掴めないので、cachegrindでD1キャッシュ読み回数(D1read)を数えてみた。

関数 メモリ time D1read
yane0 malloc 9.79 62M
wkpd0 malloc 9.82 27M
yane1 static 8.09 27M
wkpd1 static 11.35 28M

大規模なソートということでmallocで確保したメモリをソートする場合、最適化がよく効いている限り、どちらもほぼ同等の速度で動くようだ。
ただし、やね版はstaticに確保したメモリをソートする場合、Wikipedia版よりも約3割速く動いた。ほぼ本人の言っている通りの成績だ。

〆。

とはいえ、jのオフセットや番兵のありなしで20%くらい揺らぐのも事実。要素数によっても要素サイズによってもCPUによってもコンパイラによっても簡単に変わる話なので、両方実装して速度を比較しないと判断できない、といったところだろうか。
あと、iccではWikipedia版の方が速い、というより、iccではやね版が妙に遅い、という傾向がある。オプション調整で速くなるのかもしれないけれど試さない。

ソース。

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

void yaneurao_ins_sort_000(int data[], size_t const size) {
  int i, j, tmp;
  for (i = 1; i < size; ++i) {
    tmp = data[i];
    if (data[i-1] > tmp) {
      j = i;
      do {
        data[j] = data[j-1];
        --j;
      } while (j > 0 && data[j-1] > tmp);
      data[j] = tmp;
    }
  }
}

void wikipedia_ins_sort_000(int data[], size_t const size) {
  int i, j, tmp;
  for (i = 1; i < size; ++i) {
    tmp = data[i];
    for (j = i; j > 0 && data[j-1] > tmp; j--) {
      data[j] = data[j-1];
    }
    data[j] = tmp;
  }

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

#define MAX 100000
static int local[MAX];

void yaneurao_ins_sort_001(int const orig[], size_t const size) {
  int i, j, tmp;
  if (MAX < size) {
    return;
  }
  memcpy(local, orig, size*sizeof(int));
  for (i = 1; i < size; ++i) {
    tmp = local[i];
    if (local[i-1] > tmp) {
      j = i;
      do {
        local[j] = local[j-1];
        --j;
      } while (j > 0 && local[j-1] > tmp);
      local[j] = tmp;
    }
  }
}

void wikipedia_ins_sort_001(int const orig[], size_t const size) {
  int i, j, tmp;
  if (MAX < size) {
    return;
  }
  memcpy(local, orig, size*sizeof(int));
  for (i = 1; i < size; ++i) {
    tmp = local[i];
    for (j = i; j > 0 && local[j-1] > tmp; j--) {
      local[j] = local[j-1];
    }
    local[j] = tmp;
  }
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

extern void yaneurao_ins_sort_000(int data[], size_t const size);
extern void wikipedia_ins_sort_000(int data[], size_t const size);
extern void yaneurao_ins_sort_001(int const data[], size_t const size);
extern void wikipedia_ins_sort_001(int const data[], size_t const size);

int main (int argc, char *argv[]) {
  int i, loop, size;
  clock_t start, stop;

  if (argc < 3) {
    return -1;
  }
  loop = atoi(argv[1]);
  size = atoi(argv[2]);

  int *orig = malloc(size*sizeof(int));
  int *data = malloc(size*sizeof(int));
  
  srand(0xdeadbeef);
  for (i = 0; i < size; ++i) {
    orig[i] = rand();
  }

  start = clock();
  for (i = 0; i < loop; ++i) {
    memcpy(data, orig, size*sizeof(int));
    yaneurao_ins_sort_000(data, size);
  }
  stop = clock();
  for (i = 1; i < size; ++i) {
    if (data[i] < data[i-1]) {
      puts("ERROR!");
    }
  }
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    memcpy(data, orig, size*sizeof(int)); 
    wikipedia_ins_sort_000(data, size);
  }
  stop = clock();
  for (i = 1; i < size; ++i) {
    if (data[i] < data[i-1]) {
      puts("ERROR!");
    }
  }
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    yaneurao_ins_sort_001(orig, size);
  }
  stop = clock();
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    wikipedia_ins_sort_001(orig, size);
  }
  stop = clock();
  printf("%f\n", (stop-start)*1E-6);

  free(data);
  free(orig);

  return 0;
}
CC     = gcc
CFLAGS = -O3
#CC     = icc
#CFLAGS = -O3

all:a.out
	./a.out 100000000 10
	./a.out 1000000 100
	./a.out 10000 1000
	./a.out 100 10000
	./a.out 1 100000

cg:a.out
	valgrind --tool=cachegrind ./a.out 1000000 10
	valgrind --tool=cachegrind ./a.out 10000 100
	valgrind --tool=cachegrind ./a.out 100 1000
	valgrind --tool=cachegrind ./a.out 1 10000
	find . -name 'cachegrind.out.*' -exec cg_annotate {} \;

clean:
	${RM} *.out *.o
	${RM} cachegrind.out.*

.c.o:
	${CC} -c ${CFLAGS} $?

a.out:extern.o sort_000.o sort_001.o
	${CC} ${CFLAGS} extern.o sort_000.o sort_001.o -o $@

固定小数点数のフォロー

http://www.kt.rim.or.jp/%7ekbk/zakkicho/09/zakkicho0910c.html#D20091027の話。

Wikipediaだと。

固定小数点数(こていしょうすうてんすう)は、コンピュータにおける実数の近似値の表現方式。固定小数点数では整数部分に用いるビット数と小数部分に用いるビット数をあらかじめ固定して表現する。

と書いてありますが、上記引用部が成り立つのは基数=2の場合だけで、基数≠2でない場合には成り立ちません。
少なくとも私の関わった範囲だと、「固定小数点数」と一口に言った場合に「基数=2の固定小数点数」を指す、という経験はありません。逆に会計に近い分野だと、「固定小数点数」は「基数=10の固定小数点数」を指す、というのはありましたが。

誤差は。

同じ基数を利用する固定小数点数BigDecimalならば、表現範囲に収まる計算の結果は誤差も含めて一致します。というより、下記のJava APIを読む限り、BigDecimalは任意長、基数=1010^scale*1固定小数点数です。

変更が不可能な、任意精度の符号付き小数です。BigDecimal は、任意精度の「スケールなしの整数値」と、32 ビット整数の「スケール」で構成されます。0 または正の場合、スケールは小数点以下の桁数です。負の場合、スケールなしの数値に、スケールの正負を逆にした値を指数とする 10 の累乗を乗算します。つまり、BigDecimal で表される数値は (unscaledValue × 10-scale) です。

〆。

暗黙に「基数=2の固定小数点数」という分野もあると思うので、ご存知の方は教えてください。

追記

やはり「固定小数点数」は「基数=2の固定小数点数」を指す分野もある/あったようです。

*1:肝心なものが抜けてました。ごめんなさい。