3
\$\begingroup\$

The goal of the code is to enable me to express a 2D array in an unsorted coordinate-sparse representation in my code (i.e. a list of individual x, y, value entries in any order), but have this converted at compile-time to a more-readily-accessed row-sparse representation of that array (i.e. an array of pointers to rows, with empty rows as null pointers).

The Code

#include <array>
#include <cassert>
#include <iterator>

namespace ct_sparse {

    template<auto defs, std::iter_value_t<decltype(defs)>::value_t fill_value> struct lut;
    template<typename value_t> struct def;

    namespace {
        template<typename Slot, std::size_t N>
        struct SlotArenaAllocator {
            std::array<Slot,N>& arena;
            std::size_t next_available = 0;
            constexpr SlotArenaAllocator(std::array<Slot,N>& arena): arena(arena) {}
            constexpr Slot* allocate() {
                if (next_available < N) {
                    return &arena[next_available++];
                } else {
                    if consteval {
                        assert(next_available < N); // Not possible to dynamically allocate at compile time
                    } else {
                        return new Slot();
                    }
                }
            }
        };


        template<typename Iter>
        constexpr std::size_t count_width(Iter& defs) {
            std::size_t width = 0;
            for (const auto & entry: defs) {
                if (entry.x > width) {
                    width = entry.x;
                }
            }
            return width + 1; //+1 since we also need a slot for col 0
        }
        template<typename Iter>
        constexpr std::size_t count_height(Iter& defs) {
            std::size_t height = 0;
            for (const auto & entry: defs) {
                if (entry.y > height) {
                    height = entry.y;
                }
            }
            return height + 1; //+1 since we also need a slot for row 0
        }
        template<std::size_t HEIGHT, typename Iter>
        constexpr std::size_t count_filled_rows(Iter& defs) {
            std::array<bool, HEIGHT> row_exists = {false};
            std::size_t row_count = 0;
            for (const auto & entry: defs) {
                if (! row_exists[entry.y]) {
                    row_exists[entry.y] = true;
                    ++row_count;
                }
            }
            return row_count;
        }
        template<auto defs>
        struct table_size_info {
            constexpr static std::size_t WIDTH = count_width(defs);
            constexpr static std::size_t HEIGHT = count_height(defs);
            constexpr static std::size_t FILLED_ROWS = count_filled_rows<HEIGHT>(defs);
        };

    }

    template<typename T>
    struct def {
        using value_t = T;
        std::size_t x;
        std::size_t y;
        value_t value;
    };

    template<auto defs, std::iter_value_t<decltype(defs)>::value_t fill_value>
    struct lut {
        using value_t = std::iter_value_t<decltype(defs)>::value_t;
        using info = table_size_info<defs>;
        using table_row_t = std::array<value_t, info::WIDTH>;

        std::array<table_row_t*, info::HEIGHT> index = {nullptr}; // index into the arena
        std::array<table_row_t, info::FILLED_ROWS> arena = {}; // compile-time arena to place non-empty rows

        constexpr lut() {
            auto allocator = SlotArenaAllocator(arena);
            for (const auto & entry: defs) {
                if (index[entry.y] == nullptr) {
                    index[entry.y] = allocator.allocate();
                    index[entry.y]->fill(fill_value);
                }
                (*index[entry.y])[entry.x] = entry.value;
            }
        }

        constexpr value_t get(const std::size_t x, const std::size_t y) const {
            if (x >= info::WIDTH || y >= info::HEIGHT) return fill_value;
            if (index[y] == nullptr) return fill_value;
            return (*index[y])[x];
        }
    };
}

Usage Example

I was able to get the amount of syntax required at point-of-use to something fairly simple, and it does work:

#include <iostream>
#include <array>
#include "ct_sparse.h"

constexpr std::array definitions(std::to_array<ct_sparse::def<int>>({
    {1, 1, 11},
    {1, 3, 13},
    {2, 3, 23},
    {3, 3, 33},
}));

constexpr ct_sparse::lut<definitions, -1> table;

