How can I use CRTP to remove a virtual method in this context?

Question

I have the following program similar to my code base. The FunctionState class, which executes some kind of algorithm (potentially in several threads), and the Function class, which controls the use of FunctionState classes and can perform some operations of installing / uninstalling the algorithm.

#include <iostream>
#include <vector>

class FunctionState;

class Function {
public:
    virtual FunctionState* NewFunctionState() = 0;

protected:
    std::vector<FunctionState*> states;
};

class FunctionState {
public:
    FunctionState(Function* func) : mFunc(func) {}

    virtual void RunState() = 0;
    void ExecuteFunctionLotsAndLotsOfTimes();

private:
    Function* mFunc;
};

#define VERY_BIG_NUMBER 10

void FunctionState::ExecuteFunctionLotsAndLotsOfTimes() {
    for(int i = 0; i < VERY_BIG_NUMBER; ++i) {
        RunState();
    }
};

class PrintFunction : public Function {
    FunctionState* NewFunctionState();
};

class PrintFunctionState : public FunctionState {
public:
    PrintFunctionState(PrintFunction* func) : FunctionState(func) {}

    void RunState() override {
        std::cout << "in print function state" << '\n';
    }
};

FunctionState* PrintFunction::NewFunctionState() {
    FunctionState* state = new PrintFunctionState(this);
    states.push_back(state);
    return state;
}

class AddFunction : public Function {
    FunctionState* NewFunctionState();
};

class AddFunctionState : public FunctionState {
public:
    AddFunctionState(AddFunction* func) : FunctionState(func), x(0) {}

    void RunState() override {
        ++x;
    }
private:
    int x;
};

FunctionState* AddFunction::NewFunctionState() {
    FunctionState* state = new AddFunctionState(this);
    states.push_back(state);
    return state;
}


int main() {
    Function* func = new PrintFunction();
    Function* func2 = new AddFunction();
    std::vector<Function*> vec = {func, func2};

    for(auto& func : vec) {
        func->NewFunctionState()->ExecuteFunctionLotsAndLotsOfTimes();
    }

    return 0;
}

Now I was profiling my code and saw that there is a hot spot in FunctionState :: ExecuteFunctionLotsAndLotsOfTimes (). The problem is that this function is repeated many times and calls RunState (), a virtual function in the FunctionState class. There, I perform many operations that could potentially infer vtable pointers from L1 cache, as a result of which L1 cache will skip every iteration of the loop.

, . , CRTP. FunctionState , RunState().

, CRTP, Function:

• FunctionState ( )?

• Function?

  3. Function, ? , Function ?

, . - 10 + ( , ).

, RunState(), CRTP, .

CRTP:

#include <iostream>
#include <vector>

class Function;

template<class T>
class FunctionState {
public:
    FunctionState(Function* func) : mFunc(func) {}

    void RunState() {
        static_cast<T*>(this)->RunState();
    };

    void ExecuteFunctionLotsAndLotsOfTimes();
private:
    Function* mFunc;
};

class Function {
public:
    virtual FunctionState* NewFunctionState() = 0;

protected:
    std::vector<FunctionState*> states;
};

#define VERY_BIG_NUMBER 10

template <typename T>
void FunctionState<T>::ExecuteFunctionLotsAndLotsOfTimes() {
    for(int i = 0; i < VERY_BIG_NUMBER; ++i) {
        RunState();
    }
};

class PrintFunctionState;
class PrintFunction : public Function {
    PrintFunctionState* NewFunctionState();
};

class PrintFunctionState : public FunctionState<PrintFunctionState> {
public:
    PrintFunctionState(PrintFunction* func) : FunctionState<PrintFunctionState>(func) {}

    void RunState() {
        std::cout << "in print function state" << '\n';
    }
};

PrintFunctionState* PrintFunction::NewFunctionState() {
    PrintFunctionState* state = new PrintFunctionState(this);
    states.push_back(state);
    return state;
}

class AddFunctionState;
class AddFunction : public Function {
    AddFunctionState* NewFunctionState();
};

class AddFunctionState : public FunctionState<AddFunctionState> {
public:
    AddFunctionState(AddFunction* func) : FunctionState<AddFunctionState>(func), x(0) {}

    void RunState() {
        ++x;
    }
private:
    int x;
};

AddFunctionState* AddFunction::NewFunctionState() {
    AddFunctionState* state = new AddFunctionState(this);
    states.push_back(state);
    return state;
}


int main() {
    Function* func = new PrintFunction();
    Function* func2 = new AddFunction();
    std::vector<Function*> vec = {func, func2};

    for(auto& func : vec) {
        func->NewFunctionState()->ExecuteFunctionLotsAndLotsOfTimes();
    }

    return 0;
}

Answer 1

CRTP?
, :

#include <iostream>
#include <vector>

class PrintFunctionState;
class AddFunctionState;
class FunctionState;

class Function {
    template<typename T>
    static FunctionState * InternalNewFunctionState(Function *self, std::vector<FunctionState*> &states) {
        FunctionState* state = new T(self);
        states.push_back(state);
        return state;
    }

public:
    template<typename T>
    static Function * create() {
        Function *func = new Function;
        func->internalNewFunctionState = &InternalNewFunctionState<T>;
        return func;
    }

