Рассмотрим функциональный объект 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
но система не позволит мне.
Я называю эту технику магическим переключателем.
Самый эффективный способ сделать это — создать собственную таблицу переходов.
// 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()
,