如何存储和推送模拟状态,同时最低限度地影响每秒更新？

Question

我的应用程序由两个线程组成:

1. GUI线程(使用Qt)
2. 模拟线程

我使用两个线程的原因是保持GUI响应,同时让Sim线程尽可能快地旋转.

在我的GUI线程中,我在SIM卡中以30-60的FPS渲染实体; 但是,我希望我的SIM卡能够"紧缩" - 可以这么说 - 并最终排队游戏状态(想想流媒体视频,你有一个缓冲区).

现在,对于我渲染的每个帧,我需要相应的模拟"状态".所以我的sim线程看起来像:

while(1) {
    simulation.update();
    SimState* s = new SimState;
    simulation.getAgents( s->agents ); // store agents
    // store other things to SimState here..
    stateStore.enqueue(s); // stateStore is a QQueue<SimState*>
    if( /* some threshold reached */ )
        // push stateStore
}

SimState 好像:

struct SimState {
    std::vector<Agent> agents;
    //other stuff here
};

而Simulation :: getAgents看起来像:

void Simulation::getAgents(std::vector<Agent> &a) const
{
    // mAgents is a std::vector<Agent>
    std::vector<Agent> a_tmp(mAgents);
    a.swap(a_tmp);
}

这Agent本身就是一些复杂的课程.成员是一堆ints和floats两个std::vector<float>.

使用此当前设置,sim不能紧缩,必须比GUI线程绘制更快.我已经验证了当前的瓶颈simulation.getAgents( s->agents ),因为即使我省略了推送,每秒更新速度也很慢.如果我注释掉那条线,我会看到更新/秒的几个数量级的改进.

那么,我应该使用哪种容器来存储模拟的状态？我知道有一大堆复制正在进行,但其中一些是不可避免的.我应该存储Agent*在向量而不是Agent？

注意:实际上模拟不是循环,而是使用Qt,QMetaObject::invokeMethod(this, "doSimUpdate", Qt::QueuedConnection);所以我可以使用信号/槽来在线程之间进行通信; 但是,我已经验证了使用的更简单的版本while(1){},问题仍然存在.

Answer 1

尝试重新使用您的SimState对象(使用某种池机制),而不是每次都分配它们.在几个模拟循环之后,重新使用的SimState对象将具有已经增长到所需大小的向量,从而避免重新分配并节省时间.

实现池的一种简单方法是首先将一堆预先分配的SimState对象推送到std::stack<SimState*>.请注意,堆栈比队列更可取,因为您希望在缓存内存中更可能是"热"的SimState对象(最近使用的SimState对象将位于堆栈的顶部).您的模拟队列将SimState对象从堆栈中弹出,并使用计算出的SimState填充它们.然后将这些计算出的SimState对象推送到生产者/消费者队列中以提供GUI线程.在由GUI线程呈现之后,它们被推回到SimState堆栈(即"池").在完成所有这些操作时,尽量避免不必要地复制SimState对象.在"管道"的每个阶段直接使用SimState对象.

当然,您必须在SimState堆栈和队列中使用正确的同步机制以避免竞争条件.Qt可能已经有线程安全的堆栈/队列.如果存在大量争用(英特尔线程构建模块提供此类无锁队列),则无锁堆栈/队列可能会加快速度.看到计算一个SimState大约需要1/50秒,我怀疑争用会成为一个问题.

如果您的SimState池耗尽,那么这意味着您的模拟线程太"遥遥领先"并且可以等待一些SimState对象返回到池中.模拟线程应该阻塞(使用条件变量),直到SimState对象在池中再次可用.SimState池的大小对应于可以缓冲多少SimState(例如,一个约50个对象的池为您提供最多约1秒的紧缩时间).

您还可以尝试运行并行仿真线程以利用多核处理器.该线程池模式可能是有用的在这里.但是,必须注意计算的SimStates以正确的顺序排列.按时间戳排序的线程安全优先级队列可能在此处起作用.

这是我建议的管道架构的简单图表:

(右键单击并选择视图图像以获得更清晰的视图.)

(注意:池和队列通过指针而不是值来保存SimState !)

希望这可以帮助.

如果您打算重新使用SimState对象,那么您的Simulation::getAgents方法效率低下.这是因为vector<Agent>& a参数可能已经具有足够的容量来保存代理列表.

你现在这样做的方式会丢掉这个已分配的向量并从头开始创建一个新的向量.

IMO,你的getAgents应该是:

void Simulation::getAgents(std::vector<Agent> &a) const
{
    a = mAgents;
}

是的,您失去了异常安全性,但您可能会获得性能(特别是使用可重用的SimState方法).

另一个想法:您可以尝试通过使用c样式数组(或boost::array)和"count"变量代替std::vectorAgent的浮点列表成员来使您的Agent对象固定大小.只需将固定大小的阵列设置得足够大,以适应模拟中的任何情况.是的,你会浪费空间,但你可能会获得很大的速度.

然后,您可以使用固定大小的对象分配器(例如boost::pool)对您的代理进行池化,并通过指针(或shared_ptr)传递它们.这将消除大量的堆分配和复制.

您可以单独使用此想法,也可以与上述想法结合使用.这个想法似乎比上面的管道更容易实现,所以你可能想先尝试一下.

还有另外一个想法:您可以将模拟分解为几个阶段,并在其自己的线程中执行每个阶段,而不是运行模拟循环的线程池.生产者/消费者队列用于在阶段之间交换SimState对象.为了使其有效,不同阶段需要具有大致相似的CPU工作负载(否则,一个阶段将成为瓶颈).这是利用并行性的另一种方式.