Ausdrucksvorlagen und C ++ 11
Lassen Sie uns einen besonderen Vorteil von Ausdrucksvorlagen betrachten: ETs können verwendet werden, um vektorgroße temporäre Elemente im Speicher zu vermeiden, die bei überladenen Operatoren wie den folgenden auftreten:
template<typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b)
{
std::vector<T> tmp; // vector-sized temporary
for_each(...);
return tmp;
}
In C ++ 11 wendet die return-Anweisung dieser Funktion die Verschiebungssemantik an. Keine Kopie des Vektors. Das ist ein Gewinn.
Wenn ich mir aber einen einfachen Ausdruck anschaue wie
d = a + b + c;
Ich sehe, dass die obige Funktion zweimal aufgerufen wird (für beideoperator+), während die endgültige Zuweisung mit Verschiebungssemantik erfolgen kann.
Insgesamt werden 2 Schleifen ausgeführt. Bedeutet, dass ich ein temporäres Dokument lösche und es gleich danach wieder einlese. Bei großen Vektoren fällt dies aus dem Cache. Das ist schlimmer als Ausdrucksvorlagen. Sie können das Ganze in nur einer Schleife erledigen. ETs können den obigen Code ausführen, der äquivalent ist zu:
for(int i=0 ; i < vec_length ; ++i)
d[i] = a[i] + b[i] + c[i];
Ich habe mich gefragt, ob Lambdas zusammen mit der Bewegungssemantik oder einem anderen neuen Feature so gut wie ETs sind. Irgendwelche Gedanken?
Bearbeiten:
Grundsätzlich erstellt der Compiler mithilfe der ET-Technik einen Analysebaum, der dem algebraischen Ausdruck mit seinem Typsystem ähnelt. Dieser Baum besteht aus inneren Knoten und Blattknoten. Die inneren Knoten repräsentieren Operationen (Addition, Multiplikation usw.) und die Blattknoten repräsentieren Verweise auf die Datenobjekte.
Ich habe versucht, mir den gesamten Rechenprozess wie bei einer Stapelmaschine vorzustellen: Nehmen Sie eine Operation aus einem Operationsstapel und ziehen Sie die nächsten Argumente aus dem Argumentstapel und werten Sie die Operation aus. Legen Sie das Ergebnis zurück auf den Stapel und warten Sie auf die Operation.
Um diese beiden unterschiedlichen Objekte (Operationsstapel und Datenblattstapel) darzustellen, habe ich astd::tuple für die Operationen und astd::tuple für die Datenblätter in einstd::pair<>. Anfangs habe ich einstd:vector Dies führte jedoch zu einem Laufzeit-Overhead.
Der gesamte Prozess verläuft in zwei Phasen: Initialisierung der Stack-Maschine, wobei die Operation und der Argumentstack initialisiert werden. Und die Auswertungsphase, die durch die Zuordnung der gepaarten Container zum Vektor ausgelöst wird.
Ich habe eine Klasse erstelltVec die eine private hältarray<int,5> (die Nutzlast) und die einen überladenen Zuweisungsoperator enthält, der den "Ausdruck" verwendet.
Der Globusoperator* ist für alle Kombinationen der Einnahme überladenVec und "Ausdruck", um die korrekte Behandlung auch in dem Fall zu ermöglichen, in dem wir mehr als nur habena*b. (Beachten Sie, ich habe für dieses pädagogische Beispiel auf die Multiplikation umgestellt - im Grunde, um das schnell zu erkennenimull im Assembler.)
Was zuerst gemacht wird, bevor die Auswertung beginnt, ist das "Extrahieren" der Werte aus den beteiligtenVec Objekte und Initialisieren des Argumentstapels. Das war notwendig, um nicht verschiedene Arten von Objekten herumliegen zu lassen: indexierbare Vektoren und nicht indexierbare Ergebnisse. Das ist was dieExtractor ist für. Wieder eine nette Sache: Variadische Templates werden verwendet, was in diesem Fall zu keinem Laufzeit-Overhead führt (dies alles wird zur Kompilierungszeit erledigt).
Das Ganze funktioniert. Der Ausdruck wird gut bewertet (ich habe auch den Zusatz hinzugefügt, aber der wird hier weggelassen, um in den Code zu passen). Unten sehen Sie die Assembler-Ausgabe. Nur rohe Berechnung, genau so, wie Sie es möchten: Machen Sie es mit der ET-Technik.
Ergebnis. Die neuen Sprachfunktionen von C ++ 11 bieten verschiedene Vorlagen, die (zusammen mit der Metaprogrammierung von Vorlagen) den Bereich der Kompilierzeitberechnung eröffnen. Ich habe hier gezeigt, wie die Vorteile verschiedener Vorlagen genutzt werden können, um Code so gut wie mit der traditionellen ET-Technik zu erzeugen.
#include<algorithm>
#include<iostream>
#include<vector>
#include<tuple>
#include<utility>
#include<array>
template<typename Target,typename Tuple, int N, bool end>
struct Extractor {
template < typename ... Args >
static Target index(int i,const Tuple& t, Args && ... args)
{
return Extractor<Target, Tuple, N+1,
std::tuple_size<Tuple>::value == N+1>::
index(i, t , std::forward<Args>(args)..., std::get<N>(t).vec[i] );
}
};
template < typename Target, typename Tuple, int N >
struct Extractor<Target,Tuple,N,true>
{
template < typename ... Args >
static Target index(int i,Tuple const& t,
Args && ... args) {
return Target(std::forward<Args>(args)...); }
};
template < typename ... Vs >
std::tuple<typename std::remove_reference<Vs>::type::type_t...>
extract(int i , const std::tuple<Vs...>& tpl)
{
return Extractor<std::tuple<typename std::remove_reference<Vs>::type::type_t...>,
std::tuple<Vs...>, 0,
std::tuple_size<std::tuple<Vs...> >::value == 0>::index(i,tpl);
}
struct Vec {
std::array<int,5> vec;
typedef int type_t;
template<typename... OPs,typename... VALs>
Vec& operator=(const std::pair< std::tuple<VALs...> , std::tuple<OPs...> >& e) {
for( int i = 0 ; i < vec.size() ; ++i ) {
vec[i] = eval( extract(i,e.first) , e.second );
}
}
};
template<int OpPos,int ValPos, bool end>
struct StackMachine {
template<typename... OPs,typename... VALs>
static void eval_pos( std::tuple<VALs...>& vals , const std::tuple<OPs...> & ops )
{
std::get<ValPos+1>( vals ) =
std::get<OpPos>(ops).apply( std::get<ValPos>( vals ) ,
std::get<ValPos+1>( vals ) );
StackMachine<OpPos+1,ValPos+1,sizeof...(OPs) == OpPos+1>::eval_pos(vals,ops);
}
};
template<int OpPos,int ValPos>
struct StackMachine<OpPos,ValPos,true> {
template<typename... OPs,typename... VALs>
static void eval_pos( std::tuple<VALs...>& vals ,
const std::tuple<OPs...> & ops )
{}
};
template<typename... OPs,typename... VALs>
int eval( const std::tuple<VALs...>& vals , const std::tuple<OPs...> & ops )
{
StackMachine<0,0,false>::eval_pos(const_cast<std::tuple<VALs...>&>(vals),ops);
return std::get<sizeof...(OPs)>(vals);
}
struct OpMul {
static int apply(const int& lhs,const int& rhs) {
return lhs*rhs;
}
};
std::pair< std::tuple< const Vec&, const Vec& > , std::tuple<OpMul> >
operator*(const Vec& lhs,const Vec& rhs)
{
return std::make_pair( std::tuple< const Vec&, const Vec& >( lhs , rhs ) ,
std::tuple<OpMul>( OpMul() ) );
}
template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... > , std::tuple<OPs...,OpMul> >
operator*(const Vec& lhs,const std::pair< std::tuple< VALs... > , std::tuple<OPs...> >& rhs)
{
return std::make_pair( std::tuple_cat( rhs.first , std::tuple< const Vec& >(lhs) ) ,
std::tuple_cat( rhs.second , std::tuple<OpMul>( OpMul() ) ) );
}
template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... > , std::tuple<OPs...,OpMul> >
operator*(const std::pair< std::tuple< VALs... > , std::tuple<OPs...> >& lhs,
const Vec& rhs)
{
return std::make_pair( std::tuple_cat( lhs.first , std::tuple< const Vec& >(rhs) ) ,
std::tuple_cat( lhs.second , std::tuple<OpMul>( OpMul() ) ) );
}
int main()
{
Vec d,c,b,a;
for( int i = 0 ; i < d.vec.size() ; ++i ) {
a.vec[i] = 10+i;
b.vec[i] = 20+i;
c.vec[i] = 30+i;
d.vec[i] = 0;
}
d = a * b * c * a;
for( int i = 0 ; i < d.vec.size() ; ++i )
std::cout << d.vec[i] << std::endl;
}
Assembler generiert mitg++-4.6 -O3 (Ich musste einige Laufzeitabhängigkeiten in die Vektorinitialisierung einbauen, damit der Compiler nicht das Ganze zur Kompilierzeit berechnet und Sie das tatsächlich sehenimull Anweisungen.)
imull %esi, %edx
imull 32(%rsp), %edx
imull %edx, %esi
movl 68(%rsp), %edx
imull %ecx, %edx
movl %esi, (%rsp)
imull 36(%rsp), %edx
imull %ecx, %edx
movl 104(%rsp), %ecx
movl %edx, 4(%rsp)
movl 72(%rsp), %edx
imull %ecx, %edx
imull 40(%rsp), %edx
imull %ecx, %edx
movl 108(%rsp), %ecx
movl %edx, 8(%rsp)
movl 76(%rsp), %edx
imull %ecx, %edx
imull 44(%rsp), %edx
imull %ecx, %edx
movl 112(%rsp), %ecx
movl %edx, 12(%rsp)
movl 80(%rsp), %edx
imull %ecx, %edx
imull %eax, %edx
imull %ecx, %edx
movl %edx, 16(%rsp)