Hatena::ブログ(Diary)

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

2018-08-21

multi-core threading

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

昔にも書いたマルチコアスレッドコードです。マルチコアによる分散処理を行います。

長らく修正を反映出来ていなかったのでgithubに上げてまとめました。

github

  • github multi-core and muti-threading

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


簡単なマルチコアスレッディング管理用クラスです。

マルチコアとマルチスレッドの違いは、処理をコア(論理)に割り当ててるかどうかどうかだけの違いです。

コアに割り当てない設定も可能ですが使う機会は無いでしょう。

性能については、60fpsでの使用に耐えうるモノで、開始と待機の精度はそれほど高くありませんが、待機のCPU使用率が低めの、バランス型です。

もっと精度が欲しい場合はsleep(0)でポーリングすればいいだけなのでこのライブラリは要らないと思います。


このライブラリはWindowsXPで動作するように、XPまでの命令で組まれています。

なので、物理コアと論理コアの判別出来ず、OSに委ねられています。

マルチコア処理

マルチコアによる分散処理を行うには、基本的にスレッドをコアに割り当てるだけ。

windowsの場合は割り当てるAPIは2つあります。

  • SetThreadAffinityMask

https://msdn.microsoft.com/ja-jp/library/cc429346.aspx

DWORD SetThreadAffinityMask (
  HANDLE hThread,             // 操作対象スレッドのハンドル
  DWORD dwThreadAffinityMask  // スレッドアフィニティマスク
);
  • SetThreadIdealProcessor

https://msdn.microsoft.com/ja-jp/library/cc429348.aspx

DWORD SetThreadIdealProcessor(
  HANDLE hThread,         // スレッドのハンドル
  DWORD dwIdealProcessor  // 理想的なプロセッサ番号
);

SetThreadIdealProcessorがよく使われます。

スレッドを論理コア番号に紐付けし、使用中であれば他の空きコアを試みるので、4/8コアのような一部を使う場合にとても素直で賢い挙動を行ってくれます。

ほぼこちらの使用で問題ないでしょう。

もしCPUコアの全てを使用したい場合は、SetThreadAffinityMaskが良いでしょう。

これはスレッドに使用しても良いコア番号をビットマスクで指定します。つまり4コアなら、1,2,4,8とすることで全てのコアに振り分けます。

1+2=3で1と2コアの両方の使用を許可出来ます。使い方としては良い案が浮かびませんが、今は1物理コア2論理コアのハイパースレッディングが主なので、物理コア単位にすると安定するかも知れません。


このライブラリではCPUのコアをほぼ全部使う場合以外はSetThreadIdealProcessorを使うようになっています。

初期化

使い方は簡単です。

初期化はグローバル関数を呼ぶだけです。生成されるスレッド管理クラスは、1アプリケーションにつき1つだけのシングルトンです。

アプリケーション終了時やコア数を変えるときは、解放関数を呼んでください。

  // initialize
  _MultiCoreInitialize(4);  // 実際の生成スレッド数はCPUコア数の最大値に丸め込まれます
  corecount := _MultiCoreManager.Count;
...
  // finalize
  _MultiCoreFinalize;

タスクの登録

マルチスレッド処理の場合、処理を関数にまとめて、その関数ポインタとして管理クラスに登録します。

登録なのでまだ実行はされません。

  for i:=0 to TaskCount-1 do
    _MultiCoreManager.Add( MultiCore_HorizonBlur , @TaskRecord[i] );

与える関数で気をつけるところはマルチスレッドプログラミングと同じです。順序を伴う処理は含まないこと、読み込みは良いけど書き込みは他と重複しないこと、あたりは守る必要があります。

また、与える関数ポインタには、自由に使えるポインタ型の引数が備わっており、タスクに渡したい変数内容などはポインタ(アドレス)にして受け渡します。

上記のように構造体を定義して渡すのが一般的です。

type
  TMultiCoreData = record
    // scanline area
    StartIndex,EndIndex : integer;
  end;
  PMultiCoreData = ^TMultiCoreData;

実行と同期

タスクが登録出来たら実行、そして大事なのが同期です。

全ての処理の完了を待つ必要があります。

  _MultiCoreManager.Start; // start execute task
  _MultiCoreManager.Sync;  // sync all task finished

Startの後にすぐSyncを呼ぶ必要はありません。待ち時間にメインスレッドでなにか処理をさせたいなら間に処理を挟むと良いでしょう。


以上がマルチコア処理の1サイクルです。

仮想負荷値を与える

このライブラリにはシンプルな負荷によるタスクの振り分け機能を持っています。

  _MultiCoreManager.Add( hogefunc,@hogerecord , 100 );

例えば、重い処理と軽い処理があった場合、重さが均等になるようコアに割り当てられます。

core0 : [task][task][task]
core1 : [task][task][hevytask]
core2 : [task][hevytask][task]
core3 : [task][task][hevytask]

イメージとしてはこのように構築します。指定無しはweight:1とされます。