int main() {
    std::cout << "cols: " << decltype(table)::info::WIDTH << '\n';
    std::cout << "rows: " << decltype(table)::info::HEIGHT << '\n';
    std::cout << "filled: " << decltype(table)::info::FILLED_ROWS << '\n';
    std::cout << "size: " << sizeof(table) << '\n';

    constexpr int e11 = table.get(1,1);
    std::cout << "compile-time access: e11 = " << e11 << '\n';
    constexpr int e12 = table.get(1,2);
    std::cout << "compile-time access: e12 = " << e12 << '\n';

    std::cout << "run-time access of full array:\n";
    for (std::size_t y = 0; y < 5; ++y) {
        for (std::size_t x = 0; x < 5; ++x) {
            int value = table.get(x, y);
            std::cout << value << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}

Which appropriately outputs that there are 4 columns, 4 rows, 2 filled rows, 64 bytes total, and both the compile-time and run-time accesses to the array work exactly as expected.

Inspecting the compiled result on godbolt.org makes it clear that the data layout is indeed what is desired:

table:
        .quad   0
        .quad   table+32
        .zero   8
        .quad   table+48
        .long   -1
        .long   11
        .long   -1
        .long   -1
        .long   -1
        .long   13
        .long   23
        .long   33

(Field order aside, that's more-or-less equivalent to this:)

const int row1[] = {-1, 11, -1, -1};
const int row3[] = {-1, 13, 23, 33};
const int * const table[]  = {nullptr, row1, nullptr, row3};

Specific Concerns

Fixed Template Parameters

Due to the need to count up the rows to determine how large of an arena is needed at compile-time, I couldn't find a way to avoid passing the definitions list as a template parameter. As a result, this same implementation wouldn't work at runtime; it only works if definitions is itself at least implicitly constexpr.

It would be possible to have the using code call count_height and then count_filled_rows itself, and only pass the results as template parameters, but that would inflate the syntax and make it only marginally more flexible, since the results from counting the rows of a non-constexpr input still wouldn't be valid template parameters.

I've considered that it could work to just pass in the empty definitions list for that case (making the type of lut<std::to_array<ct_sparse::def<int>>({}), -1>); add logic to the constructor to run through the input to find the width, height, and number of filled rows; store that size info in member fields; and then depend on dynamic allocation to give me somewhere to put each actual row.

This would mean those extra fields would be present in the data layout for the compile-time version as well -- and despite that, I'd still have to if consteval at every reference to info::FILLED_ROWS in order keep accesses to the compile-time ones appropriately constexpr. (AFACT there's no way to make our theoretical lut.filled_rows field const-enough to let the get use it and still be constexpr, but without forcing initializer-list initialization that would in turn dissalow having count_filled_rows depend on the result of the same evaluation of count_height as used to initialize a potential lut.height.)

Lifetime Management

In addition to the other issues, there's also an issue when it comes to trying to use dynamic memory at runtime. The current partial attempt at this you can still see in SlotArenaAllocator, but it should be clear that this would leak memory due to the lack of any attempt at lifetime management for the new-ed Slots, just returning them as bare pointers:

            constexpr Slot* allocate() {
                if (next_available < N) {
                    return &arena[next_available++];
                } else {
                    if consteval {
                        assert(next_available < N); // Not possible to dynamically allocate at compile time
                    } else {
                        return new Slot(); // this leaks memory
                    }
                }
            }

On the other side though, while I'd like to handle it as a std::unique_ptr, it wouldn't be valid to go the other way either, since converting any of the actual arena slots into unique_ptrs would result in a double-free when both the arena array and the index pointer get destructed.

It seems like there's some way to resolve this by properly implementing some of the STL memory_resource interfaces for the arena and allocator, but I've not been able to make much headway in understanding how to proceed there.

Conclusion

The code I have works fine for my usage for the moment, and providing just a wholly separate implementation for non-constexpr uses wouldn't be difficult. But for future use it would be fairly desirable to be able to transparently unify them and make it not constexpr-only; any suggestions for how to approach this would be appreciated.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Passing the definitions list as a regular parameter

Due to the need to count up the rows to determine how large of an arena is needed at compile-time, I couldn't find a way to avoid passing the definitions list as a template parameter.

It is very unfortunate that parameters of constexpr functions, even if evaluated in a constexpr context, are not considered constexpr themselves. There has been a proposal (P1045) to allow the constexpr keyword for function parameters, which I think is exactly what you would want here. Maybe this will happen some day.

Originally I thought there would not be a way around this, but then I realized that you could pass a lambda as a function parameter. The lambda can be evaluated and the result of that can, surprisingly enough, be used in a constexpr context. Without changing anything in class lut, you can add a helper function to turn a function returning a definition list into a table:

namespace ct_sparse {
    …
    constexpr auto make_sparse(auto gen) {
        return ct_sparse::lut<gen(), -1>{};
    }
}

constexpr auto table = ct_sparse::make_sparse([]{
    return std::to_array<ct_sparse::def<int>>({
        {1, 1, 11},
        {1, 3, 13},
        {2, 3, 23},
        {3, 3, 33},
    });
});

I could not get this to work with GCC, but it does work with Clang, see this working on godbolt.org.

Make fill_value a member variable

While it might have been necessary to pass definitions as a template parameter, the same is not true for fill_value. This can be passed as a regular parameter to the constructor of lut, and stored as a member variable.

With that in place, you can then also pass it as a regular parameter to the proposed make_sparse() function. Now that you have a function that takes everything by normal parameter, you can use if consteval to select whether you need to use class lut with a template parameter, or if you choose another path which can create a sparse lookup table at runtime.

Lifetime management

The current partial attempt at this you can still see in SlotArenaAllocator, but it should be clear that this would leak memory due to the lack of any attempt at lifetime management for the new-ed Slots

You can use new in a constexpr context since C++20, but the allocated memory is not allowed to escape the constexpr context (see also C++ Weekly episode 188). So it has to be deleted before you do anything at runtime. So since you cannot be in constexpr land anymore if you new in SlotAllocator, I would just use a std::deque<table_row_t> to store the non-empty rows, as it provides stable pointers, and then have the array point into that.

\$\endgroup\$
1
  • \$\begingroup\$ The trick with passing the factory function arguments inside lambdas worked superbly, thanks! \$\endgroup\$ Feb 3, 2023 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.