Hatena::ブログ(Diary)

Ko-Taのバ・ー・ルのようなもの

2018-08-01

UndoRedoのメモリの最適化

f:id:Ko-Ta:20180807023358p:image

今までundo機能をなぁなぁで組んでいたら(全シリアライズデータをそのまま保持)メモリ使用量がヤバいことになったのでまじめに組み直してました。

というわけでundoとそれに使用するメモリ量の最適化のお話です。

エディタでも作らない限りundoredoのお世話になることは無いと思いますが……。

git hub

https://github.com/Ko-Ta2142/UndoRedo

まずはサンプル。

サンプルは簡単なペイントソフトでundoredoが可能です。

本題はお絵かきではなくて、キャンバスを128x128のセルで分割し、セルのシリアライズデータ(まんまピクセルデータ)をundoデータとして出力、内容の重複を検知して共有化、メモリ使用量が減る、といった一連の流れになります。

スクリーンショットだと、だいたい60〜80%ぐらいの削減が出来ています。


根幹のライブラリコードは20KB程度ととても小さい&依存性が無いので移植も簡単な内容です。

サンプルのペイントアプリのコードの方がよっぽど巨大です。(GUIアプリは仕方ないよね)

まずundoとredo

記憶するデータは、大きく分けると二種類あると思います。行動を記憶する手法(アクション)か、復元データを記憶(シリアライズ)していく手法です。

アクションの方が容量がコンパクトになる傾向ですが、undo処理そのものが編集対象に大きく依存したり、処理がかなり複雑・大規模になるので、とりあえずSaveLoadで保存と復元が可能なシリアライズデータを扱う方法で行きます。

圧縮も今回の本題では無いのでパスします。今回の最適化処理を施した後にかけるのが、容量的にも速度的にも理想的です。


シリアライズ方式であれば原理はとても単純です。作業が進めばデータをpushしていくだけ。前後の差分を気にする必要もありません。

ちょっと気を遣うとすれば、追加時に「変化が無ければ追加しない」を組み込んでおくのが現実的です。同じデータを追加させない機能があるだけで、undoredoの管理は雲泥の差で楽ちんになります。

  if UndoAdd(data) then
    // 変化があったのでundoに追加された
  else
    // 同一データなので変化無し

動作で気をつける点があるとすれば、undoのデータ保持上限を超えた場合(古いデータを破棄)、undo後に編集を行った場合(redo用に残っている前方のデータを破棄)の2つはデータの削除が発生します。

[redo data 3] (delete)
[redo data 2] (delete)
[*now] (edit!)
[undo data 1]
[undo data 0]

undo管理クラスがデータの解放まで行う都合上、データは編集オブジェクトとの関係が完全に分離されているのが望ましいでしょう。

データの解放にオブジェクトの参照が必要な構造は、オブジェクトの変化があるエディタではちょっと危険です。

シリアライズデータを小分けにする

シリアライズ方式の欠点は、サイズ・容量が大きくなりがちなことです。圧縮でなんとかなる場合もありますが、画像データなどはあまり期待出来ません。

またサイズが大きいと言うことはそれだけ生成負荷も高くなる傾向にあります。特にメモリ確保の負荷は大きくなるでしょう。

そこで、今後の布石としてまずはシリアライズデータを小分けにします。アニメーションデータ1つ!ならそれを素材や構造ごとに分けましょう。

(animation object)
  [image0 data]
  [image1 data]
  [sound0 data]
  [motion0 data]
  [motion1 data]
  [motion2 data]
...

分けただけではメモリ使用量は減ったりしてくれませんが、データの変更部分の特定、そしてなによりシリアライズデータの生成コスト(負荷)を分散、軽くすることに役立ちます。

また、小分けにしたことで生成の最適化も以下のような感じで簡単に組み込むことが出来ます。

procedure AnimationMotionClass.MakeSerialize();
begin
  if not(ChangeFlag) return;
  // make serialize data
  ...
  ChangeFlag = false;