だいたいタスクは均等になるように調整して渡すことになるので、この機能は有用そうに見えますが、実際使うことは無いでしょう……。

パフォーマンスを求めるならコア数に対して平等に処理を分割するコードを書くので尚更不要です。

待機と同期精度のお話

昔のバージョンもこれとあまり大きな変化はありませんが、何が変わったかというとタスクが無い状態での待機処理です。

割と面倒なのがこの待機処理だったりします……。


普通の使用なら、CPU使用率は度外視できるので、セマフォで同期を取ってタスク開始フラグをポーリングするだけでOKなので簡単です。

また、1回の処理限定なら、終わったらスレッドをそのままterminate(終わり)させておけば何の問題もありません。

しかし60fps環境で使用する場合は要求がちょっとタイトです。

  • 16ms周期で使用されるためスレッドは使い回すこと。
  • start/syncの応答精度が早い、個々のスレッドの待機と復帰が早いこと。
  • 待機状態でのCPU使用率が低いこと。(負荷ではなく使用率です)

の3条件です。


上でも出たフラグポーリングですが、よくあるのが以下のようなコードです。

  while true do
  begin
    semaphore.lock;
    f := StartFlag;
    semaphore.unlock;
    if f then break;
    // sleep
    sleep(1);   // sleep(0);
  end;

StartFlagがtrueになったら抜けるだけですがsleepが問題です。

応答を早めたいならsleep(0)を使いたいところですが、実際はCPU使用率が恐ろしく跳ね上がるのでsleep(1)が妥協点です。

sleep(1)の場合1msで同期が終わるかというと、スレッド間の微妙な誤差もあるので倍の2msぐらいに膨れ上がることは考慮しなければなりません。

更にstartとsyncでそれぞれ判定が入ることを考えれば、最大2+2=4ms。

更にwindowsは3msが最小単位だとかなんとかあるので、もしかすると3+3=6msになるかも。

60fpsで動作するなら、約16msのうち4ms(6ms)が消えるのは痛い出費です。


というわけで、実際のコードはちょっと変な感じですが、semaphoreであるクリティカルセクションの二重ロック(デッドロック)による永久待ちを基本にしています。

// main thread
  _MultiCoreManager.Start; ( wait.unlock )
  _MultiCoreManager.Sync; **1

// sub thread
  wait.lock;  // lock 1
  while true do
  begin
    wait.lock;  // lock 2. wait.
    wait.unlock;  // lock 1-1=0
    // flag check
    if (flagcheck) then break;
    ...
    sleep(0);
  end;
  TaskExecute;
  wait.lock;  // lock=1 **1

ただし、この方法は不完全ですり抜けることがあります。

そこですり抜けからデッドロックされるまでのちょっとの間だけ、精度の高いsleep(0)によるフラグポーリングを行います。

あれ?

マウスでぐりぐりする最初の1回目だけ処理時間が40msとかやたらかかることがあります。

この症状、どうやらクリティカルセクションの挙動によるところのようです。

待ち時間が短いとキビキビ動くんですが、待ち時間が長いと判定を甘くして地球に優しいモードになるようです。

  • InitializeCriticalSectionAndSpinCount - spin count

https://msdn.microsoft.com/ja-jp/library/cc429225.aspx

スピンカウントの値で調整してくださいね!と言うことですが、単位が不明なので正直解らないです:-Q

だいたい500ms過ぎたら寝る感じなので、60fpsなりで動く分にはキビキビ動くので、このあたりは妥協しましょう……。

尚、CPU負荷率が常に高い場合だとこの待機時間が緩和されます。このあたりはハードウェアな領域なのでこれ以上足を突っ込まない方が良さそうです。


ちなみに、普通は2でデッドロック解除待ちになりますが、任意の数値にも出来るそうです。

各スレッドごとにセマフォ持つよりは一本化する方が良い結果が出そうなのでそのうちやってみますが、更新が無かったら……期待値は得られなかったと言うことで。

暈かし処理

いつか触れようと思いますが、サンプルの暈かし処理には "prefix sum" という、値を加算して蓄積していく手法を使用しています。

原理は以下のページが詳しいです。動画に至っては英語では無いですが、図解でなんとなくわかるかと思います。

  • prefix sum

https://en.wikipedia.org/wiki/Prefix_sum

  • 2d sum quaries

https://www.youtube.com/watch?v=hqOqr6vFPp8

サンプルは横方向しか暈かしていませんので1次元です。ボックスの左端と右端を読み込めば、差分でボックス内の合計値がわかるという優れものです。

暈かしのボックスサイズが変わっても一律の処理負荷で行うアルゴリズムとして有名です。

shaderでやるならnVIDIAのサンプルを見るのが良いでしょう。

  • nVIDIA

https://docs.nvidia.com/gameworks/index.html#gameworkslibrary/graphicssamples/d3d_samples/d3dcomputefiltersample.htm

下ごしらえに加えて、RGBの深度ビット数が増える、ハードウェアなら浮動小数バッファが必要になるので、ちょっと要求が高いのが難点ですが、暈かしをリアルタイムで出来るようになったのは昨今の進化を感じます。

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があればそのデータを使って、無ければ雑にバイナリに書き込むのを用意して楽するのが良いと思います。雑で。