    FunctionState* NewFunctionState() {
        return internalNewFunctionState(this, states);
    }

private:
    FunctionState * (*internalNewFunctionState)(Function *, std::vector<FunctionState*> &);
    std::vector<FunctionState*> states;
};

class FunctionState {
public:
    FunctionState() = default;
    virtual ~FunctionState() = default;
    virtual void ExecuteFunctionLotsAndLotsOfTimes() = 0;
};

template<typename Derived>
class IntermediateFunctionState: public FunctionState {
public:
    IntermediateFunctionState(Function* func) : mFunc(func) {}

    void ExecuteFunctionLotsAndLotsOfTimes() override {
        Derived *self = static_cast<Derived *>(this);
        for(int i = 0; i < 10; ++i) {
            self->RunState();
        }
    }

private:
    Function* mFunc;
};

class PrintFunctionState : public IntermediateFunctionState<PrintFunctionState> {
public:
    PrintFunctionState(Function* func) : IntermediateFunctionState(func) {}

    void RunState() {
        std::cout << "in print function state" << '\n';
    }
};

class AddFunctionState : public IntermediateFunctionState<AddFunctionState> {
public:
    AddFunctionState(Function* func) : IntermediateFunctionState(func), x(0) {}

    void RunState() {
        std::cout << "in add function state" << '\n';
        ++x;
    }

private:
    int x;
};

int main() {
    Function* func = Function::create<PrintFunctionState>();
    Function* func2 = Function::create<AddFunctionState>();
    std::vector<Function*> vec = { func, func2 };

    for(auto& func : vec) {
        func->NewFunctionState()->ExecuteFunctionLotsAndLotsOfTimes();
    }

    return 0;
}

, .
, , , .

Answer 2

Function non-template NewFunctionState,

class FunctionStateBase {
    virtual void ExecuteFunctionLotsAndLotsOfTimes() = 0;
    // No void RunState()!
}

template<typename T>
class FunctionState {
    void ExecuteFunctionLotsAndLotsOfTimes();
    // Still no void RunState()!
}

class PrintFunctionState : public FunctionState<PrintFunctionState> {
    void RunState();
}

template <typename T>
void FunctionState<T>::ExecuteFunctionLotsAndLotsOfTimes() {
    for(int i = 0; i < VERY_BIG_NUMBER; ++i) {
        static_cast<T*>(this)->RunState(); // Statically bound!
    }
};

Answer 3

, , . , :

#include <iostream>

/*
    Just make print invocations a little less cluttered for our purposes here.
*/
template <typename Type>
void Show(Type value)
{
    std::cout << value << std::endl;
}

/*
    Base class for function types 
*/
template <typename Self>
class Function 
{
    public:

/*
    For the best performance possible, we'll always inline this function.
*/    
    inline void RunState()
    {
        static_cast<Self*>(this)->RunState();
    }

    void ExecuteFunctionLotsAndLotsOfTimes(int iterations = 1)
    {
        for(int i = 0; i < iterations; ++i)
        {
            Show("...Loop...");    
            RunState();
        }    
    }
};

/*
    Everything here is placed in an internal namespace, as none of it will be used by the caller.
*/
namespace Internal_
{

/*
    ChainFunctionLink works like an array of functions. Each of it members 
    is either some kind of function object or another ChainFunctionLink.
*/    
template <typename First, typename Second>
struct ChainFunctionLink : Function<ChainFunctionLink<First, Second>>
{
    ChainFunctionLink(First first, Second second)
    : first(first), second(second)
    {    }

    inline void RunState()
    {
        first.RunState();
        second.RunState();
    }

    First
        first;
    Second
        second;
};

/*
    We won't be able to explicitly specify the template parameters of ChainFunctionLink 
    later, so a generating function will be needed to deduce them for us. 
*/
template <typename First, typename Second>
ChainFunctionLink<First, Second> MakeChainFunctionLink(First first, Second second)
{
    return ChainFunctionLink<First, Second>(first, second);
}

} // namespace Internal_

/*
    ChainFunction generates ChainFunctionLink for the caller.
*/
template <typename First, typename Second, typename ...Next>
auto ChainFunction(First first, Second second, Next ...next)
{
    return Internal_::MakeChainFunctionLink(first, ChainFunction(second, next...));
}

/*
    The last link in the chain.
*/
template <typename Last>
Last ChainFunction(Last last)
{
    return last;
}

// Example usage:

class PrintFunction : public Function<PrintFunction>
{
    public:

    inline void RunState()
    {
        Show("PrintFunction::RunState()");
    }    
};

class AddFunction : public Function<AddFunction>
{
    public:

    inline void RunState()
    {
        Show("AddFunction::RunState()");
    }        
};

int main() 
{
    auto 
        chain = ChainFunction(AddFunction(), AddFunction(), AddFunction(), PrintFunction());
    chain.ExecuteFunctionLotsAndLotsOfTimes(4);      
}

, , , , , ( ) .

: . , ChainFunctionLink members first second . ChainFunction, , ...