Автоматическое создание операторов switch во время компиляции для разреженной индексации массива - PullRequest
Новая
       8

Автоматическое создание операторов switch во время компиляции для разреженной индексации массива

1 голос
/ 24 октября 2019

Есть ли способ генерировать операторы переключения времени компиляции для сопоставления индексов? Например, если у меня есть последовательность 1,5,8 и я хочу сопоставить ее с 0,1,2, есть ли способ, которым компилятор может сгенерировать функцию во время компиляции, которая при задании 1,5,8 возвращает соответственно 0,1,2,Чтобы лучше проиллюстрировать то, что я хочу, я подготовил эту структуру разреженного массива: https://godbolt.org/z/QpWVST

#include <tuple>
#include <limits>

template<size_t depth, size_t Idx, size_t I, size_t...Is>
size_t get_idx()
{
    static_assert(Idx==I || sizeof...(Is)>0, "Index not found.");
    if constexpr(Idx==I) return depth;
    else return get_idx<depth+1, Idx,Is...>();
}

template<typename T, size_t... Is>
struct sparse_array
{
    constexpr static size_t N = sizeof...(Is);
    constexpr static size_t size() { return N; }

    T e[N];

    constexpr sparse_array() : e{} {}
    template<typename...type_pack>
    constexpr sparse_array(const type_pack&... pack) : e{ pack... }
    {
        static_assert(sizeof...(type_pack) == size(), "Argument count must mach array size.");
    }

    template<size_t I>
    constexpr size_t idx()
    {
        return get_idx<0, I, Is...>();
    }

    size_t idx(const size_t i)
    {
        // how to achieve somethig like this?
        return idx<i>();
    }

    constexpr T& at(size_t idx)
    {
        return e[idx];
    }
};

template<typename T, size_t...Is>
auto make_dense_array(std::index_sequence<Is...>&& seq)
{
    return sparse_array<T, Is...>{};
}

template<typename T, size_t N>
using dense_array = decltype(make_dense_array<T>(std::declval<std::make_index_sequence<N>>()));

size_t test()
{
    dense_array<int, 3> a;
    sparse_array<int,1,5,8> b;
    return b.idx<8>();
}

Я хочу также иметь возможность передавать переменные времени выполнения, которые будут проходить через переключатель с индексами и возвращатьсоответствующий соответствующий индекс. Единственная идея, которую я имею для решения этой проблемы, заключается в создании массива последовательности Is... и последующем создании цикла for с инструкциями if для возврата правильного индекса. Другим вариантом является использование карты (но это также не время компиляции). sparse_array, как правило, будет очень маленьким, и мне бы хотелось, чтобы у меня была возможность делать большинство вещей во время компиляции.

1 Ответ

1 голос
/ 24 октября 2019

Как-то так? 

static constexpr size_t idx(size_t i)
{
    size_t j = 0;
    if(!(... || (j++, i == Is))) {
        throw "Index out of range!";
    }
    return j-1;
}

Может быть немного сложно читать, но делать то, что вы хотите, если я правильно понял. После создания экземпляра это в основном эквивалентно серии if else, проходящей слева направо по индексам в Is.

. Вы можете сделать его более читабельным, разделив тело выражения сгиба на лямбду. ,Вы также должны заменить выражение throw на то, что подходит для вас.

С помощью квалификатора constexpr это можно использовать и в шаблонной версии: 

template<size_t I, auto s = idx(I)>
static constexpr size_t idx() {
    return s;
}

(Установкарезультат в аргументе шаблона по умолчанию гарантирует оценку времени компиляции.)

Это не самый эффективный код, разделяющий те же проблемы, что и у написанного вручную оператора switch. В зависимости от предсказуемости входных данных многие ветви часто могут быть неправильно предсказаны, и в этом случае (в основном) версия без ответвлений будет предпочтительнее. Это может быть достигнуто путем соответствующего изменения выражения сгиба.

Если число индексов не мало, цикл локального кэша инструкций предпочтительнее для локальности кэша команд: 

static constexpr size_t idx(size_t i)
{
    static constexpr std::array ind{Is...};
    size_t j = 0;
    for(; j < ind.size() && i != ind[j]; j++);
    if(j == ind.size())
        throw "Index out of range!";
    return j;
}

Опять же, может быть предпочтительнее заменить ранний выход в цикле.

Если массив еще больше, может быть полезно не только использовать объявленный массив с циклом, но и реализовать двоичный поиск по этому массиву.

Стандартные алгоритмы, такие как std::any_of, std::find и std::binary_search, могут использоваться вместо реализаций ручного поиска. Однако эти алгоритмы будут constexpr только в C ++ 20, и это ограничит использование здесь.

...