Runtime polymorphism without dynamic memory allocation (part 2)

Just a follow-up on Runtime polymorphism without dynamic memory allocation for the reason it’s C++ and you can do all kinds of weird things. This is a fun article. I didn’t think it through.

Last time, I wanted a clear API for the caller and I created an abstraction above std::variant. I did it by returning a lambda that the caller can simply call with the needed arguments.

Then I thought “What if I can do it even more simple?”. I’d like to have the same API as the implementation with the pointer.

object->function(argument);

But without heap allocations.

The storage remains a variant. And I return a pointer to the currently selected type in the variant.

#include <cassert>
#include <variant>

struct P {
    virtual int f(int) const = 0;
    virtual ~P() = default;
};
 
struct A : P {
    int f(int in) const override {return in + 1;}
};
 
struct B : P {
    int f(int in) const override {return in + 2;};
};

struct factory {
    std::variant<A, B> object;

    P* create(char o) {  
        switch(o) {
            case 'a': object = A{}; break;
            default: object = B{}; break;
        }

        return std::visit([](auto& obj) -> P* { return &obj; }, object);
    }
};

int main() {
    factory f{};
    assert(f.create('a')->f(1) == 2);
    assert(f.create('b')->f(1) == 3);
}

 

A particular thing is that I have to use trailing return type for the lambda visitor. This is because “std::visit requires the visitor to have the same return type for all alternatives of a variant” (Clang). So I return all objects through the base class. I’m back to virtual inheritance functions.

Besides the raw pointer, I’m wondering what could go wrong with this approach.

Runtime polymorphism without dynamic memory allocation

Another one on polymorphism

This time is about not using heap allocation while having runtime polymorphism. I will use std::variant for this, so nothing new. What got my attention is how the polymorphic objects are used if stored in a variant. This is the main topic of this short article.

The use case is a factory function that creates polymorphic objects.

Virtual inheritance

I’m taking it step by step, starting with the classic approach using virtual inheritance. For this, I need some pointers, of course.

#include <cassert>
#include <memory>

struct P {
    virtual int f(int) const = 0;
    virtual ~P() = default;
};

struct A : P {
    int f(int in) const override {return in + 1;}
};

struct B : P {
    int f(int in) const override {return in + 2;}
};

std::unique_ptr<P> factory(char o) {
    switch(o) {
        case 'a': return std::make_unique<A>();
        default: return std::make_unique<B>();
    }
}

int main() {
    assert(factory('a')->f(1) == 2);
    assert(factory('b')->f(1) == 3);
}

std::variant

The std::variant solution is to have a variant with all the possible types instead of pointers to the types. This will avoid heap allocations. And it will break the need for inheritance, having objects that are not coupled to a base class anymore. Continue reading Runtime polymorphism without dynamic memory allocation

C++ multiple template parameter packs

The idea

This is just a short idea for multiple template parameter packs on a specific use case. While there are other more generic ways to achieve this, I found a method that is easier to digest for my case.

One of my learning projects is a map-like container with infinite depth, multiple specific types of keys, and any type of value.

The need for multiple template parameter packs came when I wanted to be more specific about “any type of value”. “Any” is… any. Nothing specific, clear, or well-known. And I wanted more clarity.

My map is declared as:

msd::poly_map<int, double, std::string> map;

The template arguments are the types of keys. No types for the values because the map can hold any value. But I want to be as specific as I am for the keys. What I need is to separate the key types from the value types. I want two sets of template parameters. How could I tell them apart?

The solution

After a few minutes of diving in, the idea that popped up is to store the values exactly how I store the keys: inside a variant. The bonus for switching from any to variant is that:

Variant is not allowed to allocate additional (dynamic) memory.

I introduced an auxiliary type to represent a multiple-parameter pack. And I passed two of these to my map: one for keys, one for values.

template<typename... Types>
struct types {
    using types_ = std::variant<Types...>;
};

template<typename Keys, typename Values>
struct poly_map;

poly_map<types<int, double>, types<int, bool>> map;

The full source code

