読者です 読者をやめる 読者になる 読者になる

空想犬猫記

※当日記では、犬も猫も空想も扱っておりません。(旧・エト記)

一時オブジェクトの寿命

先輩にバグじゃないの?と指摘されたコード。

class MyString
{
public:
  MyString();
  MyString(const std::string& s);
  :
};

extern const std::string& GetName(int idx);

int main()
{
  for (int i = 0; i < N; ++i)
  {
    const MyString& s = GetName(i);
    // この後、forのスコープ内で文字列 s を使うのは安全か?
  }
  
  return 0;
}

このコードは、以前、レガシーな std::string を使ったコードを国際化対応した文字列クラスに一括置換したときに生じたものだ。まだプロダクションには使われていないが、一瞬、嫌な汗をかいた。結論から言うとこれは合法だった。コンパイラも完全にスルーしていたので気付かず。

何が起こっているかというと、GetName() で std::string の参照が返った後、MyString の変換コンストラクタ MyString(const std::string&) が呼ばれ、一時オブジェクトが作られる。一時オブジェクトをconst参照で受けた場合、一時オブジェクトはconst参照に束縛されるというルールがあり、const参照変数のスコープまで延命される。したがってfor文のスコープ内で使うことができる。

まぁ、参照で受けてコピーを作らないという意図も叶っておらず、単にややこしいだけなので、早々に直したほうが良いだろう。

VC++のunordered_set/unordered_mapが遅い件

正確に言うと、insertが同種のset/mapに比べて圧倒的に遅い。

最近、メモリの節約のために辞書的なオブジェクトを作成して、同値のオブジェクト(例えば文字列)を再利用するようなコードを書いたところ、unordered_set/unordered_mapで思うような性能が得られなかった。

コンテナ以外のアロケーションの影響を受けないように、あらかじめ文字列を用意して、それを辞書に登録する以下のサンプルコードを書いて、Visual Studio 2015でプロファイルをとってみた。

#include "stdafx.h"

using namespace std;

namespace
{
  struct char_cmp : public binary_function<const char*, const char*, bool>
  {
    result_type operator()(first_argument_type l, second_argument_type r) const
    {
      if (!l)
      {
        if (!r) return false;
        return true;
      }
      else
      {
        if (!r) return true;
        return strcmp(l, r) < 0;
      }
    }
  };

  struct char_hash : public unary_function<const char*, size_t>
  {
    size_t operator()(argument_type key) const
    {
      return hash_value(key);
    }
  };

  struct char_equal_to
  {
    typedef const char* first_argument_type;
    typedef const char* second_argument_type;
    typedef bool result_type;

    bool operator()(first_argument_type pL, second_argument_type pR) const
    {
      return strcmp(pL, pR) == 0;
    }
  };

  template <typename Set> __declspec(noinline) void TestSet(const vector<string>& samples)
  {
    Set set;
    for (auto& s : samples) set.insert(s.c_str());
  }
}

int main()
{
  vector<string> samples;
  samples.reserve(100000);

  default_random_engine generator;
  uniform_int_distribution<int> distribution(33, 126);

  for (int i = 0; i < 100000; ++i)
  {
    samples.emplace_back();
    auto& str = samples.back();
    str.reserve(300);
    for (int j = 0; j < 300; ++j)
      str += distribution(generator);
  }

  TestSet<unordered_set<const char*, char_hash, char_equal_to>>(samples);
  TestSet<set<const char*, char_cmp>>(samples);
  return 0;
}

で、結果がこちら

f:id:xoinu:20161210085710p:plain

サンプルの要素数が増えれば増えるほど差は広がるばかり。確認のためTDM-GCCで同等のコードを書いてみたところ、むしろunordered_set/unordered_mapの方がinsertは高速だったので、これはVisual StudioSTLの実装特有の問題っぽい。

