# Octree code performance

I'm using a simple octree in my program and wanted to know if my implementation could be faster. It is part of this program.

Octree.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;
}

• Make it faster... have you measured it? – Emily L. Jun 2 '15 at 14:31

Well, you got some tips about performance, so I would like to also point out a few general code improvements you can apply:

• node_t: Names ending with the _t suffix are actually reserved by the POSIX standard. See this (right at the end). You should follow the fairly common PascalCase convention for type names. Node would be better.

• Public virtual destructor: Are you extending Octree somewhere? Only provide a public virtual destructor if you intend to do so. If you are not sure, I suggest following the YAGNI principle and making it non-virtual. Programmers are usually pretty bad at predicting future needs.

• Unnamed parameters on function prototypes: Please name the function parameters in the prototypes. This will make your functions self-documented.

• Public root: Doesn't seem like a good idea to leave the root node of the tree as a public field. Makes it very easy for someone to accidentally break an instance of the class by changing the root pointer.

• Nodes (node_t) should have a constructor: You should provide one or more constructors for your node type so you can more easily declare and initialize instances. E.g.: node_t * node = new node_t(42.1f);.

• You are using 0 to assign a null pointer. C++11 now has nullptr. If you have access to it, use nullptr instead. It avoids questionable implicit conversions and is more idiomatic than a literal zero.

• Logic inside loops can be simplified: When checking a condition inside a loop, you can make it simpler and more compact by using a continue or break to avoid an if-else chain. Example:

    for(int i = 7; i >= 0; i--)
{
const int index = ...

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];
}
}


Could be rewritten as:

for(int i = 7; i >= 0; i--)
{
const int index = ...

if(node->child[index])
{
node = node->child[index];
continue;
}

node->child[index] = new node_t;
node = node->child[index];
node->value = value;

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

• The POSIX restrictions are for C and it reserves names ending with _t for types. Since it's not for macros, I think that it is safe to end a type name with _t if it is not in the global namespace. – Morwenn Jun 2 '15 at 9:43
• @Morwenn POSIX restrictions are for code (C or C++) using the POSIX library or its headers. If you are 100% you are not and will never be using the POSIX library you are safe to ignore the guidelines. However POSIX being quite widespread and many people not knowing exactly which headers are POSIX or not, I'd err on the safe side and avoiding the use of _t as a suffix. Even if you're not in the global namespace you can still get name clashes as the POSIX names are in the global namespace, it is C after all. – Emily L. Jun 2 '15 at 14:27
• @EmilyL. But if you're using POSIX names in a custom namespace in C++, there are no name clashes, right? That's just like the for the C standard library: you can define a memcpy function into your own namespace without clashing with the one in <string.h>. I don't think that there would be so many names ending with _t in the Boost libraries if it was a real concern. – Morwenn Jun 2 '15 at 15:01
• @Morwenn, Your are correct, there shouldn't be any name conflicts if they are in different namespaces (unless there's a using namespace somewhere :P). However, another argument I would add against the _t suffix, or any Hungarian Notation-like name annotation, is that they are ultimately silly in a strongly typed language like C++. Better to just pick a name that describes the entity well, instead of encoding type information on it with arbitrary prefixes/suffixes. – glampert Jun 2 '15 at 17:59
• @glampert I agree that in your case, the trailing _t suffix is useless. But sometimes (e.g. size_t) it is added because you still want to name your variables/functions size but there is no name for "a type to represent a size". Using the PascalCase helps to avoid the problem, that's true. – Morwenn Jun 3 '15 at 10:15

## Performance

(Without any profiling data, I'm guessing blindly here)

You have a linked data structure (a tree), traversing the tree has poor cache locality and this is where your performance will likely suffer. Because every node could be a cache miss at worst. But please do measure this first, if you see that most of your time is spent getting the next node or close to a line of code that does, you're having cache issues.

One thing you can do to try to improve your cache performance is to encode your tree into a linear sequence (std::vector preferrably). And then measure to see if it actually is faster.

As for the encoding, we'll refer to a level of the tree as k and the root has k=0. This means that the level k has at most 8^k nodes. If we refer to each node in a level by it's grid coordinate (x,y, z) then the node n(k,x,y,z) (at level k and position (x,y,z)) will have it's child nodes on:

• n(k+1, 2*x, 2*y, 2*z)
• ... (all combinations of +1 to the x,y,z) ...
• n(k+1, 2*x + 1, 2*y + 1, 2*z + 1)

We can order all the nodes into a linear random access sequence v (std::vector) like this:

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];