Everything put together in a raw version looks like:

#include <cassert>
#include <map>
#include <variant>

template<typename... Types>
struct types {
    using types_ = std::variant<Types...>;
};

template<typename... Types>
using keys = types<Types...>;

template<typename... Types>
using values = types<Types...>;

template<typename Keys, typename Values>
struct poly_map {
    std::map<typename Keys::types_, poly_map> items_;

    using value_types = typename Values::types_;
    value_types value_;

    template <typename T>
    auto& operator=(T&& v)
    {
        static_assert(std::is_constructible_v<value_types, T>, "wrong value type");

        value_ = std::forward<T>(v);

        return *this;
    }

    template <typename T>
    auto& operator[](const T key)
    {
        return items_[key];
    }

    template <typename T>
    auto& get() const
    {
        static_assert(std::is_constructible_v<value_types, T>, "wrong value type");

        return std::get<T>(value_);
    }
};

struct X {
    int v{};
};

int main() {
    poly_map<keys<int, double>, values<int, bool, X>> map;

    map[1] = true;
    assert(map[1].get<bool>());

    map[2] = X{1};
    assert(map[2].get<X>().v == 1);
    
    //map[1] = 0.1; // does not compile because map can't hold double as value

    map[1][2.2] = 14;
    assert(map[1][2.2].get<int>() == 14);
}

Calling multiple functions for an input

Simply put, when I opt for a data-driven design, I separate the data from the behavior. Given an input as

struct Input {
    int value;
};

I pass it to some components that operate on it. I… call some functions.

void set(Input& in, int value) { input.value = value; }
void reset(Input& in) { input.value = 0; }

Input in{};
set(in, 2);
reset(in);

 

Because life is better with patterns, I’d want to have independent and configurable functions and a clear intent of their role and usage. Short story, a way to do this is a list of functions to be called with an input.

template<typename T, typename... Fs>
void apply(T& in, Fs&&... fs) {
    (fs(in), ...);
}

I’ve used the C++17 fold expression to unpack the template parameters (the list of functions). Continue reading Calling multiple functions for an input

Compile-time recursion in C++17

While not a large upgrade to the C++ standard, C++17 brought some important features. One of them helps me have simpler code in the context of compile-time recursion.

I’ve experimented with some strategies to iterate over a tuple. I wanted a list of different types that I could iterate over as I would do with an array. Without using dynamically allocated memory. Some kind of static polymorphism.

The previous article on this topic gives an implementation for C++14. Which is not that complicated, but whenever I can get something simpler, I’m very interested. That article is the base for this one, thus reading it before will give more context.

I want to improve the iteration that is based on compile-time recursion. More specifically, the exit case of the recursion. The C++14 implementation is based on template specialization. There are two versions of the iterator struct: one iterates over the elements of the tuple except for the last one, and the second one is for the last element, where the iteration must stop.

template<typename T, std::size_t S = std::tuple_size<T>::value, std::size_t I = S - 1>
struct Iterator {
    template<typename C>
    void operator()(T& objects, C callback) {
        callback(std::get<S - I - 1>(objects));
        Iterator<T, S, I - 1>{}(objects, callback);
    }
};

template<typename T, std::size_t S>
struct Iterator<T, S, 0> {
    template<typename C>
    void operator()(T& objects, C callback) {
        callback(std::get<S - 1>(objects));
    }
};

The code is partially duplicated and not the easiest to understand. Any piece of code that can be deleted is the best code I can get. And constexpr if lets me do just that. I can delete one of the structs and have the implementation, including the exit case, in one struct. The constexpr if feature allows the use of an if statement in more complex compile-time cases.

template<typename T, std::size_t I = 0U>
struct Iterator {
    template<typename C>
    void operator()(T& objects, C callback) {
        if constexpr (I < std::tuple_size_v<T>) {
            callback(std::get<I>(objects));
            Iterator<T, I + 1U>{}(objects, callback);
        }           
    }
};

I have an easier-to-read code. The iteration starts naturally from zero, and as long as I’m not past the last element, I apply the given callback, then get to the next element.