Visual Studio上でunordered_set/unordered_mapを旧来のset/mapの代わりに使う際には、必ずベンチマークをとって、挿入性能劣化に見合う検索性能の向上の恩恵に与れるかどうかを確認したほうが良さそうだ。

やれやれ……

追記:
xoinu.hatenablog.com
2年前にint型のコンテナで挿入のパフォーマンスのチェックをやってた。そのときの結果と少し矛盾している。これを見るにVC++のxhashヘッダにあったstd::hash_value()関数がよろしくないのかもという気がする。

再帰呼び出しをループに置き換える

半年に一度くらい、古いコードで使っている再帰呼び出しが原因でスタックオーバーフローになるという不具合が発見され、その都度ループで書き直す修正を入れている。再帰呼び出しをループに展開する方法は、「幅優先探索」や「深さ優先探索」というキーワードで探すと見つけることができる。そのエッセンスだけメモしておく。

再帰呼び出しのうち、トップダウンで処理していくものについては、キューを使うと比較的簡単に展開できる。たとえば

struct Node {
  Node* left;
  Node* right;
  :
};

という構造体があって、

void ProcessNode(Node* node)
{
  :
  : (do something)
  :

  if (node->left)
    ProcessNode(node->left);

  if (node->right)
    ProcessNode(node->right);
}

のような再帰呼び出しがあるとき、ProcessNode関数は以下のように展開できる。

void ProcessNode(Node* node)
{
  list<Node*> nodeList;
  nodeList.push_back(node);

  while (!nodeList.empty())
  {
    node = nodeList.front();
    nodeList.pop_front();

    :
    : (do something)
    :

    if (node->left)
      nodeList.push_back(node->left);

    if (node->right)
      nodeList.push_back(node->right);
  }
}

ボトムアップに処理していくものも基本的な考え方は一緒であるが、

  1. キューの代わりにスタックを使う
  2. スタックを積むときと実際に処理をするときの二度、ノードを訪れることになるので、今どっちのタイミングなのか、知るためのフラグが必要

になる点が少し面倒になる。模擬コードは以下のようになるはず(自分で試してね)。

namespace {
  struct Data {
    Data(Node* n) : node(n), isTraversed(false) {}
    Node* node;
    bool isTraversed;
  };
}

void ProcessNode(Node* node)
{
  vector<Data> nodeList;
  nodeList.push_back(node);

  while (!nodeList.empty())
  {
    auto& data = nodeList.back();
    node = data.node;

    if (!data.isTraversed)
    {
      data.isTraversed = true;

      if (node->left)
        nodeList.push_back(node->left);

      if (node->right)
        nodeList.push_back(node->right);
    }
    else
    {
      nodeList.pop_back();
      :
      : (do something)
      :
    }
  }
}

再帰呼び出しで書くと、単にコード中の "do something" の位置を if 文の前に持ってくるか後ろに置くかだけの差であり、記述としては簡便なうえに、マシンスタックを利用したほうがヒープよりも高速に動作する。つまりスタックオーバーフローを起こさない限りは再帰のほうが一概に優れているので、もろもろ考慮してどちらの実装方法を選ぶか決めましょう。

COMについて

自分用のメモ。幾度となくCOMの仕様を振り返って、使えるものが無いか探してしまう自分への戒め。

C++のプロジェクトで、パフォーマンスに妥協をせず、かつコンパイル、リンクの速度も維持して、ランタイムの依存性が無く(異なるバージョンのコンパイラでビルドされたモジュールと結合でき)、かつ複数の言語から使用可能な公開APIのインターフェースを突き詰めていくとCOMになる。しかし21世紀の今となっては新たにCOMのプロジェクトを始めるくらいなら、.NETのラッパを書いたほうが良い。

COMのインターフェースベースのAPIだけ参考にして、純粋なC++でライブラリを記述するのが現実的な解と思われる。

Cron の設定メモ

Windows 7上でCygwinのCronを設定した。

cygrunsrvは管理者権限が必要なので、ショートカットを右クリックしてアドミニストレータとしてCygwinを起動する。サービスの登録は以下のコマンド

