90/10ルール / 90/10 Rule

プログラムが実行時間の90%をコードの10%で費やす。80/20ルールと呼ばれることもある。 ホットな10%を見つけるのが有益。 そのために、プログラムの実行プロファイルを取る。

Stopwatchクラス / Stopwatch Class

template  class basic_stopwatch : T {
  typedef typename T Base_Timer;
public:
  // 生成、オプションで計測開始
  explicit basic_stopwatch(bool start);
  explicit basic_stopwatch(char const* activity = "Stopwatch",
                            bool start = true);
  basic_stopwatch(std::ostream& log,
                  char const* activity = "Stopwatch",
                  bool start = true);

  // ストップウォッチの停止と終了
  basic_stopwatch();

  // ラップ時間（直前のストップまでの時間）
  unsigned LapGet() const;

  // 述語：ストップウォッチが動いていれば真
  bool IsStarted() const;

  // 累積時間表示、実行継続、ラップをセット／返す
  unsigned Show(char const* event = "show");

  // ストップウォッチ（再）起動、ラップをセット／返す
  unsigned Start(char const* event_name = "start");

  // ストップウォッチを停止、ラップをセット／返す
  unsigned Stop(char const* event_name = "stop");

private: // メンバ
  char const*   m_activity; // "アクティビティ"文字列
  unsigned      m_lap;      // ラップ時間
  std::ostream& m_log;      // イベントログのストリーム
};
    

<chrono>ライブラリを使ったTimeBaseクラス。C++11が必要。

#include 
using namespace std::chrono;
class TimerBase {
public:
  // タイマをクリア
  TimerBase() : m_start(system_clock::time_point::min()) {}

  // タイマをクリア
  void Claer() {
    m_start = system_clock::time_point::min();
  }

  // タイマ実行中ならtrueを返す
  bool IsStarted() const {
    return (m_start.time_since_epoch() != system_clock::duration(0));
  }

  // タイマ開始
  void Start() {
    m_start = system_clock::now();
  }

  // タイマ開始後のミリ秒時間
  unsigned long GetMs() {
    if (IsStarted()) {
      system_clock::duration diff;
      diff = system_clock::now() - m_start;
      return (unsigned)(duration_cast(diff).count());
    }
    return 0;
  }
private:
  system_clock::time_point m_start;
};
    

C++のバージョンやOSによらないが、clock関数がLinuxとWindowsで測り方が少し異なる。

class TimeBaseClock {
public:
  // タイマをクリア
  TimerBaseClock()  { m_start = -1; }

  // タイマをクリア
  void Clear()      { m_start = -1; }

  // タイマ実行中ならtrueを返す
  bool IsStarted() const  { return (m_start != -1); }

  // タイマ開始
  void Start()      { m_start = clock(); }

  // タイマ開始後のミリ秒時間
  unsigned long GetMs() {
    clock_t now;
    if (IsStarted()) {
      now = clock();
      clock_t dt = (now - m_start);
      return (unsigned long)(dt * 1000 / CLOCKS_PER_SEC);
    }
  }
private:
  clock_t m_start;
};
    

文字列の最適化 / Optimize Strings

COW (Copy On Write)手法が良くとられる

remove_ctrl_ref_args() : 引数コピーの除去。文字列引数のコピーなくす。

std::string remove_ctrl_ref_args(std::string const& s) {
  std::string result;
  result.reserve(s.length());
  for (int i = 0; i < s.length(); ++i) {
    if (s[i] > 0x20) {
      result += s[i];
    }
  }
  return result;
}
    

文字列の戻り値のコピーをなくす

void remove_ctrl_ref_result_it(
  std::string& result,
  std::string const& s) {
  result.clear();
  result.reserve(s.length());
  for (auto it = s.begin(), end = s.end(); it != end; ++it) {
    if (*it >= 0x20) {
      result += *it;
    }
  }
}
    

文字列ではなく文字配列を使う

void remove_ctrl_strings(char* destp, char const* srcp, size_t size) {
  for (size_t i = 0; i < size; ++i) {
    if (srcp[i] >= 0x20) {
      *dstp++ = srcp[i];
    }
  }
  *destp = 0;
}
    

より豊かなライブラリをstd::stringに採用する