Simplicity is always welcome.

GoogleTest parameterized tests with JSON input

This is a full setup of parameterized tests (table-driven tests) with the GoogleTest framework. It includes using JSON test input from a file. If you’d like to skip the “story” and get to the code, you can download the CMake example project.

I assume you know what unit testing is and that tests are as important as the production code (or more important sometimes).

There are several ways to organize tests and their data (provided input and expected output). I’m testing the very simple sum function of a calculator because my focus here is on the tests, not on the tested code. Everything can be applied in more advanced contexts.

// calculator.hpp

#ifndef CALCULATOR
#define CALCULATOR

namespace calculator {

inline int sum(int a, int b) { return a + b; }

}  // namespace calculator

#endif  // CALCULATOR

Simple tests

The simplest test would call the function with some arguments and verify the result. I can create multiple similar tests for specific cases (eg. overflow). It’s the form I’m trying to use as often as possible. I like stupidly simple tests that are extremely easy to understand.

#include <gtest/gtest.h>

#include "calculator.hpp"

TEST(CalculatorSimpleTest, Sum)
{
    const auto actual = calculator::sum(1, 2);
    const auto expected = 3;
    EXPECT_EQ(actual, expected);
}

Table-driven tests

It’s a method I typically use when multiple simple tests (as above) would repeat. I can easily add multiple test cases in a configurable way; rather than thinking about the test code, I’m focusing on the test scenarios.

I always encourage scenario-based tests. What is more important than how. I construct the tests starting with the scenarios I want to cover (basic ones, edge cases), not thinking about lines of code to be covered. Although very important, the coverage should be a result, not a scope. The most important thing is for the source code to work as I promised to the user through the public interface.

If there are special scenarios that I want to be clearly stated by the tests, I add simple tests focused on particular cases besides the table-driven ones that cover the base cases.

The table is a container where each element is a test case.

#include <gtest/gtest.h>

#include <vector>

#include "calculator.hpp"

TEST(CalculatorTableDrivenTest, Sum)
{
    struct Test {
        int a;
        int b;
        int sum;
    };

    const std::vector<Test> tests{{
        {1, 2, 3},
        {4, 5, 9},
    }};

    for (const auto& test : tests) {
        const auto actual = calculator::sum(test.a, test.b);
        const auto expected = test.sum;
        EXPECT_EQ(actual, expected);
    }
}

In case of failure, I can provide details to identify faster what case failed. It’s more useful when I have many test cases. I can print the case number or I can add a description. Continue reading GoogleTest parameterized tests with JSON input

Compile-time validation

Whenever possible, I try to ensure the validation of my program early. I can move some verifications from runtime to compile-time. As such, I will find some issues when I compile the program instead of while running it.

With good tests, I will still find issues earlier than the user. But with human error, some unpleasant cases can reach the user if tests do not cover them. And they might not always be easy to spot.

Context

Take the following situation:

    • A third-party library provides an std::array with some data (integers).
    • I convert this data into another std::array that my application owns (instances of a struct).

It’s as simple as it sounds.

#include <algorithm>
#include <array>
#include <cassert>
#include <numeric>

namespace lib {
using A = std::array<int, 9>;

inline A fetch()
{
    A a;
    std::iota(a.begin(), a.end(), 1);
    return a;
}
}  // namespace lib

namespace app {
struct S {
    int i = 0;
    S() = default;
    explicit S(int v) noexcept : i{v} {}
};
inline bool operator==(int i, S s) noexcept { return i == s.i; }

using B = std::array<S, 9>;

inline B convert(const lib::A& a)
{
    B b;
    std::transform(a.cbegin(), a.cend(), b.begin(), [](int i) noexcept { return S{i}; });

    return b;
}
}  // namespace app

int main()
{
    const auto a = lib::fetch();
    const auto b = app::convert(a);

    assert(std::equal(a.cbegin(), a.cend(), b.cbegin()));
}

 

The issue that might not be too easy to spot, especially if the code is more complicated, is that the third-party library could change the array’s size.

