Создание шаблона для цикла в C ++?

Question

У меня есть фрагмент кода C ++ ниже с циклом выполнения for,

for(int i = 0; i < I; i++)
  for (int j = 0; j < J; j++)
    A( row(i,j), column(i,j) ) = f(i,j);

Фрагмент вызывается повторно. Границы цикла «I» и «J» известны во время компиляции (I / J порядка от 2 до 10). Я бы хотел как-то развернуть циклы, используя шаблоны. Основным узким местом являются функции row () и column () и f (). Я хотел бы заменить их эквивалентными метапрограммами, которые оцениваются во время компиляции, используя row<i,j>::enum трюки.

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

A(12,37) = 0.5;
A(15,23) = 0.25;
A(14,45) = 0.25;

Но я бы хотел сделать это, не слишком разрушая структуру for - for. Что-то в духе:

TEMPLATE_FOR<i,0,I>
  TEMPLATE_FOR<j,0,J>
     A( row<i,j>::value, column<i,j>::value ) = f<i,j>::value

Может ли boost :: lambda (или что-то еще) помочь мне создать это?

Answer 1

Хороший компилятор должен сделать развертывание за вас. Например, при компиляции gcc с параметром -O2 включается циклическое развертывание.

Если вы попытаетесь сделать это самостоятельно вручную, если вы не будете тщательно измерять вещи и не будете точно знать, что делаете, вы, вероятно, в конечном итоге получите более медленный код. Например, в вашем случае с ручным развертыванием вы обязаны помешать компилятору выполнить циклический обмен или оптимизацию stripmine (ищите --floop-interchange и -floop-strip-mine в в gcc docs )

Answer 2

Это способ сделать это напрямую:

template <int i, int j>
struct inner
{
  static void value()
  {
    A(row<i,j>::value, column<i,j>::value) = f<i,j>::value;
    inner<i, j+1>::value();
  }
};

template <int i> struct inner<i, J> { static void value() {} };

template <int i>
struct outer
{
  static void value()
  {
    inner<i, 0>::value();
    outer<i+1>::value();
  }
};

template <> struct outer<I> { static void value() {} };

void test()
{
  outer<0>::value();
}

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

Вот способ с вариационными шаблонами, который не требует жестко закодированных I и J:

#include <utility>

template <int j, class Columns>
struct Inner;

template <class Columns, class Rows>
struct Outer;

template <int j, int... i>
struct Inner<j, std::index_sequence<i...>>
{
  static void value() { (A(column<i, j>::value, row<i, j>::value), ...); }
};


template <int... j, class Columns>
struct Outer<std::index_sequence<j...>, Columns>
{
  static void value() { (Inner<j, Columns>::value(), ...); }
};

template <int I, int J>
void expand()
{
  Outer<std::make_index_sequence<I>, std::make_index_sequence<J>>::value();
}

void test()
{
  expand<3, 5>();
}

(фрагмент с созданной сборкой: https://godbolt.org/g/DlgmEl)

Answer 3

Вы можете использовать Повышение MPL .

Пример развертывания цикла приведен на этой странице mpl :: for_each .

for_each< range_c<int,0,10> >( value_printer() );

Не похоже, что все это оценивается во время компиляции, но это может быть хорошей отправной точкой.

Answer 4

Я бы сказал, что это ложная хорошая идея.

В C ++ это: row<i,j>::value
означает, что у вас будет столько разностных функций row<>(), сколько у вас * i. Вы не хотите этого, потому что это увеличит размер кода и сделает много ошибок кэша инструкций.

Я наблюдал это, когда выполнял функции шаблона, чтобы избежать единой логической проверки.

Если это короткая функция, просто вставьте ее.

Answer 5

Извлечение Шаблонные метапрограммы и реализации пузырьковой сортировки .

Answer 6

Вы можете использовать Boost.Mpl для реализации всего этого во время компиляции, но я не уверен, что это будет быстрее. (Mpl по существу повторно реализует все алгоритмы STL как шаблоны метапрограммирования во время компиляции)

Проблема с этим подходом состоит в том, что в итоге вы развернете и вставите много кода, который может перегрузить кэш команд и использовать пропускную способность памяти, которая могла быть сохранена. Это может привести к огромному, раздутому и медленному коду.

Вероятно, я бы, скорее всего, доверил компилятору встроенные функции, которые имеют смысл. Пока определения функций row и column видны из цикла, компилятор может тривиально встроить вызовы и развернуть столько итераций, сколько сочтет целесообразным.

Answer 7

Я никогда не пытался это сделать, поэтому возьмите эту идею с крошкой соли ...

Похоже, что вы можете использовать Boost.Preprocessor , чтобы развернуть цикл (в частности, макросы BOOST_PP_FOR и BOOST_PP_FOR_r ), а затем использовать шаблоны для генерации фактическое константное выражение.

Answer 8

Если вы хотите немного изменить синтаксис, вы можете сделать что-то вроде этого:

template <int i, int ubound>
struct OuterFor {
    void operator()() {
        InnerFor<i, 0, J>()();
        OuterFor<i + 1, ubound>()();
    }
};

template <int ubound>
struct OuterFor <ubound, ubound> {
    void operator()() {
    }
};

В InnerFor i - это счетчик внешних циклов (постоянная времени компиляции), j - счетчик внутренних циклов (изначально 0 - также постоянная времени компиляции), поэтому вы можете оценить строку как шаблон времени компиляции.

Это немного сложнее, но, как вы говорите, row (), col () и f () в любом случае ваши сложные части. По крайней мере, попробуйте и посмотрите, стоит ли производительность. Возможно, стоит изучить другие варианты, чтобы упростить функции row () и т. Д.

Answer 9

f потребуется вернуть double - это невозможно сделать во время компиляции.

Answer 10

Я не фанат шаблонного метапрограммирования, поэтому вы можете принять этот ответ с щепоткой соли. Но прежде чем я потратил любое время на эту проблему, я бы спросил себя:

1. Является ли моя for петля узким местом?
2. Развертывание это будет иметь какое-то значение? Легко тестируется ручным раскручиванием и измерением.

Во многих компиляторах / процессорах «зацикленная» версия может повысить производительность благодаря эффектам кэша.

Помните: сначала измерьте, потом оптимизируйте - если вообще.