AoS和SoA

在现代计算机体系结构中，CPU 的处理速度远超内存访问速度。为了弥补这种差距，CPU 引入了多级缓存（Cache）。当 CPU 需要数据时，它会首先在缓存中查找。如果数据在缓存中（Cache Hit），则访问速度极快；如果不在（Cache Miss），则需要从主内存中加载，这会带来巨大的性能开销。因此，缓存友好设计（Cache-Friendly Design）在高性能计算，尤其是游戏物理引擎中，变得至关重要。

本文将探讨如何通过优化数据结构和内存布局，来提高物理引擎的缓存命中率，从而显著提升性能。

为什么缓存友好设计很重要？

物理引擎通常需要处理大量的物理对象（刚体、碰撞体、约束等），并在每个时间步对它们进行复杂的计算。这些计算往往涉及频繁的数据访问和修改。如果数据在内存中是分散的，或者访问模式不连续，就会导致大量的缓存未命中，使得 CPU 花费大量时间等待数据从主内存加载，而不是执行计算。这被称为内存墙（Memory Wall）问题。

通过缓存友好设计，我们可以：

减少缓存未命中：将相关数据存储在内存的连续区域，使得 CPU 在一次缓存行加载中获取更多所需数据。
提高数据局部性：利用时间局部性（最近访问的数据很可能再次访问）和空间局部性（访问一个数据后，其附近的数据很可能被访问）。
充分利用CPU算力：减少 CPU 等待数据的时间，让其能够更专注于计算。

数组的组织形式

AoS和SoA的两种数据组织形式，对缓存性能有显著影响。

Array of Structures（AoS）

将一个对象的多个属性打包在一个结构体中，然后将这些结构体存储在一个数组中。例如，

struct RigidBody 
{ 
    Vector3 position; 
    Quaternion orientation; 
    Vector3 linearVelocity; 
    ... 
}; 

RigidBody bodies[N];

每个 RigidBody 结构体在内存中是连续的，但不同 RigidBody 实例的相同属性（例如所有刚体的 position）在内存中是分散的。这种做法符合直观的面向对象编程思想，易于理解和使用。当访问一个对象时，其所有属性都能一次性加载到缓存中。最大的问题是：缓存效率低。如果某个操作只需要访问对象的部分属性（例如，只更新所有刚体的 position），那么每次加载一个 RigidBody 结构体时，会将不需要的属性也加载到缓存中，浪费缓存空间和带宽。

Structure of Arrays (SoA)

将所有对象的相同属性存储在一个数组中。例如，

Vector3 positions[N]; 
Quaternion orientations[N]; 
Vector3 linearVelocities[N]; 
...;

所有刚体的 position 属性存储在连续的内存区域，所有刚体的 orientation 属性存储在另一个连续的内存区域，以此类推。这样做，缓存效率高。当一个操作只需要访问特定属性时（例如，遍历所有刚体并更新 position），CPU 可以连续地访问这些数据，大大提高缓存命中率。SoA 布局非常适合使用 SIMD（Single Instruction, Multiple Data）指令集进行并行处理，因为数据是连续且同构的。缺点是：访问一个对象的多个属性时，需要从不同的数组中获取，可能不如 AoS 直观。访问一个对象时，其所有属性可能不在同一个缓存行中。

AoS和SoA使用方式

在实际的物理引擎中，通常会根据具体操作的需求来选择 AoS 或 SoA，甚至采用两者的混合模式：

SoA 适用于数据并行操作：例如，在积分阶段，需要遍历所有刚体并更新其位置和速度。此时，将 positions、linearVelocities 等属性存储为独立的数组会非常高效。
AoS 适用于单个对象操作：例如，当处理单个刚体的碰撞或关节时，需要访问其所有属性。此时，将所有属性打包在一个结构体中可能更方便。
混合模式：可以将相关性强的属性组合成小的 AoS 结构，然后将这些小结构存储为 SoA 数组。例如，

struct Transform 
{ 
    Vector3 position; 
    Quaternion orientation; 
}; 

Transform transforms[N];

和

struct Velocity 
{ 
    Vector3 linear; 
    Vector3 angular; 
}; 

Velocity velocities[N];