адаптация интегрального значения 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 но система не позволит мне.

5

Решение

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

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

// 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 в границах также может быть полезно.

живой пример

3

Другие решения

Если у вашего решения есть ограничение на максимально возможное значение (скажем, 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);
}
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); }
};

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

0

Это не совсем ответ, и мой вопрос остается в силе, но я нашел обходной путь, который дает впечатляющий импульс при компиляции. Это незначительная настройка решения, приведенного в вопросе, где параметр 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(),

0
По вопросам рекламы [email protected]