cygrunsrv --install Cron --path /usr/sbin/cron.exe \
    --neverexits --preshutdown --disp "Vixie's Cron" \
    --type auto --user "<domain>\\<user>" \
    --passwd <password>

サービスを削除するときは

cygrunsrv --remove Cron

とする

Firefox設定メモ ~MS PゴシックをMeiryo UIに置換~

Google Chromeが頻繁にクラッシュするのと、メモリ使用量が必要以上に多いので、Firefoxに戻ってきた。久々に帰ってきてみたら、UIがGoogle Chromeっぽくなっていて全然違和感がない。HTML5になってから動画の再生にもプラグインが必要なくなったので、プラグインは全てアンイストールないしdeactivateした。

やるべきことは、userContent.cssをいじって「MS Pゴシック」を「Meiryo UI」フォントに置き換えたくらい。Webブラウザの世界の技術も標準化が進み枯れてきたのか、オジサンの想像力が枯れてきたのか。

具体的には以下の2ステップ。

%APPDATA%\Mozilla\Firefox\Profiles\XXXXXXXX.default

以下に chrome というフォルダをつくって、userContent.cssというファイルを作成する。中身はかつてGoogle Chromeでサポートされていたユーザスタイルシートと同じで、たんに

@charset "UTF-8";
@font-face {
  font-family: "MS Pゴシック";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS PGothic";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS P明朝";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS PMincho";
  src: local("Meiryo UI");
}

などとしておいた。私は英語版Windowsなのでフォント名は「Meiryo UI」だが、日本語版の場合は「メイリオ」などとする必要があるかもしれない。Google Chromeはご丁寧にユーザスタイルシートファイルの変更のイベントを拾って、動的に既に開いているページに変更を適用してくれたけれども、Firefoxの場合は再起動が必要。設定はたいてい一度限りだし、この方がよい実装だと思う。今のところなんの不満もない。

コンテナ内の検索の速度について(2) ~setの使いどころ~

C++エクササイズその3。前回前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。

具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。

結果

横軸がコンテナの要素数、縦軸が100万回findするのに要した時間(単位:秒)
f:id:xoinu:20140814153240p:plain

ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。

まとめ

intのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。単に検索目的であればunordered_set一択。

コード

#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <deque>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>
#include <string>

using namespace std;

static void BenchmarkFindString()
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  auto dice = bind(distribution, generator);

  uniform_int_distribution<int> distChar(65, 90);
  auto diceChar = bind(distChar, generator);

  uniform_int_distribution<size_t> distStrLen(16, 128);
  auto diceStrLen = bind(distStrLen, generator);

  vector<size_t> DATA_LENGTH_ARRAY(25);
  size_t next = 2000;

  for (auto& len : DATA_LENGTH_ARRAY)
  {
    len = next;
    next += 2000;
  }

  vector<string> QUERY_DATA(1000000);

  for (auto& dat : QUERY_DATA)
  {
    auto len = diceStrLen();
    dat.reserve(len + 1);

    for (size_t i = 0; i < len; ++i)
      dat += (char)diceChar();
  }

  cout << "size,vector,set,unordered_set" << endl;

  for (auto DATA_LENGTH : DATA_LENGTH_ARRAY)
  {
    vector<string> vals(DATA_LENGTH);

    for (auto& val : vals)
    {
      auto len = diceStrLen();
      val.reserve(len + 1);

      for (size_t i = 0; i < len; ++i)
        val += (char)diceChar();
    }

    cout << DATA_LENGTH;
    {
      vector<string> cont(begin(vals), end(vals));
      sort(begin(cont), end(cont));
      cont.erase(unique(begin(cont), end(cont)), end(cont));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        lower_bound(begin(cont), end(cont), val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      set<string> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      unordered_set<string> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }

    cout << endl;
  }
}

int main(int argc, char* argv[])
{
  BenchmarkFindString();
  return 0;
}