2017-10-25

spine morph-target

本家より良い返事が貰えたので、経緯を残しておきます。そのうち使えるようになるそうです。ありがたし!


ver3.6のspineを弄っているとメッシュデフォームがあるものの、口パクや表情でよく使うモーフターゲット(morph-target)がないので、固定的なものは力業でなんとかなるとしても、動的な表情変化などの実現が厳しいなぁと気づくと思います。

なんとかしたいですよねナナチ。

幸いランタイムのソースコードがフルオープンなので中を覗けますし、(ライセンスの範囲内で)勝手に弄ってもOKなので、なんとかできないかなーと休日眺めてみました。

サンプル

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

どういったものかはサンプルで。

  • spine-c morph-target customize sample

https://1drv.ms/u/s!AvtcMsC8irYBgzJkqmizB2me52T1

まず過去ログ

フォーラムの過去ログ(英語)を眺めてみたら、過去に2度ほど話題には上がったみたいです。

少なからず同じような悩みはあったみたいですね。

まずモーフターゲットが実装できるか

モーフターゲットを実現させるにはいくつかの条件が必要です。

  • 変形前のベースとなる形状が必要

名前の通りベースとなる”ターゲット”が必要になります。これは変形前の形状で、変形後との差分の計算に使用されます。

差分はそのままベースに加算されていき、1つのオブジェクトに変形が複数ミックスされていきます。

diff? = Animation? - base
out = base + diffA + diffB + diffC + diffD ...

みたいな感じです。

幸いspineにはベースが存在します。エディタではSETUPとして部品を組み立てるモードがありますね。あれです。あれを使いましょう。

プログラム上だとちょっとわかりにくいですがskeletonから追跡できます。Animation.cを見れば手っ取り早いかなと思います。

  • 変形後の形状もベースと同じ構造をしていること

これはSETUPから変形させて作られたアニメーションのことを指します。

モーフターゲットの場合はベースと構造が同じでなくてはいけません。メッシュなら頂点数とかポリゴンの張り方とか。

幸いspineも同じガイドラインを敷いているので問題無さそうです。

  • それら複数の形状を指定できる環境

複数合成するのでその土壌がなければいけません。幸いアニメーションはトラックという概念で複数扱えるので問題ありません。

  • ということで

エディタ上では難しいけど、ランタイムのアニメーショントラックに仕込めば実現できそうです。

エディタだとプレビューのあそこですね。タイムラインではありません。

実装

spine-c ver3.6を使用します。実装の大半はAnimation.cになります。

「void _spDeformTimeline_apply」あたりを見てみると分かりやすいと思います。

前半と中盤は定義キーが無い前と後ろの処理、要するに例外処理なので飛ばします。

一番最後あたりにアニメーションの合成にあたるコードがあります。

for (i = 0; i < vertexCount; i++) {
      float prev = prevVertices[i];
      float v = prev + (nextVertices[i] - prev) * percent;
      vertices[i] += (v - vertices[i]) * alpha;
}

prevVerticesが現在位置より後方の変形情報、nextVerticesが現在位置より前方の変形情報です。

percentがキー間のブレンド率なのでvが現在地点での変形座標。alphaがモーションのブレンド率なのでアニメーション間の合成だけ抜き出せば

out = out + (v - out) * alpha

と単純な構造です。ここをモーフターゲットに改良するだけです。


モーフターゲットはベースとなる変形前の座標が必要になります。

spineでいえばSETUPですが、このコードの上あたりを見ると―

case SP_MIX_POSE_SETUP:
    if (!vertexAttachment->bones) {
        memcpy(vertices, vertexAttachment->vertices, vertexCount * sizeof(float));
    } else {
        for (i = 0; i < vertexCount; i++) vertices[i] = 0;
    }
...

まんまがあります。

「vertexAttachment->vertices」がSETUP、変形前のベース情報になります。

SP_MIX_POSE_SETUPは最初に投げられるもので、変形前の状態を変形バッファにコピーしてる感じです。


これで必要な要素は揃いました。

あとは以下の公式に変形すればいいだけです。

out = out + (A - SETUP) * alpha

なので

float* setupVertices = vertexAttachment->vertices;
for (i = 0; i < vertexCount; i++) {
    float prev = prevVertices[i];
    float v = prev + (nextVertices[i] - prev) * percent;
    vertices[i] += (v - setupVertices[i]) * alpha;
}

となります。おわり。


本当はもうちょっと複雑

アルゴリズムの話は以上でおしまいですが、実際はもうちょっと複雑です。計算が複雑というわけではなく、例外処理、最適化処理との相性、言語的な部分などなど。

今までアニメーションは上書きだったので、alpha1.0だとそれより前のアニメーション処理要らないですね!なども組み込まれているので対処が必要です。

実際に組み込むには20カ所ほど変更や修正が必要です。

実装されるまで待ちましょう :Q