Адаптация интегрального значения non-constexpr к нетиповому параметру шаблона и раздуванию кода

Рассмотрим функциональный объект F принимая constexpr size_t аргумент I

struct F
{
    template <size_t I>
    constexpr size_t operator()(size <I>) const { return I; }
};

завернутый в тип size <I> где (для краткости)

template <size_t N>
using size = std::integral_constant <size_t, N>;

Конечно, мы могли бы пройти I напрямую, но я хочу подчеркнуть, что это constexpr, используя его в качестве аргумента шаблона. функция F это глупо, но на самом деле это может сделать множество полезных вещей, таких как получение информации из I элемент кортежа F предполагается, что имеет одинаковый тип возврата независимо от I, I может быть любого целочисленного типа, но предполагается, что он неотрицательный.

проблема

Учитывая constexpr size_t значение I мы можем позвонить F от

F()(size <I>());

Теперь, что если мы хотим позвонить F с неконцептором size_t значение i? Учтите следующее:

constexpr size_t L = 10;
idx <F, L> f;
for (size_t i = 0; i < L; ++i)
    cout << f(i) << " ";

(Зачем мне это нужно? Чтобы дать некоторый контекст, я на самом деле пытаюсь встроить составной итератор в представление контейнера, представляющее последовательность "соединенных" (сцепленных) гетерогенных контейнеров. Это даст возможность сказать что-то вроде join(a, b) = c; где массивы join(a, b) а также c имеют одинаковую длину. Тем не мение, i это состояние итератора, поэтому не может быть constexpr Тем не менее, суб-итераторы хранятся в кортеже и должны быть доступны constexpr индекс. Индивидуальный value_type примерно одинаковы, так что объединенная точка зрения может принять их common_type тип, но подконтейнеры и, следовательно, подитераторы имеют разные типы.)

Решение

Здесь я придумал структуру idx <F, L>, который адаптирует функцию F для этого предположим, что входной аргумент меньше L, Это на самом деле компилирует хорошо, давая вывод

0 1 2 3 4 5 6 7 8 9

и вот живой пример.

idx работает путем рекурсивного разложения ввода i в бинарное представление и реконструкцию аналога constexpr N:

template <typename F, size_t L, size_t N = 0, bool = (N < L)>
struct idx
{
    template <size_t R = 1>
    inline constexpr decltype(F()(size <0>()))
    operator()(size_t I, size <R> = size <R>()) const
    {
        return I%2 ? idx <F, L, N+R>()(--I/2, size <2*R>()) :
               I   ? idx <F, L, N  >()(  I/2, size <2*R>()) :
               F()(size <N>());
    }
};

где R представляет собой силу 2 на текущей итерации. Чтобы избежать бесконечной реализации шаблона, специализация дается для N >= L, возвращаясь F()(size <0>()) в качестве фиктивной стоимости:

template <typename F, size_t L, size_t N>
struct idx <F, L, N, false>
{
    template <size_t R>
    inline constexpr decltype(F()(size <0>()))
    operator()(size_t I, size <R>) const { return F()(size <0>()); }
};

Фактически, этот метод является обобщением более распространенной идиомы с логическим аргументом:

bool b = true;
b ? f <true>() : f <false>();

где f это функция, принимающая bool в качестве аргумента шаблона. В этом случае очевидно, что все две возможные версии f создаются

Вопрос

Хотя это работает, и его сложность во время выполнения предположительно является логарифмической в i, Я обеспокоен последствиями времени компиляции, такими как:

  • сколько комбинаций idx И его template operator() создаются для того, чтобы это работало во время выполнения для любого ввода i что не известно во время компиляции? (Я снова понимаю "все возможно", но сколько?)

  • действительно ли возможно встроить operator()?

  • Есть ли альтернативная стратегия или вариант, который "легче" скомпилировать?

  • Должен ли я забыть об этой идее, как о экземпляре чистого кода?

Заметки

Вот время компиляции (в секундах) и размеры исполняемых файлов (в килобайтах), которые я измерял для разных значений L:

 L      Clang(s)    GCC(s)    Clang(KB)    GCC(KB)
 10       1.3       1.7          33         36
 20       2.1       3.0          48         65
 40       3.7       5.8          87        120
 80       7.0      11.2         160        222
160      13.9      23.4         306        430
320      28.1      47.8         578        850
640      56.5     103.0        1126       1753

Таким образом, хотя это выглядит примерно линейно в L это довольно долго и разочаровывающе большой.

Попытка заставить operator() встроенный сбой: вероятно, игнорируется Clang (исполняемый файл еще больше), в то время как GCC сообщает recursive inlining,

Бег nm -C на исполняемом файле, например, для L = 160, показывает 511/1253 разные версии operator() (с Clang/GCC). Это все для N < L так что появляется окончание специализации N >= L действительно встраивается.

