4
\$\begingroup\$

I've been toying with the idea of making a simple game. In game development, it is good to do things in a more struct-of-arrays style rather than arrays-of-structs style, due to cache locality. However, I wanted to fool around even more, so my class puts all the data in one contiguous block of memory. It was my first time using placement new, and I rather enjoyed the template metaprogramming. I'm not 100% sure that my memory management was done correctly. There are some non-standard parts of the code because I was using Visual Studio:

parameter-pack.hpp

#pragma once

#include <utility> // std::integer_sequence

/**
 * @file Contains structs for doing calculations with parameter packs
 * @details Most of the functions here are for sizeof() calculations related to parameter packs
 */

namespace utils { namespace mp {

/**
 * \brief A struct to "hold" a parameter pack.
 * \tparam Ts The parameter pack that this struct "holds"
 */
template<class... Ts>
struct Pack
{};

/**
 * \brief Obtain the Nth type in a parameter pack.
 * \tparam N The index to obtain
 * \tparam T The beginning of the parameter pack list
 * \tparam Ts The rest of the parameter pack list
 * \see get_t
 */
template<size_t N, class T, class... Ts>
struct Get
{
    static_assert(N < sizeof...(Ts) + 1, "N was too large; out of bounds");
    using type = typename Get<N - 1, Ts...>::type;
};

// Recursion base case
template<class T, class... Ts>
struct Get<0, T, Ts...>
{
    using type = T;
};

/**
 * \brief The type of the element at the Nth position in the parameter pack.
 * \details This is simply a shortened form of Get, but it is easier to use
 *          because you don't have to type out `typename`
 * \tparam N The index of the type to obtain
 * \tparam Ts The parameter pack list that we want to know about
 */
template<size_t N, class... Ts>
using get_t = typename Get<N, Ts...>::type;

/**
 * \brief Obtains the size of the nth element, in bytes, like `sizeof`
 * \tparam N The element to find the sizeof
 * \tparam T The first type in the parameter pack
 * \tparam Ts The rest of the types
 */
template<size_t N, class T, class... Ts>
struct SizeOfNth
{
    static constexpr size_t value = sizeof(get_t<N, T, Ts...>);;
};

/**
 * \brief Sums the size of the first N (including the specified position) types, in bytes.
 * \tparam N The last element to sum the size in bytes up.
 * \tparam T The first type in the parameter pack
 * \tparam Ts The rest of the types
 */
template<size_t N, class T, class... Ts>
struct SizeUpToNth
{
    static_assert(N < sizeof...(Ts) + 1, "N was too large; out of bounds");
    static constexpr size_t value = sizeof(T) + SizeUpToNth<N - 1, Ts...>::value;
};

// Recursion base case
template<class T, class... Ts>
struct SizeUpToNth<0, T, Ts...>
{
    static constexpr size_t value = sizeof(T);
};

/**
 * \brief Obtains the total sum of the size of the types.
 * \tparam Ts The parameter pack types to compute the total size of
 */
template<class... Ts>
struct CombinedSizeOf
{
    static_assert(sizeof...(Ts) > 0, "Useless to discover the size of an empty pack");
    static constexpr size_t value = SizeUpToNth<sizeof...(Ts) - 1, Ts...>::value;
};

}}

grid-data.hpp

#pragma once

#include <new> // placement new
#include <utility>

#include "parameter-pack.hpp"

namespace utils {

/**
 * \brief Contains information internal to the utils namespace. Not public api; could change without warning.
 */
namespace internal {

/**
 * \brief A simple tag for use in tag dispatching within the utils::GridData type.
 */
struct GridData_ConstructorTag
{};

}

using coord_t = size_t;

/**
 * \brief Stores a multitude of types in a grid.
 * \details Rather than having an "array of structs", this implements an optimized version of a
 *          "struct of arrays", where the arrays are actually a 2D grid. This can store several
 *          pieces of information together in the grid, but optimized for cache efficiency.
 *          <br>
 *          This container assumes that it owns any objects stored within it, and it will call the
 *          destructor on any and all stored objects. Also note that if the constructor fails due
 *          to exceptions in initialization, destructors of the type that this container holds are
 *          likely to be called on garbage data.
 *          <br>
 *          Example Usage:
 *          \code{.cpp}
 *          GridData<int32_t, bool> grid{ 100, 100 };
 *          // A grid of height and walkability.
 *          // Loop through and initialize grid
 *          grid.foreach<0>([] (coord_t x, coord_t y, int32_t data) { // Do something with the data });
 *          \endcode
 * \tparam Ts The types to store in the grid.
 */
template<class... Ts>
class GridData
{
    // Simple constructor with the tag; this just initializes the data members; it does not call the
    // constructors of the elements it contains.
    GridData(size_t width, size_t height, internal::GridData_ConstructorTag)
        : width_{ width }
        , height_{ height }
        , data_{ new char[utils::mp::CombinedSizeOf<Ts...>::value * width * height] } {}

public:
    /**
     * \brief Creates a GridData with all its data members default-initialized.
     * \details The default constructors of the elements in the container MUST not
     *          throw, or the destructors may end up being called on garbage data.
     *          To initialize the data members, it becomes necessary to use copy-assignment.
     *          Consider using the other constructor; it can be faster.
     * \param width The width of the grid
     * \param height The height of the grid
     */
    GridData(size_t width, size_t height)
        : GridData{ width, height, internal::GridData_ConstructorTag{} } {
        initializeNoInitializers(std::index_sequence_for<Ts...>{});
    }

