Template -ing un ciclo 'for' in C++?

Question

Ho un C++ frammento di seguito con un runtime for ciclo,

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

Il frammento viene chiamato ripetutamente. I limiti del ciclo 'I' e 'J' sono noti al momento della compilazione (I/J sono nell'ordine da 2 a 10). Vorrei srotolare i loop in qualche modo usando i template. Il collo di bottiglia principale sono le funzioni row() e column() e f(). Vorrei sostituirli con metaprogrammi equivalenti che vengono valutati in fase di compilazione, usando i trucchi row<i,j>::enum.

Quello che mi piacerebbe davvero è qualcosa che alla fine risolve il loop in una sequenza di affermazioni del tipo:

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

Ma mi piacerebbe farlo senza distruggendo la for - struttura for troppo. Qualcosa nello spirito di:

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

Può aumentare :: lambda (o qualcos'altro) aiutarmi a creare questo?

Answer 1

Check out Template Metaprograms e bubble sort implementazioni.

Answer 2

Un buon compilatore dovrebbe srotolare per voi. Ad esempio, in gcc la compilazione con l'opzione -O2 attiva lo srotolamento del ciclo.

Se si prova a farlo manualmente, a meno che non si misuri attentamente le cose e si sappia davvero cosa si sta facendo, si rischia di finire con un codice più lento. Ad esempio, nel tuo caso con lo srotolamento manuale, è possibile impedire al compilatore di eseguire uno scambio di loop o l'ottimizzazione del stripmine (cercare --floop-interchange e -floop-strip-mine in the gcc docs)

Answer 3

Tu potrebbe usare Boost MPL.

Un esempio di srotolamento del loop è su questo mpl::for_each page.

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

Non sembra che sia tutto valutata al momento della compilazione, ma può essere un buon punto di partenza.

Answer 4

Direi che è una falsa buona idea.

In C++ questo: row<i,j>::value
significa che si avrà il maggior numero di differenti row<>() funzioni di quello che hai i * j. Non lo vuoi perché aumenta la dimensione del codice e fa un sacco di errori nella cache delle istruzioni.

Ho osservato questo quando stavo facendo le funzioni del modello per evitare un singolo controllo booleano.

Se è una funzione breve, è solo in linea.

Answer 5

È possibile utilizzare Boost.Mpl per implementare l'intero processo in fase di compilazione, ma non sono sicuro che sarà più veloce.(Mpl essenzialmente ri-implementa tutti gli algoritmi di STL come modelli metaprogrammazione a tempo di compilazione)

Il problema di questo approccio è che si finisce per srotolamento e inlining un sacco di codice, che può thrash la cache istruzioni e mangiare larghezza di banda di memoria che avrebbe potuto essere salvata. Questo può produrre codice enorme, gonfio e lento.

Probabilmente probabilmente preferirei che il compilatore incorporasse le funzioni che hanno senso. Finché le definizioni delle funzioni row e column sono visibili dal ciclo, il compilatore può inlineamente chiamare le chiamate e srotolare il numero di iterazioni che ritiene utili.

Answer 6

Non sono un fan della meta-programmazione dei modelli, quindi potresti prendere questa risposta con un pizzico di sale. Ma, prima che ho investito qualsiasi tempo su questo problema, mi chiedo quanto segue:

1. È il mio for ciclo un collo di bottiglia?
2. Lo srotolamento farà qualche differenza? Facilmente testato con srotolamento e misurazione manuale.

In molti compilatori/cpu, la versione "loop" può offrire prestazioni migliori a causa degli effetti della cache.

Ricorda: Misura prima, ottimizza dopo, se non del tutto.

Answer 7

f sarebbe necessario restituire un double - che non può essere fatto in fase di compilazione.

Answer 8

Se siete disposti a modificare la sintassi un po 'si può fare qualcosa di simile:

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()() { 
    } 
}; 

In InnerFor, i è il contatore loop esterno (compilazione costante di tempo), j è il contatore loop interno (inizialmente 0 - anche la costante di tempo di compilazione), quindi è possibile valutare la riga come un modello di tempo di compilazione.

È un po 'più complicato, ma come dici tu, row(), col() e f() sono comunque le tue parti complicate. Almeno provalo e vedi se ne vale la pena. Potrebbe valerne la pena investigare altre opzioni per semplificare le funzioni row(), etc.

Answer 9

non ho mai provato a fare questo in modo da prendere questa idea con un grano di sale ...

Sembra che si potrebbe usare per fare il Boost.Preprocessor srotolamento del loop (in particolare le BOOST_PP_FOR e BOOST_PP_FOR_r macro) e poi utilizzare i modelli per generare l'espressione costante effettiva.

Answer 10

questo è il modo per farlo direttamente:

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(); 
} 

Si può passare attraverso A come parametro per ciascuna delle value s se necessario.

Ecco un modo con i modelli variadic che non richiede ho codificato duro e 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>(); 
} 

(snippet con assembly generato: https://godbolt.org/g/DlgmEl)