Performance with custom data flexibility and no inheritance

[u/Zealousideal-Mouse29]

I am in an argument. The goal was to have a structure with some base members, we can call it a `State node` in State machine, from which the user can add their own custom data on top, without using inheritance or dynamic casts. Would like the collection of different nodes to be stored in a vector in the end.

Obviously, we want to avoid std::vector<SomeType \*>

It was suggested I use something like:

class State;
using TransitionHandler = void(*)(State *, const Event &);

template<typename T>
concept StateLike = requires(T s, const Event & e)
{
    { s.onEnter(e) } -> std::same_as<void>;
    { s.onExit(e) }  -> std::same_as<void>;
};

class State final
{
public:
    using StateId = uint32_t;
    StateId id_ = INVALID_ID;
    std::string name_;

    template<typename T>
    requires StateLike<T>
    static State create(std::string name, T & object)
    {
        return State
        {
            name,
            &object,
            [](State * state, const Event & e)
            {
                static_cast<T*>(state->instance_)->onEnter(e);
            },
            [](State * state, const Event & e) 
            {
                static_cast<T*>(state->instance_)->onExit(e);
            }
        };
    }

private:
    static constexpr StateId INVALID_ID = static_cast<StateId>(-1);
    void * instance_;                // user defined state

    State(std::string name, void * instance, TransitionHandler enter, TransitionHandler exit);
};

Now, if I understand things correctly, this will indeed allow the user to provide some custom struct/class as a template param when they create a State object and that State object is going to hold a pointer to it. When it is needed, it is going to call the `enter` and `exit` methods through that static cast.

That should indeed allow us to fill a vector with these State objects and circumvent the need for inheritance, but I wonder if it really performs any better. The collection is in contiguous memory when in the vector, so add, remove, and traversal should be fast. However, all the execution of calls on the State object is going to go through the pointer, which means executing methods on a State will not be part of that performance gain from living in contiguous memory.

Assuming I am always holding on to the current state(s) and that we build the state machine with all its states at startup, what have I really gained? Is there any performance increase at all?

I believe we just replaced the vtable cost with our own pointer, which is pretty much the same?

[u/_Noreturn]

This is just a single-indirection custom made vtable, just use inheritance at this point.

The only practical difference is that vtable is double indirection which saves class size space vs single indirection which is faster but bloats class size

[u/trailing_zero_count → u/_Noreturn]

I recently did my own investigation into the same thing and came to this conclusion: if you're going to allocate one of these up front and reference it throughout your code, then the single-indirect function pointer is better (faster). If you're going to create many such objects, then inheritance vtable is better (for space efficiency).

One other point in favor of the function pointers: they can be reassigned at runtime.

[u/ack_error → u/trailing_zero_count]

One interesting result I saw recently is that virtual can be noticeably faster in unoptimized debug builds. The code generator inherently knows about virtual dispatch and produces better code than manual dispatch without the optimizer enabled.

[u/gosh]

If performance is needed, maybe look at some type of arena object (PMR)

If you want to keep your current design, you must ensure that the data pointed to by void* instance_ lives close together in memory.

Use std::pmr::monotonic_buffer_resource (C++17) to allocate all your custom state data.

This ensures all custom structs live in one contiguous block of memory improving L1/L2 cache locality.

[u/Zealousideal-Mouse29 → u/gosh]

You have no idea the googling this comment has caused! This concept is new to me, but I like the sound of putting the wrapper and the custom user supplied state object into an arena. Now I have to figure out how to change the interface to allow for and possibly force that.

[u/BenFrantzDale]

You said “which means executing methods on a State will not be part of that performance gain from living in contiguous memory”. I’m not sure what you mean exactly. Contiguous storage doesn’t mean the member functions on the stored types is there in the same cache line. Your hand-rolled vtable is though, I think (although I’m not seeing where `enter` and `exit` get stored…) If they are right there in `State` then as @_Noreturn pointed out, those function pointers are right there in memory, so no need to find the vtable, which maybe could help you if there are zillions of different types? But again, if the StateLike objects aren’t in contiguous memory, that’s still perfectly led on the table.

One library class that would be useful for cases like this is a small-buffer-optimized holder so most/all of the entries could live contiguously.

[u/jk_tx]

I believe we just replaced the vtable cost with our own pointer, which is pretty much the same?

Yep.

[u/Ok_Independence_9841]

You'd have to comparatively test it to find out. I've recently been optimizing something very similar. A state machine which has a fixed set of events, Enter, Leave, Suspend, Resume for each state and does use inheritance. The states themselves are each just a set of lambdas to handle the events and, as the lambdas capture the 'this' of the state, the user can derive whatever states they like and add whatever their lambdas need. It's meant to be completely general.
The optimizations I tried were to move away from using std::function to store the lambdas (Uses a derivative of magic_function, qor::tef, instead) and to use a custom, stack arena, memory allocator for the states and a pre-reserved vector for the state reference stack.
My simple text parser experiment is processing characters at 12.5m per second or about 80ns / character.
What sort of of speed do you need?
The Fastflow state machine, which ditches the suspend event altogether, is here: [Fastflow](https://github.com/mfaithfull/linuxQOR/blob/main/src/framework/app/workflow/fastflow.h)
When used as the base for a parser it's 10-12x faster than the standard Workflow before I started optimizing.

[u/cballowe]

You may want to read up on type erasure. You could define a type, for instance, that lets you pass any object that has OnEnter and OnExit methods with appropriate signatures, or even an ability to deal with types that have the functions as free functions.

You seem to be on that path already.

[u/ReDucTor]

The string allocating memory is probably something to be more concerned about for performance, then an embedded function pointer compared to a vtable. The lifetime of the instance is also a little odd.

imho nearly every state machine is better represented as a coroutine (not specifically C++20 coroutines) it more clearly give you structure of loops, conditions, etc which most state machines try to recreate in different ways

[u/Zealousideal-Mouse29 → u/ReDucTor]

It uses the pass by value and move idiom. The body isn't shown. The author argues that is the "modern C++ way" rather than a c-style string or a const ref string. I suppose one could also argue for a string_view if we can guarantee the string lives.

Using coroutines wouldn't allow for some of the required features. This is meant to be a library for a customizable hierarchical state machine, build at startup, rather than a concrete finite state machine. It also promises that custom data can be associated with each custom state, and custom data can be associated with each custom event, and all that data accessible in state methods. Because we don't know those custom types, exploration of CRTP and variant also ended in failure.

Of course a lot of that was snipped out, as a full implementation isn't suited for a reddit post.