    /**
     * \brief Creates a GridData with all its data members initialized to the result of calling the corresponding
     *        initialization function
     * \details Each position in the grid is initialized by calling the function, then `std::move`-ing the result
     *          into the container. The initialization functions MUST not throw, or the destructors for the container's
     *          elements are likely to be called on garbage data. Consider using the other constructor if
     *          copy-assignment is more desirable than `std::move`.
     * \tparam Fs Functions with signature `Ts(coord_t x, coord_t y)`
     * \param width The width of the grid
     * \param height The height of the grid
     * \param initializers The initializers used to initialize the data members
     */
    template<class... Fs>
    GridData(size_t width, size_t height, Fs &&... initializers)
        : GridData{ width, height, internal::GridData_ConstructorTag{} } {
        initialize(std::index_sequence_for<Ts...>{}, std::forward<Fs>(initializers)...);
    }

    /**
     * \brief You should not be copying this object.
     * \details It is designed to hold a large amount of data; you do not want to copy the entire thing
     */
    GridData(const GridData &) = delete;

    /**
     * \brief 
     * \param m 
     */
    GridData(GridData &&m) noexcept
        : width_{ m.width_ }
        , height_{ m.height_ }
        , data_{ m.data_ } {
        m.data_ = nullptr;
    }

    /**
     * \brief Destroys this container, destroying all its elements and freeing any used memory.
     */
    ~GridData() {
        if (data_) {
            destroy(std::index_sequence_for<Ts...>{});
            delete[] data_;
            data_ = nullptr;
        }
    }

    GridData& operator=(const GridData &) = delete;
    GridData& operator=(GridData &&) = delete;

    /**
     * \brief Obtains data at the specified location, with the specified type.
     * \tparam N The type of data elements to get
     * \param x The x coordinate we want to inspect
     * \param y The y coordinate we want to inspect
     * \return The data at the specified coordinate, of the specified type.
     */
    template<size_t N>
    const utils::mp::get_t<N, Ts...>& get(coord_t x, coord_t y) const {
        return *reinterpret_cast<utils::mp::get_t<N, Ts...> *>(this->template elementStart<N>(x, y));
    }

    /**
     * \brief Obtains the data at the specified location, with the specified type. Can be used to set data at a location.
     * \details Note that anything assigned into this container is assumed to be owned by the container.
     * \tparam N The type of data elements to get
     * \param x The x coordinate we want to inspect
     * \param y The y coordinate we want to inspect
     * \return The data at the specified coordinate, of the specified type.
     */
    template<size_t N>
    utils::mp::get_t<N, Ts...>& get(coord_t x, coord_t y) {
        return *reinterpret_cast<utils::mp::get_t<N, Ts...> *>(this->template elementStart<N>(x, y));
    }

    /**
     * \brief Calls the function for each x and y coordinate of the grid.
     * \tparam N The class of types to apply the function over
     * \tparam F A function of the form `void(coord_t, coord_t, T)`. It could return anything, but doesn't need to.
     * \param f The function to apply over the entire class of types.
     */
    template<size_t N, class F>
    void foreach(F &&f) {
        for (coord_t y = 0; y < height(); y++) {
            for (coord_t x = 0; x < width(); x++) {
                (void) f(x, y, get<N>(x, y));
            }
        }
    }

    size_t height() const { return height_; }
    size_t width() const { return width_; }
private:
    coord_t width_;
    coord_t height_;
    char *data_;

    template<size_t N>
    char* elementStart(coord_t x, coord_t y) {
        char *start = data_ + (utils::mp::SizeUpToNth<N, Ts...>::value - utils::mp::SizeOfNth<N, Ts...>::value) * width_ * height_;
        return start + utils::mp::SizeOfNth<N, Ts...>::value * (x + y * width_);
    }