• Boost文字列ライブラリ(http://bit.ly/boost-string)
• C++文字列ツールキットライブラリ(http://bit.ly/string-kit-lib)

動的変数割り当てを最適化する / Optimize Dynamic Variable Allocation

動的変数の所有権を自動化するためにstd::unique_ptrを用いる。

探索と整列を最適化する / Optimize Search and Sorting

C++11で、リスト初期化構文を使ってテーブルにデータを設定できる

#include 
#include 

algorithmヘッダを使って探索を最適化する

struct kv { // (key, value)対
  char const* key;
  unsigned value;
};

kv names[] = {
  { "alpha",    1 }, { "bravo",     2 },
  //...
  { "yankee",   25 }, { "zulu",     26 }
};
    

データ構造を最適化する / Optimize Data Structures

std::dequeは両端キュー。FIFOを作るのに特化したコンテナ。

他のデータ構造

• boost::circular_buffer(http://bit.ly/circ-buffer) : std::dequeより効率的
• Boost.Container (http://bit.ly/boost-cont)
• dynamic_bitset (http://bit.ly/b-bitset)
• Fusion (http://bit.ly/b-bitset)
• Boost Graph Library (BGL) (http://bit.ly/b-graphlib)
• boost.heap (http://bit.ly/b-heap/)
• Boost.Instusive (http://bit.ly/b-intrusive)
• boost.lockfree (http://bit.ly/b-lockfree)
• Boost.MultiIndex (http://bit.ly/b-multi)

並行性を最適化する / Optimize Concurrency

単純なスレッド。

void f1(int n) {
  std::cout << "thread " << n << std::endl;
}

void thread_example() {
  std::thread t1;
  t1 = std::thread(f1, 1);
  t1.join();

  std::thread t2(f1, 2);
  std::thread t3(std::move(t2));
  std::thread t4([]() { return;});
  t4.detach();
  t3.join();
}
    

promise、future、スレッド

void promise_future_example() {
  auto meaning = [](std::promise& prom) {
    prom.set_value(42);
  };

  std::promise prom;
  std::thread(meaning, std::ref(prom)).detach();

  std::future result = prom.get_future();
  std::cout << "the meaning of life: " << result.get() << "\n";
}
    

mutex

• std::mutex
• std::recursive_mutex
• std::timed_mutex
• std::recursive_timed_mutex
• std::shared_time_mutex
• std::shared_mutex

ロック

• std::lock_guard
• std::unique_lock
• std::shared_lock

条件変数

• std::condition_variable
• std::condition_variable_any

条件変数を使った生産者と消費者

void cv_example() {
  std::mutex m;
  std::condition_variable cv;
  bool terminate = false;
  int shared_data = 0;
  int counter = 0;

  auto consumer = [&]() {
    std::unique_lock lk(m);
    do {
      while (!(terminate || shared_data != 0)) {
        cv.wait(lk);
      }
      if (terminate) {
        break;
      }
      std::cout << "consuming " << shared_data << std::endl;
      shared_data = 0;
      cv.notify_one();
    } while (true);
  };

  auto producer = [&]() {
    std::unique_lock lk(m);
      for (counter = 1; true; ++counter) {
        cv.wait(lk, [&]() {return terminate || shared_data == 0;});
        if (terminate) {
          break;
        }
        shared_data = counter;
        std::cout << "producing " << shared_data << std::endl;
        cv.notify_one();
      }
  };

  auto p = std::thread(producer);
  auto c = std::thread(consumer);
  std::this_thread::sleep_for(std::chrono::miliseconds(1000));
  {
    std::lock_guard l(m);
    terminate = true;
  }
  std::cout << "total items produced " << counter << std::endl;
  cv.notify_all();
  p.join();
  c.join();
  exit(0);
}
    

共有変数のアトミック演算。<atomic>

C++スレッドプログラムの最適化 / Optimizing C++ Thread Programs

std::threadよりstd::asyncを使う。 / Use std::async Instead of std::thread

コアと同じ個数の実行可能スレッドを作る。 / Create Runnable Threads Equal to CPU Cores

void timewaster(unsigned iterations) {
  for (counter_t i = 0; i < iterations; ++i) {
    fibonacci(n);
  }
}

void multithreaded_timewaster(
  unsigned iterations,
  unsigned threads) {
  std::vector t;
    t.reserve(threads);
    for (unsigned i = 0; i < threads; ++i) {
      t.push_back(std::thread(timewaster, iterations/threads));
    }
    for (unsigned i = 0; i < threads; ++i) {
      t[i].join();
    }
}
    

タスクキューとスレッドプールを実装する / Implement Task Queue and Thread Pool

実行されているスレッド数がわからないという問題を解決する方法は、スレッドを明文化すること。 一定個数の寿命の長いスレッドを含むデータ構造であるスレッドプールと、 スレッドプールのスレッドで実行される計算のリストを含むデータ構造であるタスクキューを提供することだ。

並行処理ライブラリ / Concurrency Libraries

C++標準にまだ採用されていない並列処理機能を提供する。

• Boost.Thread (http://bit.ly/b-thread)、Boost.Coroutine (http://bit.ly/b-coroutine)
• POSIX Threads
• スレッディング・ブルディング・ブロック (http://www.threadingbuildingblocks.org/)
• 0mq (http://zeromq.org)
• メッセージパッシングインタフェース (http://computing.llnl.gov/tutorials/mpi/)
• OpenMP (http://openmp.org)
• C++ AMP (http://bit.ly/cpp-accel)

メモリ管理を最適化する / Optimize Memory Management

• Hoard (http://www.hoard.org/)
• mtmalloc (http://bit.ly/mtmalloc)
• ptmalloc (http://bit.ly/1VFcqux)
• TCMalloc (http://bit.ly/tcmalloc)