八叉树码性能

Question

我在我的程序中使用了一个简单的八叉树，并且想知道我的实现是否会更快。它是这个程序的一部分。

十月号。H：

#ifndef OCTREE_H
#define OCTREE_H

#include "Rendera.H"

class Octree
{
public:
  struct node_t
  {
    float value;
    struct node_t *child[8];
  };

  Octree();
  virtual ~Octree();

  void clear(struct node_t *);
  void write(const int &, const int &, const int &, const float &);
  void writePath(const int &, const int &, const int &, const float &);
  float read(const int &, const int &, const int &);

  struct node_t *root;
};

#endif

Octree.cxx：

#include "Octree.H"

Octree::Octree()
{
  root = new node_t;
  root->value = 0;

  for(int i = 0; i < 8; i++)
    root->child[i] = 0;
}

Octree::~Octree()
{
  clear(root);
}

void Octree::clear(struct node_t *node)
{
  for(int i = 0; i < 8; i++)
    if(node->child[i])
      clear(node->child[i]);

  delete node;
}

void Octree::write(const int &r, const int &g, const int &b,
                   const float &value)
{
  struct node_t *node = root;

  for(int i = 7; i >= 0; i--)
  {
    const int index = ((r >> i) & 1) << 0 |
                      ((g >> i) & 1) << 1 |
                      ((b >> i) & 1) << 2;

    if(!node->child[index])
    {
      node->child[index] = new node_t;
      node = node->child[index];
      node->value = 0;

      for(int j = 0; j < 8; j++)
        node->child[j] = 0;
    }
    else
    {
      node = node->child[index];
    }
  }

  node->value = value;
}

// Sets entire path to value.
// This allows the octree to be used in a different way.
// (Needed for palette lookup.)
void Octree::writePath(const int &r, const int &g, const int &b,
                       const float &value)
{
  struct node_t *node = root;

  for(int i = 7; i >= 0; i--)
  {
    const int index = ((r >> i) & 1) << 0 |
                      ((g >> i) & 1) << 1 |
                      ((b >> i) & 1) << 2;

    if(!node->child[index])
    {
      node->child[index] = new node_t;
      node = node->child[index];
      node->value = value;

      for(int j = 0; j < 8; j++)
        node->child[j] = 0;
    }
    else
    {
      node = node->child[index];
    }
  }
}

float Octree::read(const int &r, const int &g, const int &b)
{
  struct node_t *node = root;

  for(int i = 7; i >= 0; i--)
  {
    const int index = ((r >> i) & 1) << 0 |
                      ((g >> i) & 1) << 1 |
                      ((b >> i) & 1) << 2;

    if(node->child[index])
      node = node->child[index];
    else
      break;
  }

  return node->value;
}

Answer 1

性能

(没有任何分析数据，我在这里盲目猜测)

您有一个链接的数据结构(树)，遍历树时缓存局部性很差，这可能会影响您的性能。因为在最坏的情况下，每个节点都可能是缓存丢失。但是，请首先测量这一点，如果您看到大部分时间花在获取下一个节点或接近一行代码时，就会出现缓存问题。

要提高缓存性能，可以做的一件事是将树编码成线性序列(std::vector首选)。然后测量看看它是否更快。

至于编码，我们将树的级别称为k，根具有k=0。这意味着k级别最多有8^k节点。如果我们通过网格坐标(x,y, z)来引用一个级别中的每个节点，那么节点n(k,x,y,z) (在k级别和位置(x,y,z))上将有它的子节点：

• n(k+1, 2*x, 2*y, 2*z)
• ..。( +1到x，y，z的所有组合)
• n(k+1, 2*x + 1, 2*y + 1, 2*z + 1)

我们可以将所有节点排序为线性随机访问序列v (std::vector)，如下所示：

level_base = ipow(8,k) - 1;
level_width = ipow(2,k);
grid_index = x + level_width * y + level_width*level_width*z;
n(k, x, y) = v[level_base + grid_index];

注意，k级别上的网格宽度是2^k (例如: 1、2、4、8)。这里，ipow是一个优化的整数幂函数。如果ipow证明是一个瓶颈，您可以使用LUT的功率为8和2。

福利

• 这样做的好处是，广度优先遍历/搜索将成为一个线性访问模式，您的CPU预取器将喜欢您。这太快了。
• 如果您事先知道需要(k,x,y,z)的哪个节点，您可以直接得到它。
• 你可以很容易地找到所有的邻居。
• 给定您的(r,g,b)三重奏，您可能只需直接计算目标节点的索引，写入该值，您就完成了。不对右节点进行迭代。
• 更少的内存碎片。
• 对于密集的树，这实际上占用较少的内存，因为您没有堆、簿记、开销等。
• 您不需要child[]数组使您的数据结构更小，而且更多的数据可以适合每一行缓存。

缺点

• std::vector是密集的，如果您的树非常稀疏，您可能最终会分配比您需要的更多的节点。另一方面，如果您有内存，它可能是可以接受的。
• 这是一个更复杂的索引，如果不采取适当的谨慎措施，可能会导致错误或更复杂的代码。
• 如果需要区分空节点和非空节点(而不是value == 0)，则需要引入has_data标志。但是这些节点仍然比拥有子数组要小。
• 对一种错误的抵抗力不强。在链接树类型结构中，如果您设法在节点结构之外写入，那么您将写入堆上或堆簿记中的金丝雀值。在调试模式下，RT应该让您知道您有问题。使用这种方法，您将悄悄地破坏附近的节点。不一定是有可能的，但需要注意的东西。

Answer 2

• 我所知道的性能没有一个处理器能够通过变量进行转换，这意味着>> i将被实现为一个循环(而且我不会依赖于编译器能够注意到一个模式)。我会将循环重构为: for (掩码= 0x01 << 8；掩码!= 0；掩码>>= 1) { const索引= ((r &掩码)？1: 0) x ((g和掩码)？2: 0) x ((b和掩码)？4: 0)；.}
• 神奇的数字--我理解在你的应用程序中，所有索引只有8个重要位(我想我知道原因了)。不过，可以通过Octree构造函数或作为模板参数定义位宽度是合理的。
• 全局变量--我希望在实际代码中，struct node_t *root;是Octree类的属性，而不是全局属性。
• “欺骗”读取一个没有被写入的索引，从一个完全无关的索引返回值。它可能可以处理颜色，但在一般情况下，这将是令人惊讶的。
• 多索引直接访问容器通常将read和write方法实现为operator()，ref和const变体将被使用，例如: octree(r，g，b) = value；value = octree(r，g，b)；不是严格必要的，但可能会增强可读性。

Answer 3

为什么要使用const int&？这是一个间接的，甚至可能需要更多的带宽。为什么不直接使用int呢？