My code would still compile. And of course, given that I have a test (represented here by the assert), it would fail. But I would not know why it failed until I debug the code. And if I don’t have a test, I’m not covered.

Specifically for my code, if the third-party library’s array would get larger than my app’s array, I would get an undefined behavior because I would try to copy data beyond my array’s bounds.

Moreover, a change like that in the third-party library might be something really important for me and it should scream in my face. Continue reading Compile-time validation

static_cast runtime overhead

I take some things for granted and say I will get into details later when needed. Which sometimes can be sane because some subjects don’t have an ending, they get me from one detail to another. And there are situations where I stop at a particular level. It’s the case for static_cast. To simply put it, it turns out I don’t know how it really works.

Because the name includes “static”, I wrongfully assumed it knows, at compile-time, what it’s going to happen to a runtime value. And that it just forcefully and trustfully copies information from one source to another, converting from one type to another. It believes I know what I’m doing and obeys as much as it can.

Another reason for not bothering too much with details is that I never used a static cast for other types than numeric ones. And this simplifies things.

Not long ago I learned that a static cast can have runtime overhead. It was a big surprise until I was reminded of the user-defined conversions and until, of course, I read the documentation.

The simple case

For basic types such as int and float, it’s easier to reason.

float f;
auto i = static_cast<int>(f);

would get to:

movss           xmm0, DWORD PTR [rbp-4]
cvttss2si       eax, xmm0
mov             DWORD PTR [rbp-8], eax

This means:

    • copy the f variable from the stack into the xmm0 register,
    • convert from float to integer into the eax register,
    • copy the result onto the stack in the i variable.

User-defined conversions

When one of the operands is of a user type (eg. a struct), I add a function to intermediate such a conversion because the compiler does not understand how I want the conversion to be performed. Continue reading static_cast runtime overhead

A bitfield abstraction for enum values

Given different values represented by an enum, the requirement is to pass a list of those values to another system. It’s not mandatory to use an enum, I’ve chosen it just as a use case. The list of values can be a vector, an array, a bitset, or any other container or utility that can hold multiple values. Depending on the context, there are advantages and disadvantages over one container or another.

Options

A vector is very easy to use but uses dynamic memory allocation. In an embedded context, the use of dynamic memory can be restricted.

An array uses preallocated memory and has a fixed number of elements, which could be the maximum number of values in the enum. If you want to send fewer elements than the maximum, you must have a convention to let the other system know how many you are sending. This is because you will always send a fixed number of elements (the maximum). You can choose a special value that indicates an element in the array is not of interest. Or you can place the values you want to send starting with the first position in the array, and pass along another value that says how many elements you are sending.

For a bitset, you must know the number of bits used. And you have a general semantic of manipulating values. If these aspects are convenient, a bitset can be an option.

The most simple option I can think of is a bitwise representation on an unsigned, fixed-width integer type (eg: uint32_t). It can give you the smallest memory space to represent multiple values. If you need this list of values in a very small scope, like a small function where you set the bits on a variable which you pass to the other system, it might be enough. If you pass this variable in larger scopes of the project, it’s a matter of time until someone does not know what that variable holds (there is no semantic). And they might confuse it for a variable that holds a single value, not a representation of multiple ones. Then, operations like equality might work by coincidence in some cases, other cases being runtime bugs.

For all of the above and other options not mentioned, you need to obtain the underlying value of the enum. An unscoped enum is implicitly converted to the numeric type you use for the option you choose. From a scoped enum you have to explicitly get the value. Continue reading A bitfield abstraction for enum values

Timeline to 4 years of writing

  • 2002 – I started to learn programming and later worked on some tiny projects.
  • ~2006 – Started to work on some real (and still small) projects for actual clients.
  • 2010 – Had my first job.
  • 2018 – January 26th – 4 years ago today: I wrote my first article on this blog.

When I started writing I had no plans with the blog and I still have none. And it’s great like this. It doesn’t matter too much when or what I write about. I’m just happy with the outcome of learning.

Hello, interviewe(r/e)!