Help with optimizing virtual method

Question

I am developing a key / value database

https://github.com/nmmmnu/HM4

Currently I have following commands

• XNSUM - sum keys with same prefix
• XRSUM - sum keys from some range
• XNCOUNT - count keys with same prefix
• XRCOUNT - count keys from some range

All this works well, except I have way too many commands - 10+

Now I have idea to add some more, so I want this to look like this:

• XNPIPE prefix | SUM
• XRPIPE start stop | SUM
• XNPIPE prefix | COUNT
• XRPIPE start stop | COUNT

For this I need to do some "API" / interface with virtual methods of function pointers.

Here is very basic idea.

Some reduce commands will require a copy of the input data to be made. (no real copy is done, but I store like 100'000 pointers to objects in array)
Then these will be done as user_map_copy which is very efficient with single vtable call.
Yes all data is copied but that's OK, because is required for other reasons.

However other operations, for example sum and count, does not need "copy" of the input and "copy" will be waste. But if we do not copy, we have to do 100'000 vtable call - user_map.

Because those 100'000 vtable call are to the same object, there should be something I can do, so these calls to be devirtualized. I can guarantee I wont change the vtable between the calls :)

user_map_test - here I am trying to devirtualize the call, without success.

Any idea how I can make user_map more optimal?

I am using C++17.

---

#include <algorithm>
#include <iterator>

struct BaseReducer{
    std::size_t result = 0;

    virtual void map(int a) = 0;
    virtual void map_range(const int *begin, const int *end) = 0;

    // no need the d-tor, but for completeness
    virtual ~BaseReducer() = default;
};

auto user_map(const int *begin, const int *end, BaseReducer &r){
    r.result = 0;

    for(auto it = begin; it != end; ++it){
        r.map(*it);
        // much more logic here
    }
    
    return r.result;
}

auto user_map_test(const int *begin, const int *end, BaseReducer &r){
    r.result = 0;

    void (BaseReducer::*f)(int) = &BaseReducer::map;

    for(auto it = begin; it != end; ++it)
        (r.*f)(*it);

    return r.result;
}

auto user_map_copy(const int *begin, const int *end, BaseReducer &r){
    // here we copy the elements and pass it to the BaseReducer
    // example is very basic so we do not copy, but real code does copy
    // and store pointers to real objects because they are very big.

    r.result = 0;

    int vector[5]; // let suppose know magically know the size

    std::copy(begin, end, vector);

    // ugly because we need pointers to iterate
    r.map_range(std::begin(vector), std::end(vector));

    return r.result;
}

struct SumReducer : BaseReducer{
    void map(int a) final{
            map_(a);
    }

    void map_range(const int *begin, const int *end) final{
        for(auto it = begin; it != end; ++it)
            map_(*it);
    }

private:
    void map_(int){
            ++result;
    }
};

struct CountReducer : BaseReducer{
    void map(int a) final{
            ++result;
    }

    void map_range(const int *begin, const int *end) final{
        result = static_cast<std::size_t>(end - begin);
    }
};

#include <iterator>

int main() {
    const int data[] = { 1, 2, 3, 4, 5 };

    CountReducer cr;

    user_map(std::begin(data), std::end(data), cr);

    std::cout << cr.result << '\n';

    user_map_copy(std::begin(data), std::end(data), cr);

    std::cout << cr.result << '\n';
}

Answer 1

I bet it doesn’t make a difference. If it does: Implement your function with a non virtual inline function named inline_f which has a T* pthis as the first argument and put it in the header file. Then call this instead of the virtual function, so inline_f (obj, args) instead of obj->f(args). To avoid code duplication implement f as inline_f(this, args).

This removes the virtual function call, and the non-virtual call, and allows optimisations if some of the arguments have known values.

Answer 2

If you always have access to the fully-derived type you are using, you don't need virtual functions at all.

struct BaseReducer{
    std::size_t result = 0;
};

// CountReducer and SumReducer as before, but final qualifiers are not needed or allowed

template <typename Reducer>
auto user_map(const int *begin, const int *end, Reducer& r){
    r.result = 0;

    for(auto it = begin; it != end; ++it){
        r.map(*it);
        // much more logic here
    }
    
    return r.result;
}

template <typename Reducer>
auto user_map_copy(const int *begin, const int *end, Reducer& r){
    // here we copy the elements and pass it to the BaseReducer
    // example is very basic so we do not copy, but real code does copy
    // and store pointers to real objects because they are very big.
    r.result = 0;
   
    int vector[5]; // let suppose know magically know the size

    std::copy(begin, end, vector);

    // ugly because we need pointers to iterate
    r.map_range(std::begin(vector), std::end(vector));

    return r.result;
}

int main() {
    const int data[] = { 1, 2, 3, 4, 5 };

    CountReducer cr;

    user_map(std::begin(data), std::end(data), cr);

    std::cout << cr.result << '\n';

    user_map_copy(std::begin(data), std::end(data), cr);

    std::cout << cr.result << '\n';
}