    template<size_t N, class F>
    void initializeBlock(F &&f) {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                new(elementStart<N>(x, y)) utils::mp::get_t<N, Ts...>(std::move(f(x, y)));
            }
        }
    }

    template<size_t... I, class... Fs>
    void initialize(std::index_sequence<I...>, Fs &&... fs) {
        int unused[] = { (initializeBlock<I>(fs) , 1)... };
        (void) unused;
    }

    template<size_t N>
    void initializeBlockNoInitializers() {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                new(elementStart<N>(x, y)) utils::mp::get_t<N, Ts...>;
            }
        }
    }

    template<size_t... I>
    void initializeNoInitializers(std::index_sequence<I...>) {
        int unused[] = { (initializeBlockNoInitializers<I>() , 1)... };
        (void) unused;
    }

    template<size_t N, class T>
    void destroyBlock() {
        for (coord_t y = 0; y < height_; y++) {
            for (coord_t x = 0; x < width_; x++) {
                T *t = reinterpret_cast<T*>(elementStart<N>(x, y));
                t->~T();
            }
        }
    }

    template<size_t... I>
    void destroy(std::index_sequence<I...>) {
        int unused[] = { (destroyBlock<I, utils::mp::get_t<I, Ts...>>() , 1)... };
        (void) unused;
    }
};

}

I did also test it using Google Test, but I'm not that worried about the quality of my test code:

test-grid-data.cpp

#include "grid-data.hpp"

#include "gtest/gtest.h"

#include <string>
#include <tuple>

using namespace utils;

TEST(Utils_GridData, WorksForOneType) {
    GridData<std::string> data{ 100, 100 };
    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            data.template get<0>(x, y) = std::to_string(y * data.width() + x);
        }
    }

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), std::to_string(y * data.width() + x));
        }
    }
}

TEST(Utils_GridData, WorksForOneTypeWithInitializers) {
    GridData<std::string> data{ 100, 100, [] (size_t x, size_t y) { return std::to_string(y * 100 + x); } };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), std::to_string(y * data.width() + x));
        }
    }
}

TEST(Utils_GridData, WorksForTwoTypes) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{ 100, 100 };
    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            data.template get<0>(x, y) = y * data.width() + x;
            data.template get<1>(x, y) = { x, y };
        }
    }

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}

TEST(Utils_GridData, WorksForTwoTypesWithInitializers) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); }
    };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}

TEST(Utils_GridData, WorksForManyWithInitializers) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>, bool, int32_t> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); },
        [] (size_t x, size_t y) { return static_cast<bool>((x ^ y) & 1); },
        [] (size_t x, size_t y) { return static_cast<int32_t>(x - y); }
    };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
            EXPECT_EQ(data.template get<2>(x, y), static_cast<bool>((x ^ y) & 1));
            EXPECT_EQ(data.template get<3>(x, y), static_cast<int32_t>(x - y));
        }
    }
}

TEST(Utils_GridData, ForeachWorks) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>, bool, int32_t> data{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); },
        [] (size_t x, size_t y) { return static_cast<bool>((x ^ y) & 1); },
        [] (size_t x, size_t y) { return static_cast<int32_t>(x - y); }
    };

    bool succeeded = true;
    data.foreach<0>([&] (size_t x, size_t y, uint32_t result) {
        if (result != y * data.width() + x) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<1>([&] (size_t x, size_t y, std::pair<uint32_t, uint32_t> result) {
        if (result != std::make_pair(x, y)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<2>([&] (size_t x, size_t y, bool result) {
        if (result != static_cast<bool>((x ^ y) & 1)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);

    succeeded = true;
    data.foreach<3>([&] (size_t x, size_t y, int32_t result) {
        if (result != static_cast<int32_t>(x - y)) succeeded = false;
    });
    EXPECT_TRUE(succeeded);
}

TEST(Utils_GridData, WorksAfterBeingMoved) {
    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data1{
        100, 100,
        [] (size_t x, size_t y) { return y * 100 + x; },
        [] (size_t x, size_t y) { return std::make_pair(x, y); }
    };

    GridData<uint32_t, std::pair<uint32_t, uint32_t>> data{ std::move(data1) };

    for (size_t y = 0; y < data.height(); y++) {
        for (size_t x = 0; x < data.width(); x++) {
            EXPECT_EQ(data.template get<0>(x, y), y * data.width() + x);
            EXPECT_EQ(data.template get<1>(x, y), std::make_pair(x, y));
        }
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ A quick profiling shows that my version is faster than substituting the char * with a std::tuple of boost::numeric::ublas::matrix: coliru.stacked-crooked.com/a/c06221193c072d5c \$\endgroup\$ – Justin Nov 9 '16 at 14:52
  • \$\begingroup\$ On the other hand, if I instead use std::vector instead of char *, I sometimes end up with the std::vector being more efficient, sometimes my version. In either case, the performance difference ends up being small, except for initialization. coliru.stacked-crooked.com/a/e7503f91e2c8ef62 \$\endgroup\$ – Justin Nov 15 '16 at 11:05
  • \$\begingroup\$ Found a design bug: moving this object requires that objects stored in it are trivially moveable. Additionally, maybe this could take advantage of alignas / alignof. \$\endgroup\$ – Justin Feb 22 '17 at 18:05
  • \$\begingroup\$ Upon further investigation, the sizeof a struct is already aligned for that struct. All we need to do is ensure that the first value is placed in an aligned way. \$\endgroup\$ – Justin Feb 22 '17 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.