Note that the width of the grid at level k is 2^k (example: 1, 2, 4, 8). Here ipow is an optimized integer power function. If ipow proves to be a bottle neck, you can use a LUT for the powers of 8 and 2.

### Benefits

• The benefits to doing this is that Breadth First Traversal/Search becomes a linear access pattern which your CPU's pre-fetcher will love you for. This is very fast.
• If you know before hand which node you want (k,x,y,z), you can get it directly.
• You can get all the neighbours easily.
• Given your (r,g,b) triplet, you may be able to just directly compute the index of the destination node, write the value and you're done. No iteration to the right node.
• Less memory fragmentation.
• For dense trees this actually takes less memory as you don't have the heap bookkeeping overhead etc.
• You do not need the child[] array making your data structure smaller and more of them can fit in each cache line.

### Drawbacks

• The std::vector is dense, if your tree is very sparse, you may end up allocating a lot more nodes than you need. On the other hand, if you have the memory it might be acceptable.
• It's a more complex indexing which can result in bugs or more complex code if proper caution isn't taken.
• If you need to distinguish between empty and non-empty nodes (as opposed to having value == 0), you need to introduce a has_data flag. But the nodes are still smaller than having the child array.
• Not as resilient against off-by-one type of bugs. In a linked-tree type structure if you manage to somehow write outside of the node's structure you'll write into the canary values on the heap or in the heap book-keeping. Under debug mode your RT should let you know you have an issue. With this approach you will silently corrupt nearby nodes. Not necessarily likely but something to be aware of.
• What are x, y and z in the above answer? Are they integer offsets into grid cells (e.g. -level_width to +level_width)? Thanks! – Kazade Jan 28 '18 at 9:53
• Performance

No processor I know about is capable of shifting by a variable, meaning that >> i would be implemented as a loop (and I wouldn't rely on compiler being able to notice a pattern). I'd restructure the loop as:

for (mask = 0x01 << 8; mask != 0; mask >>= 1) {
const int index =
((r & mask)? 1: 0) |
((g & mask)? 2: 0) |
...
}

• Magic number

I understand that in your application all indices have only 8 significant bits (and I think I know why). Still, it would be reasonable to have bit width definable either through the Octree constructor or as a template parameter.

• Global variable

I hope that in the actual code struct node_t *root; is a property of the Octree class, not global.

• "Cheating"

Reading an index which has not been written returns value from a quite unrelated index. It might be OK for color processing, but in general case it would be surprising.

• Multi-indexed direct access containers usually implement your read and write methods as operator(), with ref and const ref const variants to be used like:

octree(r, g, b) = value;
value = octree(r, g, b);


Not strictly necessary, but may enhance readability.

• I changed the loops per your suggestion, thank you. (The other things probably don't matter for this, but I can see how they would in a more generalized implementation.) – joe63074 Nov 22 '14 at 15:13
• Intel processors have an instruction SAR r/m, CL in which the register or memory location is shifted right by the count in the CL register, and at least gcc is capable of using that instruction. So no loop is necessarily required. – Edward Nov 22 '14 at 15:45
• Using shifts the disassembly indeed showed SAR/SAL being used, and executed 20% faster in a quick & dirty test. – joe63074 Nov 22 '14 at 18:58
• Just a note about "No processor I know about is capable of shifting by a variable." Actually x86 architecture as a series of shift operations using the cl register for the shift count (since 8088 if my memory serves me correctly) Your code: 5 logicals 3 jumps. His code: 10 logicals. His is probably faster. – Hurricane Jun 2 '15 at 9:18

Why use const int&? It's an indirection and may even take more bandwidth. Why not use int directly ?