PS Я бы добавил тег code-bloat но система не позволит мне.

Источник

4 ответа

Решение

Я называю эту технику магическим переключателем.

Самый эффективный способ сделать это - создать собственную таблицу переходов.

// first, index list boilerplate.  Does log-depth creation as well
// needed for >1000 magic switches:
template<unsigned...Is> struct indexes {typedef indexes<Is...> type;};
template<class lhs, class rhs> struct concat_indexes;
template<unsigned...Is, unsigned...Ys> struct concat_indexes<indexes<Is...>, indexes<Ys...>>{
    typedef indexes<Is...,Ys...> type;
};
template<class lhs, class rhs>
using ConcatIndexes = typename concat_indexes<lhs, rhs>::type;

template<unsigned min, unsigned count> struct make_indexes:
    ConcatIndexes<
        typename make_indexes<min, count/2>::type,
        typename make_indexes<min+count/2, (count+1)/2>::type
    >
{};
template<unsigned min> struct make_indexes<min, 0>:
    indexes<>
{};
template<unsigned min> struct make_indexes<min, 1>:
    indexes<min>
{};
template<unsigned max, unsigned min=0>
using MakeIndexes = typename make_indexes<min, max-min>::type;

// This class exists simply because [](blah){code}... `...` expansion
// support is lacking in many compilers:
template< typename L, typename R, unsigned I >
struct helper_helper {
    static R func( L&& l ) { return std::forward<L>(l)(size<I>()); }
};
// the workhorse.  Creates an "manual" jump table, then invokes it:
template<typename L, unsigned... Is>
auto
dispatch_helper(indexes<Is...>, L&& l, unsigned i)
-> decltype( std::declval<L>()(size<0>()) )
{
  // R is return type:
  typedef decltype( std::declval<L>()(size<0>()) ) R;
  // F is the function pointer type for our jump table:
  typedef R(*F)(L&&);
  // the jump table:
  static const F table[] = {
    helper_helper<L, R, Is>::func...
  };
  // invoke at the jump spot:
  return table[i]( std::forward<L>(l) );
};
// create an index pack for each index, and invoke the helper to
// create the jump table:
template<unsigned Max, typename L>
auto
dispatch(L&& l, unsigned i)
-> decltype( std::declval<L>()(size<0>()) )
{
  return dispatch_helper( MakeIndexes<Max>(), std::forward<L>(l), i );
};

которая требует статической настройки, но довольно быстрая при запуске.

Утверждают что i в границах также может быть полезно.

живой пример

Источник

Если у вашего решения есть ограничение на максимально возможное значение (скажем, 256), вы можете использовать макро-магию и оператор switch, чтобы упростить его:

#define POS(i) case (i): return F<(i)>(); break;
#define POS_4(i) POS(i + 0) POS(i + 1) POS(i + 2) POS(i + 3)
#define POS_16(i) POS_4(i + 0) POS_4(i + 4) POS_4(i + 8) POS_4(i + 12)

int func(int i)
{
    switch(i)
    {
        POS_16(0)
    }
}

Другое возможное решение (с C++11) - использовать шаблоны с переменным числом аргументов:

template<int I>
struct FF
{
    static int f() { return I; }
};


template<typename... I>
int func(int i)
{
    constexpr int (*Func[])() = { I::f... };
    return Func[i]();
}

int main(int argc, char** argv)
{
    func<FF<0>,FF<1>>(1);
}
Источник

Я возьму очевидную позицию и спрошу: "Хочу ли я подчеркнуть, что это constexpr используя его в качестве аргумента шаблона "стоит этой стоимости и если:

struct F
{
    constexpr size_t operator()(size_t i) const { return i; }
    template <size_t I>
    constexpr size_t operator()(size <I>) const { return (*this)(I); }
};

не будет намного более простым решением.

Источник

Это не совсем ответ, и мой вопрос остается в силе, но я нашел обходной путь, который дает впечатляющий импульс при компиляции. Это небольшая настройка решения, приведенного в вопросе, где параметр R перемещен из operator() снаружи к структуре idxи условие завершения теперь включает в себя как R а также N:

template <
    typename F, size_t L,
    size_t R = 1, size_t N = 0, bool = (R < 2 * L && N < L)
>
struct idx //...

Весь код приведен в этом новом живом примере.

Этот подход, по-видимому, сокращает огромное количество ненужных комбинаций специализации для R, Время компиляции и размеры исполняемых файлов значительно уменьшаются. Например, мне удалось скомпилировать за 10,7/18,7 секунд с Clang/GCC для L = 1<<12 (4096), получая исполняемый файл размером 220/239 КБ. В этом случае, nm -C показывает 546/250 версий operator(),

Источник
Другие вопросы по тегам