Class design, responsibility granulation, efficiency and performance

Question

I am in a design dilemma. I have a set of data that can be interpreted in numerous ways, but I cannot really decide how finely grained should it be. To illustrate it with some simple code:

class Base {
    Datamembers data;
    virtual void doStuff() = 0;
};

class T1 : public Base {
    void doStuff() {
        // do T1 stuff
    }
};

class T2 : public Base {
    void doStuff() {
        // do T2 stuff
    }
};

class ...

// ---------------------------

class Master {
    enum Role {
        T1, T2 ...
    };

    Role r;
    Datamembers data;

    void doStuff() {
        switch (r) {
        case T1:
            // do T1 stuff
            return;
        case T2:
            // do T2 stuff
            return;
        case ...
        }
    }
};

In reality the number of responsibilities is much higher than 2, currently still in the two digit range, but may grow further. Also, it is not one, but several doStuff()s at play.

In the first case, the data is encapsulated in a base class, and doStuff() is a pure virtual, which each derived class implements. Each responsibility is encapsulated in its own, dedicated type.

In the second case doStuff() is not a virtual function, and the responsibility is stored as an extra member in a Role, and the method switches the role and executes the appropriate code.

The two designs achieve the same goal in a different way, but what are the consequences?

Code maintenance:

The first approach seems cleaner, but even though usually clean implies maintainable, I feel it is kind of fragmented, which may end up reducing the ease of maintenance.

In the second approach all the code for the different responsibilities is crammed in the same place, which may sound dirty, but in many cases having it all in the same place may actually be easier, since all you have to do is scroll rather than jump around different files. But then again... it is still a big wall of code, not obvious in the example code above, but in practice it will be 4-5 digit lines of code. Although there is an easy remedy for that, just implement a function for each case that takes this as a parameter to access the data and force inlining to eliminate the overhead of extra function calls (even if not virtual).

Performance:

In my case, I deal with massive trees of objects, where doStuff() will be executed in tight loops, traversing that tree.

In approach one, the method is virtual, this means I get penalty for the indirection. Also, the code is spread across multiple types, which may end up fragmenting it in memory, reducing cache efficiency.

In the second approach the method is not virtual, and all code is essentially in a single function, which means it will be tighter in memory, and potentially more cache friendly. There is the switching penalty vs the indirection and fragmentation of the first approach.

Memory usage:

Although it is missing from the example code above, the hierarchy does have a constructor with plenty of arguments. Meaning that in the first approach each derived class will have its own constructor with the same parameters, redirecting those to the base class constructor. This, aside from tedious to implement for each type, also adds some code bloat. And there is the overhead of the v-tables. Both the extra constructors and v-tables are avoided in the second approach.

---

Obviously, I've made some considerations, and had this been a smaller undertaking, I'd do both and compare. But it is actually a lot of work and it is not really possible, so I'd appreciate some experienced opinions - are my considerations valid, am I missing something, is there another, better way to do it?

As it seems the scale of the problem isn't entirely clear, I will just summarize it. I am talking about an object tree, potentially tens of millions of nodes big, a responsibility hierarchy of currently 30 roles, expected to grow to over 100. Right now I have approximately about 200 lines of code per role, although the number varies. Parallelization is not an option, since node result depends on parent or children nodes results, so I am limited to a single thread traversing the tree, currently processing 200-300k nodes a second.

Answer 1

You've possibly already seen some variant of Donald Knuth's "premature optimization" quote:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

This is a good quote, but it's equally accurate if you replace "premature" with "misplaced". You talk about traversing large trees and executing code in tight loops so thinking about performance certainly isn't premature, but I think the optimization you're thinking of may well be a bit misplaced.

If you're about to execute over 10,000 lines of code, it seems extremely unlikely that whether you enter into those lines via a method call or switch statement is going to have a noticeable effect on the overall performance. If you're in such a tight, performance-intensive situation that the nanosecond-to-microsecond range cost of a method call is important, then your 10,000 line statement already means you're screwed.

So unless I'm misunderstanding your question, I think that the focus of your optimization is misplaced. A much more important concern will be whether running the contents of the doStuff methods in a tight loop will have acceptable performance. If not, you'll have to consider higher-level strategies like caching results or parallelizing. It's hard to comment on these without knowing the specifics of your situation better.

