32x32x32 units octree, that supports 15-bit data units

Question

The idea is to have an octree that stores a 32x32x32 region of 15 bit values more efficiently than a 32x32x32 array, because if all 8 leaf nodes of a given branch are the same, the branch does not need to be allocated and can just be stored as a single value instead of 8+. This recursively means that if all values are the same in the octree, only one object needs to be stored. Each node is a 16 bit object, where the MSB determines if the remaining 15 bits are an pointer (relative to the start of the octree) to a set of 8 subnodes, or a value.

The provided code is a basic implementation of this idea, but does not include more advanced features such as detecting and merging branches whose values are all identical, or multiple parents referencing a single child set if they are the same (i.e. an octree DAG). The Set function resizes the octree via realloc when more space is needed, to the smallest power of 2 large enough to contain all the nodes.

One issue is then a full octree would have 65536 allocated objects but only 37448 will ever be needed at any point (excluding the root node0). A recommendation for a better reallocation scheme, along with general advice for improvement, would be heavily appreciated <3.

A valid all-0 octree could be initialized as follows:

Octree *o0 = memset(malloc(sizeof(Octree)), 0, sizeof(Octree));

The code:

typedef union Node8 {
    uint64_t y[2], c[2];
    uint32_t z[2][2], b[4];
    uint16_t x[2][2][2], a[8];
} Node8;
typedef struct Octree {
    uint64_t *data; // data* fields are reserved for future use
    uint16_t datasize, nodesize;
    uint8_t dataalloc, nodealloc;
    uint16_t node0; // root node
    Node8 node[]; // node[-1] == node0
} Octree;
uint16_t *Get(Octree *const o, const uint8_t x, const uint8_t z, const uint8_t y, uint_fast8_t *const p) {
    uint16_t *n = &o->node0;
    uint_fast8_t i = 4;
    while (*n&0x8000 && (n = &o->node[*n&0x7FFF].x[y>>i&1][z>>i&1][x>>i&1], i))
        --i;
    if (p)
        *p = i;
    return n;
}
Octree *Set(Octree *o, const uint8_t x, const uint8_t z, const uint8_t y, const uint16_t v) {
    uint_fast8_t i;
    uint16_t *n = Get(o, x, z, y, &i);
    if (i) {
        const uint16_t p = *n;
        const unsigned size = o->nodesize+i;
        if (size >= 1U<<o->nodealloc) {
            const ptrdiff_t off = n-(uint16_t *)o->node;
            n = (uint16_t *)(o = realloc(o, sizeof(Octree)+(sizeof(Node8)<<(o->nodealloc = 32-__builtin_clz(size)))))->node+off;
        }
        do {
            *n = o->nodesize|0x8000;
            Node8 *const s = &o->node[o->nodesize++];
            n = &s->x[y>>i&1][z>>i&1][x>>i&1];
            s->a[1] = s->a[0] = p; // copy 8 objects in 3 steps instead of 8
            s->b[1] = s->b[0];
            s->c[1] = s->c[0];
        } while (i--);
    }
    *n = v;
    return o;
}
void Iter(const Octree *const o) {
    const uint16_t *node[6] = {&o->node0};
    int_fast8_t index[6] = {0};
    for (uint_fast8_t i = 0;;) {
        const int_fast8_t j = index[i]--;
        if (j == -1) {
            if (i--)
                continue;
            break;
        }
        const uint16_t n = node[i][j];
        if (n&0x8000 && i < 5) {
            node[++i] = o->node[n&0x7FFF].a;
            index[i] = 7;
            continue;
        }
        printf("%d\n", n);
    }
}

Answer 1

Make your code more readable

Your code is written in a very compact style, making it hard for someone not familiar with it to understand it. Avoid multiple statements per line, avoid assignments inside expressions, and don't hesitate to create helper functions even for small amounts of code if it helps readability. Consider:

static bool entry_is_pointer(uint16_t entry) {
    return entry & 0x8000;
}

static Node8 *entry_to_node(Octree *o, uint16_t entry) {
    return &o->node[entry & 0x7fff];
}

static uint16_t *descend(Node8 *node, uint8_t x, uint8_t z, uint8_t y, fast_uint8_t level) {
    return &node.x[(x >> level) & 1][(y >> level) & 1][(z >> level) & 1];
}

uint16_t *Get(Octree *octree, uint8_t x, uint8_t z, uint8_t y, uint_fast8_t *levelptr) {
    uint16_t *entry = &octree->node0;
    uint_fast8_t level = 5;

    while (entry_is_pointer(*entry)) {
        --level;
        Node8 *node = entry_to_node(octree, *entry);
        entry = descend(node, x, y, z, level);
    }

    if (levelptr)
        *levelptr = level;

    return entry;
}

The binary generated by the compiler should still be exactly the same.

Use const in the right place

I see you made the parameters const, but not in the most useful way. Ideally, you pass a const Octree* to Get(), and get a const uint16_t* back. This will allow the compiler to better optimize code for callers that query the tree but don't want to modify it. Of course, you are using Get() inside Set(), so that is a bit problematic; either you have to duplicate the code to get to an entry but return a non-const pointer, or you have to cast the constness away inside Set(). The latter is safe though, because you already have a non-const pointer to an Octree there.

Missing error checking

Calls to malloc() and realloc() can fail and return NULL. You should check for that. If you really cannot do anything about it, call abort() or another function to terminate the program.

Also note that if realloc() fails, the original allocation is still valid, so o = realloc(o, …) will then leak memory.

Optimizing for space or bandwidth efficiency?

Disregarding your allocation strategy for now, consider that most CPUs nowadays read 64-byte cache lines at a time. This means 32 16-bit entries in one go, whereas a Node8 is only 8 16-bit entries, or 16 bytes. That means that if while descending the octree the nodes are not consecutive in memory (likely), you are wasting 75% of the memory bandwidth.

Instead of using an octree, you could use a different tree structure, where first you store 32 planes indexed by x, then 32 lines indexed by y, and then 32 values indexed by z. So you only need to fetch at most 3 cache lines to get to the desired value. You still get to make "nodes" in this tree have the same value everywhere, but they are then either a whole plane or a whole line. Depending on what you store in the tree, that might be more or less efficient when it comes to the size of the resulting tree.

Check if v is the same as already present

In Set(), you never check if v has the same value as is already present at the given location. If so, you can return without having to allocate new nodes.

Allocation strategy

One issue is then a full octree would have 65536 allocated objects but only 37448 will ever be needed at any point (excluding the root node0).

Your code is more complex than necessary. If you are in Set() and i != 0, then you know that you need to allocate exactly i new nodes. Of course, calling realloc() every time you just need to add a few is not efficient, so indeed you can add more in one go. Doubling the size every time gives \$O(1)\$ amortized cost for allocation. But since you know you don't need more than 37448 nodes, just cap it to that number?

Also, just keep a simple counter of how many nodes that are used and how many nodes you have allocated. That avoids all the bit shifting and the non-standard _builtin_clz().