How can I make code that is both DRY and fast where intermediate values in a calculation may or may not be needed?

Question

How can I make DRY (lacks repetitive patterns) code that also avoids inefficiencies from using intermediate values in a calculation that might not need to be used?

Here is an example:

In this code, I am using an octree to store a region of 32x32x32 voxels, and I need a function to get and set any given one of the voxels. The get function involves descending the tree until a leaf node is encountered.

The set function involves doing the same, except an array of all previous offsets need to be recorded, so that if a branch is inserted or deleted in the middle of the tree, the indices in parent branches can be updated when the memory is shift to make more space or to fill the gap.

typedef struct Octree {
    Ptr data; // Definition of Ptr and Node8 are not relevant to this question
    uint8_t data_alloc, set_alloc;
    uint16_t data_size, set_size, base;
    Node8 set[];
} Octree;
static uint_fast8_t octree_index(const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint_fast8_t level) {
    return (x>>level&1)|(z>>level&1)<<1|(y>>level&1)<<2;
}
uint16_t octree_get(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) { // Gets the value at a certain position in the octree
    uint_fast16_t set = 0;
    uint_fast8_t level = 5;
    uint16_t node = octree->base;
    while (node&0x8000 && level--)
        node = ((uint16_t *)octree->set)[(set += node&0x7FFF)<<3|octree_index(x, y, z, level)];
    return node;
}
Octree *octree_set(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint16_t new) { // Gets the value at a certain position in the octree
    uint_fast16_t set = 0, stack[5]; // Note the new `stack` variable
    uint_fast8_t level = 5;
    uint16_t node = octree->base;
    while (node&0x8000 && level--)
        node = ((uint16_t *)octree->set)[stack[level] = (set += node&0x7FFF)<<3|octree_index(x, y, z, level)];
        // The only difference in the above line is the `stack[level] = ` before `(set += ...`
    if (node != new) {
        if (level) {
            // Subdivide and insert
        } else {
            // Set and merge if necessary
        }
    }
    return octree;
}

The above code is repetitive, but more 'efficient' since the octree_get function does not save the intermediate values that do not need to be saved. A less repetitive, but less 'efficient' way is to use:

typedef struct Stack {
    uint16_t node;
    uint_fast8_t level;
    uint_fast16_t offset[5];
} Stack;
Stack octree_get(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y) {
    Stack stack = {octree->base, 5};
    while (stack.node&0x8000 && stack.level--)
        stack.node = ((uint16_t *)octree->set)[stack.offset[stack.level] = (set += stack.node&0x7FFF)<<3|octree_index(x, y, z, stack.level)];
    return stack;
} // Returning a struct in and of itself may or may not be optimal but that is arguably a separate question
Octree *octree_set(Octree *octree, const uint_fast8_t x, const uint_fast8_t z, const uint_fast8_t y, const uint16_t new) {
    Stack stack = octree_get(octree, x, y, z);
    if (stack.node != new) {
        if (stack.level) {
            // Subdivide and insert
        } else {
            // Set and merge if necessary
        }
    }
    return octree;
}

In the above solution, the traversal code is not duplicated, but getting a value saves said stack of values, even if not needed later. Keep in mind that this is just an example, but my question involves any variation of such problems where there is a complex calculation and one or more intermediate values may or may not be needed at a later point.

Does anyone know the most efficient way (perhaps eliminating the unnecessary array creation and stores) of doing this while still not duplicating the code? I have thought long and hard about this, and this seems to be a space/time tradeoff. Can someone prove me wrong and find a way that is both non-repetitive as in the second example, but as 'efficient' as the first example?

Answer 1

I would consider the following alternatives, in that order:

1. Start with the DRY variant, even it is less efficient. In most real-world cases, this won't matter. If a benchmark tells you here is your bottleneck, go to option 2.

2. Give the get function a parameter where it is told whether one wants the intermediate values back or not. The parameter could be, for example, a boolean flag or a pointer to the output structure (here Stack) - when that pointer is NULL, no intermediate values will be returned.

   For this, I would keep the new get variant internal to the module (for example, call it get_internal), and provide two new public entries, like get and get_all. get could call get_internal(...,NULL) and get_all could call get_internal(...,&stack). So you don't have to leak the new parameter into the public API.

   In the unlikely case testing the extra parameter is still the bottleneck (and you proofed this by profiling), goto option 3:

3. Live with the duplication, because a specific implementation is really so much faster that it is worth to ignore the DRY principle. This option is something I would only recommend after a thorough benchmark which proves the two former variants are both too slow to fulfill your performance requirements, and #3 really solves it.

   In case the duplication becomes really horrible, and you think #1 and #2 are definitely not fast enough, as a last resort, there is option 4:

4. Implement the get_internal function not with a runtime parameter, but make use of compile time parameters / macros, for providing actually two variants of the function (from one source code). In C++, one could make use of template meta programming to make a relatively clean implementation of this. In C, this can be sometimes necessary, but there is a certain risk to end up in some ugly macro hack where it is debatable if that's better or worse than sacrifycing DRY. So if you consider to go this route, better think twice if it is really worth the hassle.

Answer 2

Newcomer developers have a tendency to copy/paste code and not realize that there's an opening for reusability. Intermediate developers understand the importance of reusability and apply it to everything that looks the same, to the point of overdoing it.
Senior developers look at a potential reusability, compare the benefits (do we make use of the reusable part?) and drawbacks (how complex would a reusable solution have to be?) and make a judgment call based on those observations.

You've identified a possible reusability optimization. The question now is whether acting on it would do more good than bad, compared to what you're currently doing.

Personally, I am not well versed in C (compared to C#) and your current code is already sufficiently complex. I wouldn't want to introduce another layer of abstraction in there.
However, maybe you and your colleagues are very familiar with this and do not consider this to already be complex. If so, that would mean that adding another reusability abstraction makes sense to you.

I cann't definitively tell you what you should do. What you shouldn't do, however, is design your code based on a dogmatic adherence to a principle. Just because you've spotted somewhat of a repetition does not mean that you must remove it.

While DRY phrases itself as an immovable command (don't repeat yourself), it should really be taken as a point of consideration instead (consider if you should avoid repeating yourself here). Unfortunately, CIYSARYH is not a catchy initialism like DRY is.

If you prefer phrasing it as a command: don't forget to consider if this should be made reusable and if not, make sure you can justify why.

You have to weigh the pros and cons and judge accordingly. An internet stranger can't tell you where you should draw the line. DRY, just like pretty much every programming guideline, can end up being an infinite well that you keep digging in. You have to find a reasonable depth at which it becomes irrelevant to dig any deeper.