Only once the contents of those doStuff methods run on a timescale comparable to the time savings you might get from in-lining the method should you consider doing that. Otherwise it's misplaced optimization and you should put performance out of your head while making that design decision.

Answer 2

You can use Visitor pattern. Visitor pattern with C++ templete is highly efficient.

class T1 {
    public: void do(Node& node) {...}
};

class T2 {
    public: void do(Node& node) {...}
};

class Master {
public:
    template <typename T>
    void traverse() {
        T t;
        for each node in the tree {
            t.do(node);
        }
    }
};

Master m;
m.traverse<T1>();

If you have many traversal algorithms, Strategy pattern can be used together.

Answer 3

A couple of points about optimization, first:

• the overhead for a virtual method dispatch vs entering a case statement is roughly the same; unless the rest of your code is extremely efficient, it is unlikely to make a noticeable difference.

• regarding cache usage, unless the per-role routines are small enough to fit more than one in a single cache line, there will be no difference between the two. Only locality within a cache line matters; for objects larger than a cache line they can be randomly spread over the entire system memory and the cache will be just as effective.

• if your class already has virtual members, the first option you present will use less memory. This may result in a lower memory bandwidth and therefore a slight improvement in performance.

Regarding maintainability of the code, however, you seem to have neglected a third possibility, which is to have Role being an abstract class with a doStuff method to which your main (non-virtual) doStuff method can then delegate. You would then create a subclass for each role you have, and a single static instance of each subclass would be shared between each node on your tree with that particular role.

This has all the advantages of your first approach without the cited disadvantage of duplicated code for constructors. Furthermore, as the main class's doStuff will get inlined, it should be exactly equivalent performance-wise to your first approach.

Answer 4

As it seems the scale of the problem isn't entirely clear, I will just summarize it. I am talking about an object tree, potentially tens of millions of nodes big, a responsibility hierarchy of currently 30 roles, expected to grow to over 100. [...] currently processing 200-300k nodes a second.

With these kinds of numbers, and provided that there is a strong notion of quality that arises from being able to process nodes faster, I wouldn't call these concerns premature since they relate to interface design in a fairly broad context more than implementation in a teeny, isolated one.

I'm going to venture the unpopular route and actually suggest the second solution for both efficiency and maintainability reasons provided that:

