reallocによる配列拡張の償却時間計算量

reallocを使ってメモリアロケーションのサイズを少しずつ伸ばしていく際に、償却時間計算量はO(N)になるだろうか、それともO(N^2)だろうか。結論としては、普通にやるとO(N^2)になる。ただし、セオリー通りにアプリケーション側で工夫するとO(N)にできる。性能テストをしてきちんと確認しておこう。

長さが事前にわからない文字列や配列を扱うには、動的に領域を確保する必要がある。標準C言語にはreallocという関数があり、それは既存の確保領域を拡張することが可能である。これを使うと、既に確保してある領域の直後にまだ確保されていない領域があってそこを合わせて確保できる場合、領域の再確保をせずに、利用可能なサイズだけを増やしてくれる。それが不可能な場合、別の領域を確保してから既存の領域のデータをコピーして、古い領域は削除してくれる。C++のnew/deleteにはこの機能はない。

同じ領域に対するreallocを連続で呼ぶ場合、領域移動なしのサイズ拡張が可能である。以下の例では1が2つ出力されるはずだ。仕様としての保証はないけど。

void* p1 = realloc(nullptr, 100);
void* p2 = realloc(p1, 200);
std::cout << (p1 == p2) << std::endl;
void* p3 = realloc(p2, 300);
std::cout << (p2 == p3) << std::endl;

複数の領域を交互に拡張しようとすると、そうはいかない。以下の例では0が2つ出力されるはずだ。仕様としての保証はないけど。

void* p1 = realloc(nullptr, 100);
void* q1 = realloc(nullptr, 100);
void* p2 = realloc(p1, 200);
std::cout << (p1 == p2) << std::endl;
void* q2 = realloc(q1, 200);
std::cout << (q1 == q2) << std::endl;

既に述べたが、reallocによる領域の移動は、既存領域の内容の複製を伴う。したがって、1バイトの領域を1バイトずつ伸ばしてNバイトにする作業を2つの領域で交互に行ったとしたら、その時間計算量はO(N^2)になってしまう。reallocの実装は領域が漸次的に拡張されるということは前提としていないので、本当に二次関数の勢いで遅くなる。なので普通はreallocなど使わずに、std::stringのappendメソッドとか、std::striingstreamの挿入オペレータとか、vectorのpush_backメソッドとかを使う。それらは内部の記憶領域を倍倍ゲーム（実際はfactor=1.5とか）で増やすので、償却時間計算量はO(N)になる。すなわち、最悪のケースでは最後のNバイト目を確保する際にN-1バイトのコピーが発生するし、その場合は以前に(N-1)/2バイトのコピーと(N-1)/4バイトのコピーと(N-1)/8バイトのコピーなどなどが発生しているはずだが、それらを全部足してもNに過ぎないので、線形オーダーとみなせるわけだ。

ところで、std::stringのappendとかが便利なのになぜreallocを使うのか。それは、std::stringは空間利用に無駄があるからだ。mallocやreallocの実装の内部では、割り当てた領域のアドレスに紐づけて割り当てたサイズを管理している。一方で、std::stringも自分が何バイト確保したかを属性として持っている。それでいて、std::stringが内部で呼ぶnewは結局mallocを呼ぶので、同じ情報を二箇所で持つことになる。ついでに言うと、std::stringでもstd::stringstreamでもstd::vectorでも、確保サイズの属性と利用サイズの属性は別個に持つ必要がある。今議論しているのは前者についてだ。

アプリケーション側で確保サイズの情報を持たなくても、毎回reallocを呼んじゃえばいい。reallocを呼ぶ際にも倍倍ゲームでサイズを決めれば、std::stringのappendを使うよりも効率的に、長さが増える文字列を扱うことができる。具体的に言うと、確保したいサイズを受け取ったら、それ以上で最小の2の冪をサイズにすればよい。つまり、以下のようなコードになる。8を最小値にしたのは経験則による最適化だ。

void* PowerAlignedRealloc(bool alignment, void* ptr, size_t size) {
  size_t aligned_size = 8;
  while (aligned_size < size) {
    aligned_size *= 2;
  }
  return std::realloc(ptr, aligned_size);
}

領域の再確保をしない場合のreallocは、確保サイズの変数を調べるだけの簡単なお仕事しかしない。その際にはスレッド安全性のために何らかの排他制御が行われるはずで、それなりのコストがかかる可能性はあるが、時間効率よりも空間効率の方が大事だという場面もある。

性能テストをしよう。100バイトずつサイズを増やしながらメモリ領域を確保する処理を100個の別個のレコードで行う。各レコードで1000回ずつ拡張操作を行い、1回目から100回目、101回目から200回目、...、901回目から1000回目にかかった経過時間をそれぞれ測定する。生のreallocと、冪アラインメント付きのreallocと、std::stringのappendメソッドを比較する。以下のプログラムだ。