end;
function AnimationMotionClass.SetTime(time:float);
begin
  MotionTime := time;
  ChangeFlag = true;
end;

変更が無ければ作り直さないよ。というフラグを噛ましておく常套手段が有効でしょう。

シリアライズデータの生成は未圧縮でもそこそこ重い処理なので、分散と生成の最適化(キャッシュ)は速度面できわめて重要です。

データ(メモリ)サイズの最適化

undoデータはその性質上、全く変更されていないデータの部分が大半を占めることになります。

(undo->)
[MotionData0]*---------*****
[MotionData1]---*******----*
[MotionData2]---------------
pass : -
changed : *

こんなかんじで大半が1つ前の同一のデータが並びます。

1つ前との差分方式などXOR比較など様々な方式が思い浮かびますが、比較速度、複製速度、扱いやすさ(取り出し)で同一データの場合は共有化させることで落ち着きました。

上の例なら以下のような感じに共有化します。

[data0]*---------*****
[data0]011111111123456
number : data class

実装も極力シンプルに、メモリ上のバイナリデータ(MemoryStream)から最適化されたクラスを取得、あとはそれを介してバイナリにアクセスするだけです。

  CacheClear;
  CacheSerializeData := object.GetSerializeData;
  CacheUndoData := MemoryOptimizePool.Get(CacheSerializeData); // get optimize data class

データを保持するクラスは自身の複製を作ったら参照カウンタを+1、解放されたら-1、0で実際に解放するよくある構造です。

ガベージコレクトというよりwindowsのcomみたいなヤツですね。

// replicate 複製
function MemoryBlock.Replicate();
begin
  AddRef();
  return(self);
end;

procedure MemoryBlock.AddRef();
begin
  RefCount++;
end;
procedure MemoryBlock.Release();
begin
  RefCount--;
  if RefCount = 0 then self.Free;
end;

複製と解放のコストがほぼ0(カウンタを+-1するだけ)なので、大量に複製する事になるundoに向いてます。

また、(共有化済み)データの比較がアドレス比較で済むので、内容に変化があったか(undoに追加して良いか)を検知が限りなく低コストで済みます。

嬉しいですね。

procedure MemoryBlock.Compare(other:TMemoryBlock):boolean; inline;
begin
  // self === other
  Result := pointer(self) = pointer(other);
end;

わざわざ関数作ってやることでは無いですが。

管理プールについて

共有化されたメモリデータはプールに登録、管理されます。

  // create
  pool := TmemoryBlockPool.Create;
  // get block from memory pointer
  block := pool.GetBlock(ptr,size);
  // free block
  pool.FreeBlock(block);
  // free
  pool.Free;

基本はシングルトンで動き、あのオブジェクトのデータもこのオブジェクトのデータもなんでも突っ込んで、雑に使って良いように設計されています。

無駄に重複しそうなものがあれば、undo以外のモノをぶち込んでも問題ありません。


雑に使っても良いようにプールとしてはそれなりに多いデータを保持することになります。だいたい1万個ぐらいは想定の範囲でなければなりません。

データの登録削除もそれなりに早くて、かつ検索が早い方式として、BinaryTree(二分木)を使用しています。

二分木と言っても、「同値を入れることが出来る」「削除が可能」なものが必要で、ちょっとアルゴリズムが複雑です。

ライブラリに無ければ、リニア(ふつうのarray配列)でも十分な速度が出てたので、それでもいいかなと思います。

最後に

ツールを作っていると億劫になりがち(出来れば実装したくないなぁ)なundoredoですが、わりと楽出来るように落とし込めたと思います。

オブジェクトの方にシリアライズ出力を書くのが億劫ではあるんですが、undoredoについてはマルチプラットフォーム(ビッグ、リトルエディアント問題)を無視出来るので(データを他に持っていったりしないので)、既にSaveLoadがあればそのデータを使って、無ければ雑にバイナリに書き込むのを用意して楽するのが良いと思います。雑で。