C++ 绘制 Mandelbrot 集，性能不佳

Question

我不确定是否可以实现实际的性能提升，或者我的计算机是否只是又旧又慢，但无论如何我都会问。

所以我尝试编写一个程序来使用 cairo 库绘制 Mandelbrot 集。

绘制像素的循环如下所示:

vector<point_t*>::iterator it;
for(unsigned int i = 0; i < iterations; i++){
  it = points->begin();
  //cout << points->size() << endl;
  double r,g,b;
  r = (double)i+1 / (double)iterations;
  g = 0;
  b = 0;
  while(it != points->end()){
    point_t *p = *it;
    p->Z = (p->Z * p->Z) + p->C;
    if(abs(p->Z) > 2.0){
      cairo_set_source_rgba(cr, r, g, b, 1);
      cairo_rectangle (cr, p->x, p->y, 1, 1);
      cairo_fill (cr);
      it = points->erase(it);
    } else {
      it++;
    }
  }
}

想法是给所有刚从集合中逃脱的点上色，然后将它们从列表中删除以避免再次评估它们。

它确实正确地渲染了集合，但似乎渲染花费的时间比需要的时间长得多。

有人能发现循环的任何性能问题吗？还是尽善尽美？

提前致谢:)

解决方案

非常好的答案，谢谢 :) - 我最终得到了一种混合的答案。想到建议的内容，我意识到计算每个点，将它们放入 vector 中然后提取它们是对 CPU 时间和内存的巨大浪费。因此，程序现在只计算每个点的 Z 值，甚至不使用 point_t 或 vector 。它现在运行得更快了!

Answer 1

编辑:如果您不关心“增量”计算，但我认为 kuroi neko 的答案中的建议也是一个非常的好主意，但有一个固定的迭代次数。

1. 你应该使用 vector<point_t>而不是 vector<point_t*> .

   A vector<point_t*>是指向 point_t 的指针列表.每个点都存储在内存中的某个随机位置。如果您遍历这些点，访问内存的模式看起来完全是随机的。你会得到很多缓存未命中。

   对面vector<point_t>使用连续 内存来存储点。因此，下一个点直接存储在当前点之后。这允许有效的缓存。

2. 你不应该调用 erase(it);在你的内部循环中。

   每次调用 erase必须在您删除的元素之后移动所有元素。这具有 O(n) 运行时间。例如，您可以向 point_t 添加标志以表明不应再对其进行处理。在每次迭代后删除所有“非事件”点可能会更快。

3. 使用 cairo_rectangle 绘制单个像素可能不是一个好主意.我建议您创建一个图像并存储每个像素的颜色。然后用一次绘制调用绘制整个图像。

您的代码可能如下所示:

for(unsigned int i = 0; i < iterations; i++){
  double r,g,b;
  r = (double)i+1 / (double)iterations;
  g = 0;
  b = 0;
  for(vector<point_t>::iterator it=points->begin(); it!=points->end(); ++it) {
    point_t& p = *it;
    if(!p.active) {
      continue;
    }
    p.Z = (p.Z * p.Z) + p.C;
    if(abs(p.Z) > 2.0) {
      cairo_set_source_rgba(cr, r, g, b, 1);
      cairo_rectangle (cr, p.x, p.y, 1, 1);
      cairo_fill (cr);
      p.active = false;
    }
  }
  // perhaps remove all points where p.active = false
}

如果不能改point_t ，您可以使用额外的 vector<char>存储点是否变为“非事件”。