#include <chrono>
#include <string>
#include <cstdlib>
#include <cassert>
#include <iomanip>
#include <iostream>

constexpr int num_iterations = 1000;
constexpr int num_records = 1000;
constexpr int size_unit = 100;
constexpr int check_unit = 100;

double GetWallTime() {
  const auto epoch = std::chrono::time_point<std::chrono::system_clock>();
  const auto current = std::chrono::system_clock::now();
  const auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(current - epoch);
  return elapsed.count() / 1000000.0;
}

void* Realloc(bool alignment, void* old_ptr, size_t size) {
  if (alignment) {
    size_t aligned_size = 8;
    while (aligned_size < size) {
      aligned_size *= 2;
    }
    size = aligned_size;
  }
  void* new_ptr = std::realloc(old_ptr, size);
  assert(new_ptr != nullptr);
  return new_ptr;
}

void TestRealloc(bool alignment) {
  std::cout << "-- Realloc alignment=" << alignment << " --" << std::endl;
  void* records[num_records];
  for (int record_index = 0; record_index < num_records; record_index++) {
    records[record_index] = nullptr;
  }
  int size = size_unit;
  double start_time = GetWallTime();
  for (int iteration_count = 1; iteration_count <= num_iterations; iteration_count++) {
    for (int record_index = 0; record_index < num_records; record_index++) {
      records[record_index] = Realloc(alignment, records[record_index], size);
    }
    if (iteration_count % check_unit == 0) {
      const double end_time = GetWallTime();
      std::cout << "iteration=" << iteration_count
                << " size=" << size
                << " time=" << end_time - start_time << std::endl;
      start_time = GetWallTime();
    }
    size += size_unit;
  }
}

void TestString() {
  std::cout << "-- std::string --" << std::endl;
  std::string records[num_records];
  std::string unit(size_unit, 0);
  double start_time = GetWallTime();
  for (int iteration_count = 1; iteration_count <= num_iterations; iteration_count++) {
    for (int record_index = 0; record_index < num_records; record_index++) {
      records[record_index].append(unit);
    }
    if (iteration_count % check_unit == 0) {
      const double end_time = GetWallTime();
      std::cout << "iteration=" << iteration_count
                << " size=" << records[0].size()
                << " time=" << end_time - start_time << std::endl;
      start_time = GetWallTime();
    }
  }
}

int main(int argc, char** argv) {
  std::cout << std::fixed;
  std::cout << std::setprecision(4);
  TestRealloc(false);
  TestRealloc(true);
  TestString();
  return 0;
}

結果はこんな感じ。単位は秒。

	default realloc	aligned realloc	std::string
1-100	0.1311	0.0092	0.0116
101-200	0.4607	0.0142	0.0177
201-300	0.7554	0.0044	0.0286
301-400	1.0436	0.0272	0.0107
401-500	1.3101	0.0040	0.0113
501-600	1.5381	0.0040	0.0488
601-700	1.7880	0.0504	0.0152
701-800	1.9643	0.0046	0.0136
801-900	2.1867	0.0045	0.0139
901-1000	2.3064	0.0045	0.0132

生のreallocが遅いのは予想通りだ。一方で、冪アラインメントした場合はめちゃくちゃ早い。8, 16, 32, 64, 128, 256, 512を跨ぐところでそれぞれ1回ずつの複製が発生するので、そこだけほんのちょっとコストがかかるが、それ以外は刹那の時間しかかからない。各計測ブラケットで1万回のreallocを呼んでいるので、何もしないreallocにかかる時間は4マイクロ秒以下と言える。毎回呼んでもそんなに痛くない。ほんのちょっと工夫すれば2以外のfactorでも実装できるので、時間と空間のトレードオフは任意に調整できる。std::stringのappendメソッドの性能も同じような傾向で、めちゃ早い。reallocの方が少し早いのは、reallocのテストでは連結した末端部分の文字列の初期化をサボっているという理由も少しはあるが、本質的にreallocの方がnew/deleteの組み合わせより早いという理由が大きい。とはいえstd::stringも十分早い。

まとめ。配列のサイズを漸増させる実装を自分で書く場合、reallocの前段にサイズを調整する処理を入れるだけで、確保したサイズの属性をアプリケーション側で持たずとも、償却時間計算量をO(N)にできる。std::stringに比べて、サイズのための変数1つ分、8バイトのメモリ節約になる。多くの場合はそんなことはぜずに普通にstd::stringやstd::vectorを使えば良いのだが、小さい配列を大量に持つ場合にはこの節約は地味に効いてくる。転置索引のポスティングリストを表すのにこの方法は最適だ。それについてはまた改めて考察する。