Unterschied zwischen Code, der mit einer Vorlagenfunktion erzeugt wird, und einer normalen Funktion

Question

Ich habe einen Vektor mit einer großen Anzahl von Elementen. Nun möchte ich eine kleine Funktion schreiben, die die Anzahl der geraden oder ungeraden Elemente im Vektor zählt. Da die Leistung ein wichtiges Anliegen ist, möchte ich keine if-Anweisung in die Schleife einfügen. Also habe ich zwei kleine Funktionen geschrieben wie:

long long countOdd(const std::vector<int>& v)
{
    long long count = 0;
    const int size = v.size();
    for(int i = 0; i < size; ++i)
    {
        if(v[i] & 1)
        {
            ++count;
        }
    }
    return count;
}

long long countEven(const std::vector<int>& v)
{
    long long count = 0;
    const int size = v.size();
    for(int i = 0; i < size; ++i)
    {
         if(0 == (v[i] & 1))
        {
            ++count;
        }
    }
    return count;
}

Meine Frage ist, kann ich das gleiche Ergebnis durch das Schreiben einer einzigen Vorlage Funktion wie diese erhalten:

template <bool countEven>
long long countTemplate(const std::vector<int>& v1)
{
    long long count = 0;
    const int size = v1.size();
    for(int i = 0; i < size; ++i)
    {
        if(countEven)
        {
            if(v1[i] & 1)
            {
                ++count;
            }
        }
        else if(0 == (v1[i] & 1))
        {
            ++count;
        }
    }
    return count;
}

Und es so zu verwenden:

int main()
{
  if(somecondition)
  {
     countTemplate<true>(vec); //Count even
  }      
  else
  {
     countTemplate<false>(vec); //Count odd
  } 
}

Wird der für die Vorlage und die Version ohne Vorlage generierte Code derselbe sein, oder werden zusätzliche Anweisungen ausgegeben?

Bitte beachten Sie, dass die Zählung der Zahlen nur der Veranschaulichung dient, schlagen Sie also bitte keine anderen Zählmethoden vor.

EDIT : Ok. Ich stimme zu, dass es vielleicht nicht viel Sinn aus Sicht der Leistung zu machen. Aber zumindest unter dem Gesichtspunkt der Wartbarkeit möchte ich nur eine Funktion statt zwei pflegen müssen.

Answer 1

Die Schablonenversion Mai und, sehr wahrscheinlich, wird vom Compiler optimiert werden, wenn er sieht, dass eine bestimmte Verzweigung im Code nie erreicht wird. Die countTemplate Code zum Beispiel, wird die countEven Schablonenargument auf true gesetzt, damit der ungerade Zweig weggeschnitten wird.

(Entschuldigung, ich kann keine andere Zählmethode vorschlagen)

In diesem speziellen Fall könnten Sie Folgendes verwenden count_if auf Ihrem Vektor:

struct odd { bool operator()( int i )const { return i&1; } };
size_t nbOdd = std::count_if( vec.begin(), vec.end(), odd() );

Dies kann auch optimiert werden und ist viel kürzer :) Die Entwickler der Standardbibliothek haben sich viele Gedanken über mögliche Optimierungen gemacht, also nutzen Sie sie besser, wenn Sie können, anstatt Ihre eigene for-Schleife zu schreiben.

Answer 2

Ihre Version der Vorlage wird einen Code wie diesen erzeugen:

template <>
long long countTemplate<true>(const std::vector<int>& v1)
{
    long long count = 0;
    const int size = v1.size();
    for(int i = 0; i < size; ++i)
    {
        if(true)
        {
                if(v1[i] & 1)
                {
                        ++count;
                }
        }
        else if(0 == (v1[i] & 1))
        {
                ++count;
        }
    }
    return count;
}

template <>
long long countTemplate<false>(const std::vector<int>& v1)
{
    long long count = 0;
    const int size = v1.size();
    for(int i = 0; i < size; ++i)
    {
        if(false)
        {
                if(v1[i] & 1)
                {
                        ++count;
                }
        }
        else if(0 == (v1[i] & 1))
        {
                ++count;
        }
    }
    return count;
}

Wenn also alle Optimierungen deaktiviert sind, wird die if werden theoretisch noch vorhanden sein. Aber selbst ein sehr naiver Compiler wird feststellen, dass Sie eine Konstante testen, und einfach die if .

In der Praxis sollte es also keinen Unterschied im generierten Code geben. Sie können also die Vorlagenversion verwenden und sich keine Sorgen machen.

Answer 3

Ich vermute, dass ein guter Compiler überflüssigen Code in Ihrer Vorlage ausschneidet, da countEven ist eine Kompilierzeitkonstante und es ist sehr einfach, eine solche Optimierung während der Instanziierung der Vorlage zu implementieren.

Auf jeden Fall wirkt es ziemlich seltsam. Sie schrieben eine Vorlage, aber tun "dynamische Umschaltung" innerhalb. Vielleicht versuchen Sie etwas wie das:

struct CountEven {}
struct CountOdd {}

inline void CountNum(int & num, long long & count, const CountEven &)
{
   if(num & 1)
   {
      ++count;
   }
}

inline void CountNum(int & num, long long & count, const CountOdd &)
{
   if(0 == (num & 1))
   {
      ++count;
   }
}

template <class T>
long long countTemplate(const std::vector<int>& v1)
{
    long long count = 0;
    const int size = v1.size();
    for(int i = 0; i < size; ++i)
    {
        CountNum(v1[i], count, T());
    }
    return count;
}

Sie wählt die notwendigen CountNum() Funktionsversion in der Kompilierungsphase:

int main()
{
  if(somecondition)
  {
     countTemplate<CountEven>(vec); //Count even
  }      
  else
  {
     countTemplate<CountOdd>(vec); //Count odd
  } 
}

Der Code ist chaotisch, aber ich denke, Sie haben die Idee verstanden.

Answer 4

Dies hängt davon ab, wie intelligent der Compiler-Optimierer ist. Der Compiler könnte in der Lage sein zu erkennen, dass die if-Anweisung eigentlich redundant ist und nur ein Zweig davon ausgeführt wird, und das Ganze zu optimieren.

Der beste Weg, dies zu überprüfen, ist ein Blick in die Assemblerdatei - dieser Code wird nicht allzu viel Maschinencode erzeugen.

Answer 5

Das erste, was mir in den Sinn kommt, sind die beiden "Optimierungsregeln":

• Entscheiden Sie sich nicht voreilig.
• Tun Sie es noch nicht.

Der Punkt ist, dass wir uns manchmal über einen Leistungsengpass aufregen, der in der Praxis nie auftreten wird. Es gibt Studien, die besagen, dass 20 Prozent des Codes für 80 Prozent der Software-Ausführungszeit verantwortlich sind. Das bedeutet natürlich nicht, dass man voreilig pessimistisch ist, aber ich glaube nicht, dass das bei Ihnen der Fall ist.

Im Allgemeinen sollten Sie diese Art der Optmierung nur durchführen nach Sie haben einen Profiler auf Ihr Programm angesetzt und die wirklichen Engpässe ermittelt.

Was Ihre Funktionsversionen betrifft, so hängt dies, wie andere bereits sagten, von Ihrem Compiler ab. Denken Sie einfach daran, dass Sie mit dem Template-Ansatz nicht in der Lage sein werden, Aufrufe zur Laufzeit umzuschalten (Templates sind ein Werkzeug zur Kompilierzeit).

Ein letzter Hinweis: long long ist (noch) nicht Standard in C++.