C++ 中的粒子池性能优化

Question

我有一个存储粒子指针的粒子池

它有大量粒子

每个粒子都有 IsActive 变量

当根据其活动状态每帧对向量进行分区时，CPU 使用率很高

因此这是对向量进行分区的好方法在工作线程上每隔几秒？

Answer 1

由于活动粒子的顺序并不重要，并且它们不会经常变得活动或不活动，因此您可以使用一种技巧将活动粒子保持在前面：

假设 nActive 是数字的活性粒子。

当非活动粒子变为活动状态时，执行 std::swap(vector[nParticle], vector[nActive]); nActive++; 即使其成为最后一个活动粒子 - 无论该槽中已有什么非活动粒子，都会转到该粒子曾经所在的位置，我们不在乎，因为我们不关心订单。

当活动粒子变为非活动状态时，执行 nActive--; std::swap(vector[nParticle], vector[nActive]); 即使其成为第一个非活动粒子 - 并且无论该插槽中已有什么活动粒子，都会转到粒子曾经是，我们不在乎，因为我们不关心顺序。

您可以通过记住使粒子处于活动或不活动状态很容易（如果我们不关心它是哪一个）来记住这个技巧，因为我们只需从 nActive 中加或减 1。但随后我们不知道我们刚刚改变了哪个粒子。因此，我们将该粒子与我们想要更改的粒子交换，并且我们不关心该粒子去哪里，只要它保持不活动或保持活动（不改变）即可。

像这样：

+-----------+-----------+-----------+-----------+
| Particle0 | Particle1 | Particle2 | Particle3 |
| active    | active    | inactive  | inactive  |
+-----------+-----------+-----------+-----------+
                        ^
                        |
                    nActive==2

使粒子 3 处于活动状态：交换粒子 3 和 2，然后递增 nActive：

+-----------+-----------+-----------+-----------+
| Particle0 | Particle1 | Particle3 | Particle2 |
| active    | active    | active    | inactive  |
+-----------+-----------+-----------+-----------+
                                    ^
                                    |
                                nActive==3

使粒子 0 处于非活动状态：递减 nActive，然后交换粒子 3（在插槽 2 中）和 0。

+-----------+-----------+-----------+-----------+
| Particle3 | Particle1 | Particle0 | Particle2 |
| active    | active    | inactive  | inactive  |
+-----------+-----------+-----------+-----------+
                        ^
                        |
                    nActive==2

现在粒子顺序都打乱了，但您不这样做不在乎这个，对吧？

Answer 2

虽然 user253751 的答案对于优化分区方案来说是绝对正确的，但听起来您将遇到与粒子数量和缓存一致性相关的更大问题。

我猜测所使用的数据结构类似于

struct Particle
{
    vec2 position;
    vec2 velocity;
    float scale;
    float scaleVelocity;
    float lifeRemaining;
    vec4 color;
    // Other attributes
};

std::vector<Particle> particles;

void updateParticles(const float delta)
{
    for(size_t i = 0; i < particles.size(); ++i)
    {
        particles[i].position += particles[i].velocity;
        particles[i].scale += particles[i].scaleVelocity;
        particles[i].lifeRemaining -= delta;
    }
}

这导致每个粒子元素被一个接一个地打包。这在多线程环境中会产生更差的性能，因为同步可能必须在单个缓存行中的核心之间发生（假设您单独处理每个组件而不是块，无论哪种方式能够矢量化仍然会更好）。

位置	速度	比例	速度	寿命	颜色
比例	position_0velocity_0scale_0scaleVelocity_0lifeRemaining_0	​	有	color_0position_1velocity_1scale_1scaleVelocity_1lifeRemaining_1color_1position_2velocity_2scale_2scaleVelocity_2lifeRemaining_2color_2position_3velocity_3scale_3scaleVelocity_3lifeRemaining_3color_3	​
缓存	的	糟糕	剩余	这	​
​	​	​	​	​	​
​	​	​	​	​	​

​一致性并且不利于矢量化。

在这种情况下，您可能可以通过切换到类似于以下内容的面向数据的编程方法来显着提高性能。

struct ParticleContainer
{
    std::vector<vec2> position;
    std::vector<vec2> velocity;
    std::vector<float> scale;
    std::vector<float> lifeRemaining;
    std::vector<vec4> color;
};

ParticleContainer particles;

void updateParticles(const float delta)
{
    for(size_t i = 0; i < particles.size(); ++i)
    {
        particles.position[i] += particles.velocity[i];
    }

    for(size_t i = 0; i < particles.size(); ++i)
    {
        particles.scale[i] += particles.scaleVelocity[i];
    }

    for(size_t i = 0; i < particles.size(); ++i)
    {
        particles.lifeRemaining[i] -= delta;
    }
}

会导致相同的元素打包在一起，从而允许您一次对其中多个元素进行操作

Particle 0	Particle 1	2	Particle
3position_0position_1position_2	Particle	这	位置
_3 速度_0	速度_1 速度	_2 速度	_3
缩放_0	缩放	_1 缩放	_2
缩放	_3缩放速度_0 缩放	速度_1 缩放速度_2	缩放速度_3
lifeRemaining_0	lifeRemaining_1	lifeRemaining_2	lifeRemaining_3
color_0	color_1	color_2	color_3

这种内存布局更有利于矢量化，并且由于缓存一致性可以显着提高性能。它还为您提供了手动矢量化代码的选项，类似于

void updateParticles(const float delta)
{
    // A vec2 of type float requires 64 bits, allowing us to pack 2 into a 128 bit vector.
    for(size_t i = 0; i < particles.size() / 2; i += 2)
    {
        const __m128 positionVector = _mm_loadu_ps(&particles.position[i]);
        const __m128 velocityVector = _mm_loadu_ps(&particles.velocity[i]);
        const __m128 newPosition = _mm_add_ps(positionVector, velocityVector);
        _mm_storeu_ps(&particles.position[i], newPosition);
    }

    // A float requires 32 bits, allowing us to pack 4 into a 128 bit vector.
    for(size_t i = 0; i < particles.size() / 4; i += 4)
    {
        const __m128 scaleVector = _mm_loadu_ps(&particles.scale[i]);
        const __m128 scaleVelocityVector = _mm_loadu_ps(&particles.scaleVelocity[i]);
        const __m128 newScale = _mm_add_ps(positionVector, scaleVelocityVector);
        _mm_storeu_ps(&particles.scale[i], newScale);
    }

    const __m128 deltaVector = _mm_set_ps1(delta);

    // A float requires 32 bits, allowing us to pack 4 into a 128 bit vector.
    for(size_t i = 0; i < particles.size() / 4; i += 4)
    {
        const __m128 lifeRemainingVector = _mm_loadu_ps(&particles.lifeRemaining[i]);
        const __m128 newLifeRemaining = _mm_sub_ps(lifeRemainingVector, deltaVector);
        _mm_storeu_ps(&particles.lifeRemaining[i], newLifeRemaining);
    }
}

此代码显然需要一些健全性检查，例如确保每个数组大小始终是向量大小的倍数。此外，如果您可以确保内存从 16 字节边界开始，您可以使用对齐的加载和存储函数。如果可用，您还可以使用 AVX 和 AVX2 256 位寄存器。

内存访问是现代计算机中最慢的部分，这样做可以确保在给定时间操作尽可能多的数据。这也使得 CPU 更容易急切地加载内存行。您现在还可以在多核环境中使用此功能，性能显着提高，并且不会影响缓存行的使用，这可以通过 CPU 上的多个线程来完成，也可以使用 CUDA、OpenCL 或计算着色器等在 GPGPU 上轻松执行。