1. There are very few places that performs this kind of type check.
2. The state for each role (Datamembers as you've shown), is homogeneous (does not vary) per Role. This part is key, as otherwise my entire answer will be invalidated.
3. Datamembers is fairly small.
4. You do not need an open architecture in this context (ex: no need for an external client, say a plugin, to add new roles on the fly).
5. You find it easier in this case to debug/trace through more centralized code.

Dynamic Dispatch is Cheap Here

Now as a caveat:

Currently that's about 30 roles for about 6k lines of code. On average, 200 lines of code. And it is mostly arithmetic on the members. There is no branching, no function calling or any of that stuff.

With these kinds of numbers, the cost of dynamic dispatch becomes especially cheap in comparison (but this is not the cost we necessarily want to avoid the most). The pipeline ends up being plenty deep enough for effective branch prediction to work, and we still often need some form of branching anyway for the switch. The cost of the optimization barrier (being unable to inline function calls, i.e.) for functions that span an average of 200 LOC is hardly anything to worry about.

Memory Efficiency

There's a bigger, glaring cost I think that people are missing here, and it relates to memory. Given #2 (homogeneous data, only different actions on the same data), a solution that involves polymorphism is going to imply:

1. A dynamic allocation per role and a loss of a contiguous representation within a tree node.
2. A vptr overhead per role (this would be quite trivial if sizeof(Datamembers) is hundreds of bytes, e.g., but it would be far from trivial if it's like 32 bytes). This is going to be a bit larger than, say, a 16-bit or 32-bit index on 64-bit systems.
3. Yet another pointer overhead per tree node to store the memory address to the dynamically-allocated role.

1 could be cheapened considerably using a fixed allocator, and a single fixed allocator can be used for all roles given the homogeneity of Datamembers since they'll all be the same size. Yet that's also degrading the maintainability of your code when a simple alternate solution exists which would allow you to store Datamembers contiguously with your tree nodes using this second Master solution without reaching for custom allocators.

The costs associated with 2 and 3 are unavoidable with a polymorphic solution.

This is the most glaring efficiency and maintenance overhead to me, and the switch version gets around that completely. It's not so much to avoid dynamic dispatch, it's to avoid 1, 2, and 3 above. The biggest problem is that, when processing hundreds of thousands of nodes per second (or more potentially as you optimize further), a polymorphic memory representation would look like this:

When these two memory blocks could potentially be coalesced into a single, contiguous block otherwise.

Maintainability

Given that 1-5 in the top list are valid assumptions, then you might even have an easier time maintaining the second version. It depends on the motions you have to go through when adding a new role.

Naturally in a codebase that uses conditionals in 50 different decentralized places checking for the type of object being passed to it, introducing a new type is going to be a horrendous nightmare (as well as extremely error-prone). But if you have 3 centralized places, it might be even easier with the switch.

This is considering things from a post-optimization side, taking into account that speeding up the first solution will likely involve custom memory allocators and so forth. At the end of this, the second solution might very well be just as easy or easier to maintain.

Hybrid Solution

You can potentially get a hybrid and balance the performance and maintainability needs through your own custom table of function pointers. Note that this is not about function pointers vs. virtual functions (the latter can actually be more efficient in non-homogeneous cases where a single object stores a single vptr as opposed to many function pointers), but about avoiding the memory inefficiencies above while still getting the ability to easily extend the number of roles you can support.

The solution might look like this:

// We have one of these per *type* of role, not per role instance.
// This is like a simulated vtable, but we're not doing it to avoid
// virtual function calls (that would almost always be silly).
// We're doing it to avoid memory fragmentation since we're facing a 
// homogeneous data context where sizeof(Role) is always going to be the 
// same regardless of the type of role.
struct Role {
    // `data` could be const here depending on whether roles mutate the data.
    typedef void RoleFunction(Datamembers& data);

    RoleFunction* func1;
    RoleFunction* func2;
    // etc
};

// Add new role entries here with the appropriate function pointers set.
// The index can be stored in your tree nodes to indicate which role each
// node has.
vector<Role> roles;

// Store this in your tree nodes.
DataMembers data;
int role_type;      // index into 'roles' above.
... // other stuff you need with your tree node -- arranged to 
    // minimize padding (typically descending order from biggest
    // to smallest).

... something to this effect. With that the maintenance cost of implementing a new role shrinks down to just implementing a few functions conforming to this RoleFunction signature, and adding pointers to them to this Master class in the form of a bundled Role entry. The resulting index can then be used to associate which role each tree node has.

With this you avoid the memory inefficiencies described above while retaining the ability to easily extend this solution wherever you want (can implement all your roles in one source file if you like).

The dynamic dispatch overhead is still there, but it was never a very big cost in this kind of scenario with a couple hundred lines of code per average to execute (even the optimization barrier will typically be moot with such a deep pipeline).

Answer 5

Where you're going to gain with the granular approach is if you have to configure your program where you need a different six roles at different times. This would keep you from having to load or even think about the other 24. And if you need another 30 roles, it's much easier to add those as individual classes than have another 6000 lines in your switch statement. See the Zero one infinity rule--the switch statement imposes an exact limit on how many cases you can handle.

If your Master Class needs to do anything else other than your 30 cases, then it's going to get really crowded in there, really fast, especially if you embrace the switch statement approach for all of those things.

Answer 6

Just to supplement what other people have said, worrying about virtual function dispatch time is worrying about trivia.

A large hierarchy has another, hidden, source of performance issues. You need to know how to clean these out, on an ongoing basis, while developing the code.

Here's an example.

The hidden source of performance issues is this: Most lines of code are calls to methods of other classes, and a method you can call is like a credit card. It makes spending easy, so with a credit card, on average you spend more than you would if spending were not so easy.

In software, this effect compounds over many layers. At one layer you can spend more than you need to by 50%, because you generally assume things are efficient, and if they are not perfect, so what? At a lower layer you (or your teammates) also do it. Those two layers do not have to be adjacent. 1.5 * 1.5 = 2.25, so you've slowed down the software by more than twice! This can easily escalate to an order of magnitude or more.

There's a funny psychological effect going on here. When somebody writes a super-useful function or method foo, they tend to assume its users will respect it and use it sparingly. OTOH, each of those users think foo is such a great, well-written, efficient function that you can really get a lot done by using it a lot! Sometimes this happens when the writer and the user are the same person.

All of this is not a reason to avoid layers, just as credit cards are not a bad idea. It is a reason to know how to find and remove the inefficiencies, just as credit cards require discipline.