前置き
この記事は自作の空間分割マップ HashCellIndex の性能評価です。
性能評価に用いているミニアプリ Boids-ECS の概略については下記を参照してください。
[Unity] Entities 0.50 環境で Boids Simulation を再設計した話
リポジトリはGitHubで公開しています。
HashCellIndex は Assets/Script/ECS/HashCellIndex に置いてあり、asmdef も定義済みです。
もしよろしければMITライセンスでご利用ください。
起動後、左下の Benchmark Start を押せば所定のFPSを維持できるところまでBoidsが増えます。
この記事では60FPSを維持できるBoids数をスコアとして扱います。
パフォーマンス計測結果
計測環境:
| Parts | Model | Remark |
|---|---|---|
| CPU | Core i7 12700 | PL1=PL2=202W (実働約150W) |
| Memory | 32GB DDR4-3200 | |
| GPU | GTX1070 |
結果:
※a worker thread のほか main thread も使われるので、実際のthread数はグラフの横軸+1になります。
※b MergedCell-NeighborList (m6): 今回の条件ではMergeSeize=6
※c Boids数9万ぐらいでGTX1070の方が限界になるので、高負荷時にはカメラ操作(WASDまたはマウスドラッグ)であらぬ方向に向けてカリングさせてテストしました。
まず結論
-
分布がまばらなもの(Player, Bossなどで判定点が一つの場合)の周りを探索
-> Cell の効果は望めないので普通にEntities.ForEach()などでNeighborListだけ使う。 -
密集しているもの同士(多数のミサイルを機銃で迎撃、大きなボスで別々な当たり判定が多数、など)を近傍探索
-> MergedCell-NeighborList を使う。セルサイズ、マージ数は場合に合わせて適宜調整する。
考察
各ComputePlanについて:
- Direct: 直接法。計算量 $O(n^2)$ 。実装は単純なのでテストには向く。
- CellIndex: 空間をセルに区切って近傍探索を高速化する。計算量 $O(n)$ 。ただしメモリ使用量も $O(n)$ 。
- NeighborList を構築するもの
- Entity-NeighborList
- Cell-NeighborList
- Cell-Cell
- MergedCell-NeighborList
- その場で相互作用を計算するもの
- Combined-Cell-NeighborList
- Combined-Cell-Cell
- NeighborList を構築するもの
▽ Direct
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_Direct : SystemBase
{
private EntityQuery query;
protected override void OnCreate()
{
base.OnCreate();
query = GetEntityQuery(new EntityQueryDesc
{
All = new[] {
ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<NeighborsEntityBuffer>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_Direct>()
}
});
}
private struct NeighborDetectionDataContainer
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[DeallocateOnJobCompletion]
[ReadOnly]
public NativeArray<Entity> entitiesGlobal;
}
protected override void OnUpdate()
{
var common_data = new NeighborDetectionDataContainer
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
entitiesGlobal = query.ToEntityArray(Allocator.TempJob),
};
// args for Entities.ForEach() must be ordered as (Entity), (ref args), and (in args).
Dependency = Entities.
WithName("NeighborDetectionJob").
WithAll<BoidType, Tag_ComputeNeighbors_Direct>().
WithBurst().
ForEach(
(Entity entity, ref DynamicBuffer<NeighborsEntityBuffer> neighbors, in Translation position, in Velocity velocity) =>
{
neighbors.Clear();
float3 pos0 = position.Value;
float3 fwd0 = math.normalize(velocity.Value);
float r2_search = common_data.distThresh * common_data.distThresh;
for (int i = 0; i < common_data.entitiesGlobal.Length; i++)
{
var target = common_data.entitiesGlobal[i];
if (entity == target) continue;
float3 pos1 = common_data.positionFromGlobalEntity[target].Value;
var to = pos1 - pos0;
var dist2 = math.lengthsq(to);
if (dist2 < r2_search)
{
var dir = math.normalize(to);
var prod = math.dot(dir, fwd0);
if (prod > common_data.prodThresh)
{
neighbors.Add(new NeighborsEntityBuffer { entity = target });
}
}
}
}).ScheduleParallel(Dependency);
}
}
Tagを追加した程度で、hecomiさんの実装とほぼ同じです。
ひとつだけ計算量が $O(n^2)$ で、コア数を増やしても 5000 -> 11000 程度にしか性能が改善しません。
ただし実装がもっとも単純でバグを作りにくいことがこの手法の価値なので、高速化版の動作確認のため誰もが一度は書くと思います。
また、対象の数が少ないことがあらかじめわかっているならあえてこの手法を使うのもアリでしょう。
▽ Entity-NeighborList
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_Entity_NeighborList : SystemBase
{
private struct NeighborDetectionDataContainer
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
public void GetNeighborList(float3 pos, NativeList<Entity> list)
{
list.Clear();
if (cellIndex.Box.IsInside(pos)) cellIndex.GetNeighborList(pos, distThresh, Boundary.Open, list);
}
}
protected override void OnUpdate()
{
//--- search neighbors
var common_data = new NeighborDetectionDataContainer
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
cellIndex = CellIndex_Bootstrap.HashCellIndex,
};
Dependency = Entities.
WithName("NeighborDetectionJob_CellIndex_Entity_NeighborList").
WithAll<BoidType, Tag_ComputeNeighbors_CellIndex_Entity_NeighborList>().
WithBurst().
ForEach(
(Entity entity, ref DynamicBuffer<NeighborsEntityBuffer> neighbors, in Translation position, in Velocity velocity) =>
{
neighbors.Clear();
float3 pos0 = position.Value;
float3 fwd0 = math.normalize(velocity.Value);
if (!common_data.cellIndex.Box.IsInside(pos0)) return;
var entitiesForSearch = new NativeList<Entity>(32, Allocator.Temp);
common_data.GetNeighborList(pos0, entitiesForSearch);
var positionsForSearch = ComponentDataUtility.GatherComponentData(common_data.positionFromGlobalEntity,
entitiesForSearch, Allocator.Temp);
NeighborDetectionFunc.SearchNeighbors(entity,
pos0,
fwd0,
common_data.distThresh,
common_data.prodThresh,
entitiesForSearch,
positionsForSearch,
neighbors);
entitiesForSearch.Dispose();
positionsForSearch.Dispose();
}).ScheduleParallel(Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
static internal class NeighborDetectionFunc
{
internal static void SearchNeighbors(Entity entity, float3 pos0, float3 fwd0,
float distThresh, float prodThresh,
NativeArray<Entity> neighborsFromCell,
NativeArray<Translation> positionsForSearch,
DynamicBuffer<NeighborsEntityBuffer> neighbors)
{
float r2_search = distThresh * distThresh;
for (int i = 0; i < neighborsFromCell.Length; i++)
{
var target = neighborsFromCell[i];
if (entity == target) continue;
float3 pos1 = positionsForSearch[i].Value;
var to = pos1 - pos0;
var dist2 = math.lengthsq(to);
if (dist2 < r2_search)
{
var dir = math.normalize(to);
var prod = math.dot(dir, fwd0);
if (prod > prodThresh)
{
neighbors.Add(new NeighborsEntityBuffer { entity = target });
}
}
}
}
}
ComponentDataUtility.cs
static internal class ComponentDataUtility
{
internal static NativeArray<T> GatherComponentData<T>(ComponentDataFromEntity<T> data_from_entity,
NativeArray<Entity> entities,
Allocator alloc)
where T : unmanaged, IComponentData
{
var array = new NativeArray<T>(entities.Length, alloc, NativeArrayOptions.UninitializedMemory);
GatherComponentDataImpl(data_from_entity, entities, array);
return array;
}
private static void GatherComponentDataImpl<T>(ComponentDataFromEntity<T> data_from_entity,
NativeArray<Entity> entities,
NativeArray<T> data_array)
where T : unmanaged, IComponentData
{
for (int i = 0; i < entities.Length; i++)
{
data_array[i] = data_from_entity[entities[i]];
}
}
}
Entityについてループを回すところは Direct と同様で、ネイバーリストの候補を HashCellIndex から受け取り相対位置を確認します。
アルゴリズムは $O(n)$ に改善されましたがデータに関する事前知識はとくに利用していません。よって高速化はそこそこですが性能も状況にあまり左右されないと思われます。以降に取り扱うCellを利用した実装は「Cell内に同じネイバーリストを利用するものが複数ある」という前提を利用したものなので、そのような状況になければこの実装を採用することになるでしょう。
▽ Cell-NeighborList
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_Cell_NeighborList : SystemBase
{
private NativeList<PosIndex> cell_list;
protected override void OnCreate()
{
base.OnCreate();
RequireForUpdate(
GetEntityQuery(ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<NeighborsEntityBuffer>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_CellIndex_Cell_NeighborList>()));
cell_list = new NativeList<PosIndex>(Allocator.Persistent);
}
protected override void OnDestroy()
{
base.OnDestroy();
cell_list.Dispose();
}
[BurstCompile]
private struct NeighborDetectionJob_Cell_NeighborList : IJobParallelFor
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public ComponentDataFromEntity<Velocity> velocityFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
[ReadOnly]
public NativeArray<PosIndex> cellList;
[NativeDisableContainerSafetyRestriction]
public BufferFromEntity<NeighborsEntityBuffer> neighborsFromGlobalEntity;
public void Execute(int i_job)
{
var index = cellList[i_job];
var entitiesInCell = new NativeList<Entity>(64, Allocator.Temp);
cellIndex.GetValuesInCell(index, entitiesInCell);
if (entitiesInCell.Length <= 0)
{
entitiesInCell.Dispose();
return;
}
var entitiesForSearch = new NativeList<Entity>(256, Allocator.Temp);
cellIndex.GetNeighborList(index, distThresh, Boundary.Open, entitiesForSearch);
//--- gather data in cell
var positionsInCell = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesInCell, Allocator.Temp);
var velocitiesInCell = ComponentDataUtility.GatherComponentData(velocityFromGlobalEntity, entitiesInCell, Allocator.Temp);
//--- gather data for search
var positionsForSearch = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesForSearch, Allocator.Temp);
//--- search neighbors by cell to neighbors from cellIndex
for (int i_entity = 0; i_entity < entitiesInCell.Length; i_entity++)
{
var neighbors = neighborsFromGlobalEntity[entitiesInCell[i_entity]];
neighbors.Clear();
NeighborDetectionFunc.SearchNeighbors(entitiesInCell[i_entity],
positionsInCell[i_entity].Value,
math.normalize(velocitiesInCell[i_entity].Value),
distThresh,
prodThresh,
entitiesForSearch,
positionsForSearch,
neighbors);
}
entitiesInCell.Dispose();
entitiesForSearch.Dispose();
positionsForSearch.Dispose();
positionsInCell.Dispose();
velocitiesInCell.Dispose();
}
}
protected override void OnUpdate()
{
//--- search neighbors
var cellIndex = CellIndex_Bootstrap.HashCellIndex;
cellIndex.GetContainsIndexList(cell_list);
var neighborDetectionJob = new NeighborDetectionJob_Cell_NeighborList()
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
velocityFromGlobalEntity = GetComponentDataFromEntity<Velocity>(true),
cellIndex = cellIndex,
cellList = cell_list,
neighborsFromGlobalEntity = GetBufferFromEntity<NeighborsEntityBuffer>(),
};
Dependency = neighborDetectionJob.Schedule(cell_list.Length,
CellIndex_Bootstrap.UpdateBatchSize(cell_list.Length),
Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
同じセル内のBoidsは同じネイバーリスト候補について確認を行うため、EntityごとではなくCellごとにループを回す実装をとったものです。
当初の実装ではすべてのCellについてループを回していましたがあまり速くなく、Boidsの密度から半分以上のCellが空だったのでBoidsを含むセルをリストアップしたあとこのリストでループを回すようにしたところ大きく改善しました。
ネイバーリスト候補を複数回計算に使用するためキャッシュ効率がよく、Entityでループを回した場合と比べておよそ２倍ほど高速化しました。
▽ Cell-Cell
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_Cell_Cell : SystemBase
{
private NativeList<PosIndex> cell_list;
protected override void OnCreate()
{
base.OnCreate();
RequireForUpdate(
GetEntityQuery(ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<NeighborsEntityBuffer>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_CellIndex_Cell_Cell>()));
cell_list = new NativeList<PosIndex>(Allocator.Persistent);
}
protected override void OnDestroy()
{
base.OnDestroy();
cell_list.Dispose();
}
[BurstCompile]
private struct NeighborDetectionJob_Cell_Cell : IJobParallelFor
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public ComponentDataFromEntity<Velocity> velocityFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
[ReadOnly]
public NativeArray<PosIndex> cellList;
[NativeDisableContainerSafetyRestriction]
public BufferFromEntity<NeighborsEntityBuffer> neighborsFromGlobalEntity;
public void Execute(int i_job)
{
var index = cellList[i_job];
var entitiesInCell = new NativeList<Entity>(64, Allocator.Temp);
cellIndex.GetValuesInCell(index, entitiesInCell);
if(entitiesInCell.Length <= 0)
{
entitiesInCell.Dispose();
return;
}
for(int j = 0; j < entitiesInCell.Length; j++)
{
neighborsFromGlobalEntity[entitiesInCell[j]].Clear();
}
var searchIndexList = new NativeList<PosIndex>(64, Allocator.Temp);
var entitiesForSearch = new NativeList<Entity>(64, Allocator.Temp);
var positionsForSearch = new NativeList<Translation>(64, Allocator.Temp);
//--- gather data in cell
var positionsInCell = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesInCell, Allocator.Temp);
var velocitiesInCell = ComponentDataUtility.GatherComponentData(velocityFromGlobalEntity, entitiesInCell, Allocator.Temp);
//--- search neighbors by cell to cell
cellIndex.GetSearchIndexList(index, distThresh, Boundary.Open, searchIndexList);
for (int i_cell = 0; i_cell < searchIndexList.Length; i_cell++)
{
entitiesForSearch.Clear();
cellIndex.GetValuesInCell(searchIndexList[i_cell], entitiesForSearch);
//--- gather data for search target cell
positionsForSearch.ResizeUninitialized(entitiesForSearch.Length);
for(int i=0; i<entitiesForSearch.Length; i++)
{
positionsForSearch[i] = positionFromGlobalEntity[entitiesForSearch[i]];
}
//--- detect neighbors
for (int i_entity = 0; i_entity < entitiesInCell.Length; i_entity++)
{
NeighborDetectionFunc.SearchNeighbors(entitiesInCell[i_entity],
positionsInCell[i_entity].Value,
math.normalize(velocitiesInCell[i_entity].Value),
distThresh,
prodThresh,
entitiesForSearch,
positionsForSearch,
neighborsFromGlobalEntity[entitiesInCell[i_entity]]);
}
}
searchIndexList.Dispose();
entitiesInCell.Dispose();
entitiesForSearch.Dispose();
positionsForSearch.Dispose();
positionsInCell.Dispose();
velocitiesInCell.Dispose();
}
}
protected override void OnUpdate()
{
//--- search neighbors
var cellIndex = CellIndex_Bootstrap.HashCellIndex;
cellIndex.GetContainsIndexList(cell_list);
var neighborDetectionJob = new NeighborDetectionJob_Cell_Cell()
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
velocityFromGlobalEntity = GetComponentDataFromEntity<Velocity>(true),
cellIndex = cellIndex,
cellList = cell_list,
neighborsFromGlobalEntity = GetBufferFromEntity<NeighborsEntityBuffer>(),
};
Dependency = neighborDetectionJob.Schedule(cell_list.Length,
CellIndex_Bootstrap.UpdateBatchSize(cell_list.Length),
Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
前述のCell-NeighborListの亜種で、ネイバーリスト候補をまとめて一つの配列にするのではなく、各セルごとに順次計算するパターンです。
3次元で隣接セルは3x3x3=27セルあり、相対的にCellが大きく一つのセル内に多数の対象がある条件ではこれらのセルをひとまとめにするとキャッシュからあふれて性能が低下する場合があり、その問題を回避するパターンです。
今回の条件ではBoidsの探索半径が小さく1つのCell内にたかだか数個のBoidsしかいなかったのでループ分割によるオーバーヘッド増加により、Cell-NeighborListに比べわずかに低速でした。
▽ Combined-Cell-NeighborList
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_Combined_CNL : SystemBase
{
private NativeList<PosIndex> cell_list;
protected override void OnCreate()
{
base.OnCreate();
RequireForUpdate(
GetEntityQuery(ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<Acceleration>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_CellIndex_Combined_CNL>()));
cell_list = new NativeList<PosIndex>(Allocator.Persistent);
}
protected override void OnDestroy()
{
base.OnDestroy();
cell_list.Dispose();
}
[BurstCompile]
private struct NeighborDetectionJob_Combined : IJobParallelFor
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly] public float alignmentWeight;
[ReadOnly] public float cohesionWeight;
[ReadOnly] public float separationWeight;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public ComponentDataFromEntity<Velocity> velocityFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
[ReadOnly]
public NativeArray<PosIndex> cellList;
[NativeDisableContainerSafetyRestriction]
public ComponentDataFromEntity<Acceleration> accelerationFromGlobalEntity;
private struct TmpForceValue
{
public float3 Alignment, Cohesion, Separation;
public int Count;
public void Clear()
{
Alignment = 0f;
Cohesion = 0f;
Separation = 0f;
Count = 0;
}
public float3 GetAccel(Translation pos0, Velocity vel0,
float alignmentWeight,
float cohesionWeight,
float separationWeight)
{
if (Count <= 0) return float3.zero;
float count_inv = 1f / Count;
return (Alignment * count_inv - vel0.Value) * alignmentWeight
+ (Cohesion * count_inv - pos0.Value) * cohesionWeight
+ (Separation * count_inv) * separationWeight;
}
}
public void Execute(int i_job)
{
var index = cellList[i_job];
var entitiesInCell = new NativeList<Entity>(64, Allocator.Temp);
cellIndex.GetValuesInCell(index, entitiesInCell);
if (entitiesInCell.Length <= 0)
{
entitiesInCell.Dispose();
return;
}
//--- gather data in cell
var positionsInCell = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesInCell, Allocator.Temp);
var velocitiesInCell = ComponentDataUtility.GatherComponentData(velocityFromGlobalEntity, entitiesInCell, Allocator.Temp);
var entitiesForSearch = new NativeList<Entity>(64, Allocator.Temp);
cellIndex.GetNeighborList(index, distThresh, Boundary.Open, entitiesForSearch);
//--- gather data for search
var positionsForSearch = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesForSearch, Allocator.Temp);
var velocitiesForSearch = ComponentDataUtility.GatherComponentData(velocityFromGlobalEntity, entitiesForSearch, Allocator.Temp);
//--- result buffer
var tmpForceInCell = new NativeArray<TmpForceValue>(entitiesInCell.Length, Allocator.Temp);
//--- compute interaction with neighbors
for (int i_entity = 0; i_entity < entitiesInCell.Length; i_entity++)
{
var force_tmp = tmpForceInCell[i_entity];
ComputeInteraction(entitiesInCell[i_entity],
positionsInCell[i_entity].Value,
math.normalize(velocitiesInCell[i_entity].Value),
distThresh,
prodThresh,
entitiesForSearch,
positionsForSearch,
velocitiesForSearch,
ref force_tmp);
tmpForceInCell[i_entity] = force_tmp;
}
//--- writeback buffered acceleration
for (int i = 0; i < entitiesInCell.Length; i++)
{
var entity = entitiesInCell[i];
var acc = accelerationFromGlobalEntity[entity].Value;
acc += tmpForceInCell[i].GetAccel(positionsInCell[i], velocitiesInCell[i],
alignmentWeight, cohesionWeight, separationWeight);
accelerationFromGlobalEntity[entity] = new Acceleration { Value = acc };
}
entitiesInCell.Dispose();
positionsInCell.Dispose();
velocitiesInCell.Dispose();
entitiesForSearch.Dispose();
positionsForSearch.Dispose();
velocitiesForSearch.Dispose();
tmpForceInCell.Dispose();
}
static void ComputeInteraction(Entity entity, float3 pos0, float3 fwd0,
float distThresh, float prodThresh,
NativeArray<Entity> neighborsFromCell,
NativeArray<Translation> positionsForSearch,
NativeArray<Velocity> velocitiesForSearch,
ref TmpForceValue tmp_value)
{
float r2_search = distThresh * distThresh;
for (int i = 0; i < neighborsFromCell.Length; i++)
{
var neighbor = neighborsFromCell[i];
if (entity == neighbor) continue;
float3 pos1 = positionsForSearch[i].Value;
var to = pos1 - pos0;
var dist2 = math.lengthsq(to);
if (dist2 < r2_search)
{
var dir = math.normalize(to);
var prod = math.dot(dir, fwd0);
if (prod > prodThresh)
{
//--- alignment
tmp_value.Alignment += velocitiesForSearch[i].Value;
//--- cohesion
tmp_value.Cohesion += positionsForSearch[i].Value;
//--- separation
tmp_value.Separation += (-dir);
//--- count
tmp_value.Count++;
}
}
}
}
}
protected override void OnUpdate()
{
//--- search neighbors
var cellIndex = CellIndex_Bootstrap.HashCellIndex;
cellIndex.GetContainsIndexList(cell_list);
var computeInteractionJob = new NeighborDetectionJob_Combined()
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
alignmentWeight = BoidParams_Bootstrap.Param.alignmentWeight,
cohesionWeight = BoidParams_Bootstrap.Param.cohesionWeight,
separationWeight = BoidParams_Bootstrap.Param.separationWeight,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
velocityFromGlobalEntity = GetComponentDataFromEntity<Velocity>(true),
cellIndex = cellIndex,
cellList = cell_list,
accelerationFromGlobalEntity = GetComponentDataFromEntity<Acceleration>(),
};
Dependency = computeInteractionJob.Schedule(cell_list.Length,
CellIndex_Bootstrap.UpdateBatchSize(cell_list.Length),
Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
メモリアクセス改善案のひとつとして、DynamicBufferを使わず結果の格納にfloat3しか必要としないパターンとしてネイバーリストの構築を行わずその場で相互作用を計算するパターンを試しました。
が、Cell-NeighborListと比べて性能が悪化しました。
原因はネイバーリスト候補に対してTranslationのほかにVelocityが必要になりメモリコントローラの負荷が増大したことや、最内ループでのif分内の処理が増えたことで分岐予測ミスのペナルティが大きくなったことが考えられますが、詳細は私の理解を超えています。
最適化において、実験の重要性を教えてくれる一例です。
ECSのような、個別の小さなデータ型ごとに独立した配列があり、それらを共通のインデックスでアクセスするデータ構造を計算機工学ではStructure of Array (SoA)とよび、オブジェクト指向でイメージしやすいList<T>のようなまとまった要素にデータ型をまとめたものの配列であるArray of Structure (AoS)と区別されます。
インテルの最適化資料によれば、SoAパターンはBurstCompilerのようなSIMDの恩恵を受けやすい反面、データ要素ごとに別の配列を扱うためメモリーストリーム参照が増え、"プリフェッチやアドレス生成計算が追加されるだけでなく、ページアクセス効率にも大きく影響"するそうです。
Unity ECSは実際にはchunkごとに分割されているので正しくはハイブリッドSoA(またはAoSoA)であり、普通の使い方でECSを利用する限りたいていの状況においては注意深く設計されたその恩恵に浴することができます。
あと一歩の最適化が必要になったとき、このあたりの知識が頭の片隅にあればUnityに限らない知見を探す一助となるでしょう。
▽ Combined-Cell-Cell
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_Combined_CC : SystemBase
{
private NativeList<PosIndex> cell_list;
protected override void OnCreate()
{
base.OnCreate();
RequireForUpdate(
GetEntityQuery(ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<Acceleration>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_CellIndex_Combined_CC>()));
cell_list = new NativeList<PosIndex>(Allocator.Persistent);
}
protected override void OnDestroy()
{
base.OnDestroy();
cell_list.Dispose();
}
[BurstCompile]
private struct NeighborDetectionJob_Combined : IJobParallelFor
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly] public float alignmentWeight;
[ReadOnly] public float cohesionWeight;
[ReadOnly] public float separationWeight;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public ComponentDataFromEntity<Velocity> velocityFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
[ReadOnly]
public NativeArray<PosIndex> cellList;
[NativeDisableContainerSafetyRestriction]
public ComponentDataFromEntity<Acceleration> accelerationFromGlobalEntity;
private struct TmpForceValue
{
public float3 Alignment, Cohesion, Separation;
public int Count;
public void Clear()
{
Alignment = 0f;
Cohesion = 0f;
Separation = 0f;
Count = 0;
}
public float3 GetAccel(Translation pos0, Velocity vel0,
float alignmentWeight,
float cohesionWeight,
float separationWeight)
{
if (Count <= 0) return float3.zero;
float count_inv = 1f / Count;
return (Alignment * count_inv - vel0.Value) * alignmentWeight
+ (Cohesion * count_inv - pos0.Value) * cohesionWeight
+ (Separation * count_inv) * separationWeight;
}
}
public void Execute(int i_job)
{
var index = cellList[i_job];
var entitiesInCell = new NativeList<Entity>(64, Allocator.Temp);
cellIndex.GetValuesInCell(index, entitiesInCell);
if(entitiesInCell.Length <= 0)
{
entitiesInCell.Dispose();
return;
}
var searchIndexList = new NativeList<PosIndex>(64, Allocator.Temp);
var entitiesForSearch = new NativeList<Entity>(64, Allocator.Temp);
var positionsForSearch = new NativeList<Translation>(64, Allocator.Temp);
var velocitiesForSearch = new NativeList<Velocity>(64, Allocator.Temp);
//--- gather data in cell
var positionsInCell = ComponentDataUtility.GatherComponentData(positionFromGlobalEntity, entitiesInCell, Allocator.Temp);
var velocitiesInCell = ComponentDataUtility.GatherComponentData(velocityFromGlobalEntity, entitiesInCell, Allocator.Temp);
var tmpForceInCell = new NativeArray<TmpForceValue>(entitiesInCell.Length, Allocator.Temp);
//--- search neighbors by cell to cell
cellIndex.GetSearchIndexList(index, distThresh, Boundary.Open, searchIndexList);
for (int i_cell = 0; i_cell < searchIndexList.Length; i_cell++)
{
entitiesForSearch.Clear();
cellIndex.GetValuesInCell(searchIndexList[i_cell], entitiesForSearch);
if (entitiesForSearch.Length <= 0) continue;
//--- gather data for search target cell
positionsForSearch.ResizeUninitialized(entitiesForSearch.Length);
velocitiesForSearch.ResizeUninitialized(entitiesForSearch.Length);
for (int i_entity=0; i_entity < entitiesForSearch.Length; i_entity++)
{
var entity = entitiesForSearch[i_entity];
positionsForSearch[i_entity] = positionFromGlobalEntity[entity];
velocitiesForSearch[i_entity] = velocityFromGlobalEntity[entity];
}
//--- compute interaction with neighbors
for (int i_entity = 0; i_entity < entitiesInCell.Length; i_entity++)
{
var force_tmp = tmpForceInCell[i_entity];
ComputeInteraction(entitiesInCell[i_entity],
positionsInCell[i_entity].Value,
math.normalize(velocitiesInCell[i_entity].Value),
distThresh,
prodThresh,
entitiesForSearch,
positionsForSearch,
velocitiesForSearch,
ref force_tmp);
tmpForceInCell[i_entity] = force_tmp;
}
}
//--- writeback buffered acceleration
for (int i=0; i<entitiesInCell.Length; i++)
{
var entity = entitiesInCell[i];
var acc = accelerationFromGlobalEntity[entity].Value;
acc += tmpForceInCell[i].GetAccel(positionsInCell[i], velocitiesInCell[i],
alignmentWeight, cohesionWeight, separationWeight);
accelerationFromGlobalEntity[entity] = new Acceleration { Value = acc };
}
searchIndexList.Dispose();
entitiesInCell.Dispose();
entitiesForSearch.Dispose();
positionsForSearch.Dispose();
velocitiesForSearch.Dispose();
positionsInCell.Dispose();
velocitiesInCell.Dispose();
tmpForceInCell.Dispose();
}
static void ComputeInteraction(Entity entity, float3 pos0, float3 fwd0,
float distThresh, float prodThresh,
NativeArray<Entity> neighborsFromCell,
NativeArray<Translation> positionsForSearch,
NativeArray<Velocity> velocitiesForSearch,
ref TmpForceValue tmp_value)
{
float r2_search = distThresh * distThresh;
for (int i = 0; i < neighborsFromCell.Length; i++)
{
var neighbor = neighborsFromCell[i];
if (entity == neighbor) continue;
float3 pos1 = positionsForSearch[i].Value;
var to = pos1 - pos0;
var dist2 = math.lengthsq(to);
if (dist2 < r2_search)
{
var dir = math.normalize(to);
var prod = math.dot(dir, fwd0);
if (prod > prodThresh)
{
//--- alignment
tmp_value.Alignment += velocitiesForSearch[i].Value;
//--- cohesion
tmp_value.Cohesion += positionsForSearch[i].Value;
//--- separation
tmp_value.Separation += (-dir);
//--- count
tmp_value.Count++;
}
}
}
}
}
protected override void OnUpdate()
{
//--- search neighbors
var cellIndex = CellIndex_Bootstrap.HashCellIndex;
cellIndex.GetContainsIndexList(cell_list);
var computeInteractionJob = new NeighborDetectionJob_Combined()
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
alignmentWeight = BoidParams_Bootstrap.Param.alignmentWeight,
cohesionWeight = BoidParams_Bootstrap.Param.cohesionWeight,
separationWeight = BoidParams_Bootstrap.Param.separationWeight,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
velocityFromGlobalEntity = GetComponentDataFromEntity<Velocity>(true),
cellIndex = cellIndex,
cellList = cell_list,
accelerationFromGlobalEntity = GetComponentDataFromEntity<Acceleration>(),
};
Dependency = computeInteractionJob.Schedule(cell_list.Length,
CellIndex_Bootstrap.UpdateBatchSize(cell_list.Length),
Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
Combined-Cell-NeighborListのループをCell-Cellのパターンに変更したものです。
相変わらず性能はさほどではありませんが、P-coreの実コア数を超えたところでCombined-Cell-NeighborListがほとんど性能が上がらなくなったのに対し、Combined-Cell-CellはそれなりにThread数の恩恵を受けることができています。
この挙動の差もネイバーリスト候補にVelocityの要求が増えたことによるメモリコントローラの負荷増大を示唆しています。
▽ MergedCell-NeighborList
ソースコードを表示（折りたたみ）
[UpdateInGroup(typeof(NeighborDetectionSystemGroup))]
public partial class NeighborDetectionSystem_CellIndex_MergedCell_NeighborList : SystemBase
{
private NativeList<MergedPosIndex> cell_list;
protected override void OnCreate()
{
base.OnCreate();
RequireForUpdate(
GetEntityQuery(ComponentType.ReadOnly<BoidType>(),
ComponentType.ReadOnly<Translation>(),
ComponentType.ReadOnly<Velocity>(),
ComponentType.ReadWrite<NeighborsEntityBuffer>(),
ComponentType.ReadOnly<Tag_ComputeNeighbors_CellIndex_MergedCell_NL>()));
cell_list = new NativeList<MergedPosIndex>(Allocator.Persistent);
}
protected override void OnDestroy()
{
base.OnDestroy();
cell_list.Dispose();
}
[BurstCompile]
private struct NeighborDetectionJob_Cell_NeighborList : IJobParallelFor
{
[ReadOnly] public float prodThresh;
[ReadOnly] public float distThresh;
[ReadOnly]
public ComponentDataFromEntity<Translation> positionFromGlobalEntity;
[ReadOnly]
public ComponentDataFromEntity<Velocity> velocityFromGlobalEntity;
[ReadOnly]
public HashCellIndex<Entity> cellIndex;
[ReadOnly]
public NativeArray<MergedPosIndex> cellList;
[NativeDisableContainerSafetyRestriction]
public BufferFromEntity<NeighborsEntityBuffer> neighborsFromGlobalEntity;
public void Execute() { for (int i = 0; i < cellList.Length; i++) Execute(i); }
public void Execute(int i_job)
{
var merged_cell_index = cellList[i_job];
//--- gather data
var entitiesForMergedSearch = cellIndex.GetMergedNeighborList(merged_cell_index,
distThresh,
Boundary.Open,
64, Allocator.Temp);
var positionsForMergedSearch = MergedCellUtility.GatherComponentData(positionFromGlobalEntity,
entitiesForMergedSearch,
Allocator.Temp);
var entitiesInMergedCell = entitiesForMergedSearch.ExtractMergedCell(Allocator.Temp);
var velocitiesInMergedCell = MergedCellUtility.GatherComponentData(velocityFromGlobalEntity,
entitiesInMergedCell,
Allocator.Temp);
//--- cell iteration
for(int i_cell = 0; i_cell < entitiesInMergedCell.Length; i_cell++)
{
var entitiesInCell = entitiesInMergedCell.GetCell(i_cell);
var positionsInCell = positionsForMergedSearch.GetCell(i_cell);
var velocitiesInCell = velocitiesInMergedCell.GetCell(i_cell);
var entitiesForSearch = entitiesForMergedSearch.GetNeighbors(i_cell);
var positionsForSearch = positionsForMergedSearch.GetNeighbors(i_cell);
//--- search neighbors by cell to neighbors from cellIndex
for (int i_entity = 0; i_entity < entitiesInCell.Length; i_entity++)
{
var neighbors = neighborsFromGlobalEntity[entitiesInCell[i_entity]];
neighbors.Clear();
NeighborDetectionFunc.SearchNeighbors(entitiesInCell[i_entity],
positionsInCell[i_entity].Value,
math.normalize(velocitiesInCell[i_entity].Value),
distThresh,
prodThresh,
entitiesForSearch,
positionsForSearch,
neighbors);
}
}
entitiesForMergedSearch.Dispose();
positionsForMergedSearch.Dispose();
entitiesInMergedCell.Dispose();
velocitiesInMergedCell.Dispose();
}
}
protected override void OnUpdate()
{
//--- search neighbors
var cellIndex = CellIndex_Bootstrap.HashCellIndex;
cellIndex.GetContainsMergedCellList(CellIndex_Bootstrap.CellMergeSize, cell_list);
var neighborDetectionJob = new NeighborDetectionJob_Cell_NeighborList()
{
prodThresh = math.cos(math.radians(BoidParams_Bootstrap.Param.neighborSearchAngle)),
distThresh = BoidParams_Bootstrap.Param.neighborSearchRange,
positionFromGlobalEntity = GetComponentDataFromEntity<Translation>(true),
velocityFromGlobalEntity = GetComponentDataFromEntity<Velocity>(true),
cellIndex = cellIndex,
cellList = cell_list,
neighborsFromGlobalEntity = GetBufferFromEntity<NeighborsEntityBuffer>(),
};
Dependency = neighborDetectionJob.Schedule(cell_list.Length,
CellIndex_Bootstrap.UpdateBatchSize(cell_list.Length),
Dependency);
CellIndex_Bootstrap.SetJobHandle(this.GetType().Name, Dependency);
}
}
ほかの実装による性能評価をもとに、キャッシュ効率の最大化を狙いあとから追加したパターンです。
XYZそれぞれにn個のCellをまとめて取り扱います。
下記において最終的に採用したのは DirectCompressed-DirectComponent です。
まず試作として以下の要素をテストしました。
- Naive: まとめたCellそれぞれについてCell-NeighborListのAPIを利用して複数個のCellのネイバーリスト候補を連続で取得する。
- cached:
NativeMultiHashMapもComponentDataFromEntityもKeyまたはIDによる間接参照でランダムアクセスになるはずである。よってバッファの先頭領域をローカルcacheとしてアクセスする範囲のCellをあらかじめ並べ、cacheからネイバーリスト候補の配列を組み立てる。 - Compressed: Cellからみてネイバーリスト候補を隣接するセル3x3x3とすると、隣り合うセル間ではそのうち2x3x3が重複している。これを利用してネイバーリスト候補のバッファ内で重複を排除しつつそれぞれのインデックス範囲をオーバーラップさせることでネイバーリスト候補の構築コストを軽くする。
これらの要素のグラフに示した結果との対応表は下記のとおりです。
| Plan | cached (map) | cached (Component) | Compressed NeighborList |
|---|---|---|---|
| Naive | |||
| Cached-DirectComponent | 〇 | ||
| Cached | 〇 | 〇 | |
| CachedAndCompressed-DirectComponent | 〇 | 〇 | |
| CachedAndCompressed | 〇 | 〇 | 〇 |
まず試作の結果として、mapもComponentDataもユーザー管理のキャッシュを使うパターンは遅くなりました。
これは今回の問題に対しては現代のCPUが備えるキャッシュメモリは十分に大容量で、ユーザーがキャッシュ目的のバッファを作るとメモリコントローラからは違うメモリ領域として扱われ、キャッシュ管理の邪魔にしかならなかったと考えられます。
このような使い方の高速メモリとしてはスクラッチパッドメモリと呼ばれ、キャッシュの進歩とともに廃れた歴史がありますが、思い返してみればキャッシュとスクラッチパッド両方に対応したかつてのXeonPhiではスクラッチパッドメモリとして扱う専用命令が追加されていました。一般的なCPUでキャッシュに変な小細工をしてはいけないようです。
一方でネイバーリストの圧縮については効果がありました。圧縮はどれか一つの軸方向なので、マージサイズ2 (2x2x2) の場合バッファ容量、構築処理どちらも1/3ほど削減でき(圧縮軸方向のアクセスが6->4になる)、サイズが大きいほど効果も高くなります。
あまり巨大なサイズでは性能が低下すると思っていましたが、今回はCellごとのデータが小さいせいかかなり大きな場合(9x9x9=729 cells)でも性能を維持していました。
キャッシュにデータをまとめて保持する、という意味ではCell-NeighborListでCellサイズを大きくしても同様の効果はありますが、こちらはネイバーリスト候補を小さく保てるため計算量を増やさずに済む点で優れています。
これらの結果から、ネイバーリスト候補の圧縮のみを行うパターンとして DirectCompressed-DirectComponent を実装し、性能を確認した後採用しました。
もし不採用となったパターンの実装に興味がございましたら、"feature-MergedNeighborList-build-from-cache" ブランチをご参照ください。
まとめ
最終的に、データをECSで管理しBurstも適用するという条件は共通で、メモリアクセス最適化の結果同じthread数で2.5倍、または12 threadと同等の性能を 2 threadで出せるようになりました。
(Entity-NeighborList -> MergedCell-NeighborList)
Unity ECS自体、汎用的にメモリアクセスを最適化することがもともとの設計コンセプトですが、ユーザーが実装する問題に合わせた最適化を行うことでさらに大きな性能向上が得られます。
MonoBehaviourで同様の最適化を行うことに比べれば、すでにECS化されていればそのハードルは大きく下がるので、皆さんもぜひ試してみてください。
おまけ: AlderLakeのE-coreについて
冒頭の画像は worker threads = 11 (+ main thread(1) でi7-12700の実コア数 12)に設定した時の様子です。
4つのE-coreはタスクマネージャーの右下の4つですが、おおよそ論理コアの優先度としては
P-core > E-core(1つ残しておく) > HyperThread P-core > 最後の E-core
のようにしてゲーム以外からの割り込みを最後のE-coreで受け付けられるようにしているように見えます。
結局のところコア数どうこうよりもメモリチューニングがきちんとできているかどうかの方がはるかに効くので、
P-core, E-core 気にせずJobはじゃんじゃん投げましょう。