7

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?

7
  • 5
    This is exactly the type of code that prompts one type of commenter to say you should introduce a boolean parameter to control the optional saving of values, and another type to say that you should never, ever have boolean parameters. In my view it is the best argument why you should sometimes use them. Sep 13, 2023 at 6:40
  • 2
    One pattern is of "lazy evaluation". Where a chain of operations "are recorded, but not yet performed" on some input data. The actual operations are only performed IF the lazy value ever becomes a part of the final result evaluation. This is highly effective when code is divided into independent functions and work done by one, may or may not be used at all in future calculations.
    – S.D.
    Sep 13, 2023 at 7:09
  • 1
    Your first code looks perfectly legit to me: The actual repetition is only two lines, also octree_set() is a member of Octree and thus perfectly entitled to access its private data members. So, nothing to fuzz about. I would only add a comment before the while() loop in octree_set() saying something along the lines of //record the path to the leaf node at (x, y, z). Because that's what you are doing. You might even want to create a private member function octree_getPath(), but that's unnecessary imho. Sep 13, 2023 at 14:01
  • 1
    The set variable is not used, this is not repetition, it should be removed. The stack is the required result of the lookup, as well as the node variable, so they cannot be folded into a function call and do not count as repetition. The level variable is just a loop index that should have been written inside a for() initialization statement, imho, it's an integral part of the loop itself. If I count that as a repetition (which I didn't do), it's still only three lines of repetition. Sep 13, 2023 at 15:40
  • 3
    I'd expect a good compiler to inline octree_get into octree_set and then optimize away any unnecessary operations.
    – corvus_192
    Sep 13, 2023 at 18:35

2 Answers 2

14

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.

4
  • 1
    Similar situations where one needs a function that can operate on either of two data structures, but the target platform is horribly inefficient at processing pointer indirection. If a construct like foo.bar takes less than half as much code space as fooPtr->bar, using macros with #include to generate a function which acts on foo and one that acts as bar may yield code which is smaller as well as faster than a single function which accepts a fooPtr argument. While #4 is generally less desirable than the others, there are times where it's the only good approach.
    – supercat
    Sep 13, 2023 at 14:48
  • 3
    Checking the boolean flag is plausibly worse for the CPU pipeline than storing all the value even when you don't need them (would need to test to see for sure)
    – user253751
    Sep 13, 2023 at 16:44
  • 1
    @user253751: that's why its best to try #1 before #2 and profile in each step.
    – Doc Brown
    Sep 13, 2023 at 17:29
  • A compiler that supports constant propagation will very likely generate two copies of that function, making #2 the best option. Sep 14, 2023 at 3:41
0

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.

2
  • Yeah, even on purely its own terms (i.e. without considering things like performance tradeoffs) DRY isn't absolute. It should be something like "Don't repeat yourself where the repetitions would have to change in lockstep". If two pieces of code happen to be the same right now but the reasons why they would change are likely to be independent, then DRY often makes things worse. (Of course whether things are synchronised or independent itself changes over time as the codebase evolves; it's fundamentally a judgement call, not an objective good)
    – Ben
    Sep 14, 2023 at 1:16
  • 1
    @Ben: 100% agree and I would take it slightly further that there can sometimes be cases where there is true reusability (things that would actually change in lockstep) but it would make things prohibitively complex to create the reusability abstraction; at which point the better choice is to acknowledge that DRY would apply but still choose to not apply it anyway. It's a pragmatic decision in some scenarios.
    – Flater
    Sep 14, 2023 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.