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

Wenn Sie sich um Optimierungsfragen kümmern, versuchen Sie, es wie folgt zu gestalten:

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 ) {
      // According to C++ Standard 4.5/4: 
      // An rvalue of type bool can be converted to an rvalue of type int, 
      // with false becoming zero and true becoming one.
      if ( v1[i] & 1 == countEven ) ++count;
    }
    return count;
}

Ich glaube, dass der obige Code genauso kompiliert wird wie der Code ohne Vorlagen.

Answer 2

Verwende STL, Luke :-) Es ist sogar als Beispiel in Referenz

bool isOdd(int i)
{
    return i%2==1;
}

bool isEven(int i)
{
    return i%2==0;
}

std::vector<int>::size_type count = 0;
if(somecondition)
{
    count = std::count_if(vec.begin(), vec.end(), isEven);
}
else 
{
    count = std::count_if(vec.begin(), vec.end(), isOdd);
}

Answer 3

Im Allgemeinen wird das Ergebnis ähnlich sein. Sie beschreiben eine O(n)-Iteration über den linearen Speicher des Vektors.

Wenn Sie einen Vektor von Zeigern hätten, wäre die Leistung plötzlich viel schlechter, weil die Speicherlokalität der Referenz verloren gehen würde.

Generell gilt jedoch, dass selbst Netbook-CPUs gigantische Mengen an Operationen pro Sekunde ausführen können. Eine Schleife über Ihr Array ist höchstwahrscheinlich kein leistungskritischer Code.

Sie sollten Ihren Code so schreiben, dass er gut lesbar ist, dann ein Profil erstellen und dann überlegen, ob Sie nicht doch lieber von Hand etwas optimieren sollten, wenn das Profiling die Hauptursache für ein Leistungsproblem aufzeigt.

Und Leistungssteigerungen ergeben sich in der Regel aus algorithmischen Änderungen; wenn Sie die Anzahl der Quoten beim Hinzufügen und Entfernen von Elementen aus dem Vektor mitzählen würden, wäre es beispielsweise O(1) zum Abrufen...

Answer 4

Ich sehe, Sie verwenden lang lang für Zähler, und das bedeutet wahrscheinlich, dass Sie eine große Anzahl von Elementen im Vektor erwarten. In diesem Fall würde ich mich auf jeden Fall für die Template-Implementierung entscheiden (wegen der Lesbarkeit des Codes) und die if-Bedingung einfach außerhalb der for-Schleife verschieben.

Wenn wir davon ausgehen, dass der Compiler keinerlei Optimierung vornimmt, hätten Sie 1 Bedingung und möglicherweise mehr als 2 Milliarden Iterationen durch den Vektor. Da die Bedingung außerdem sein würde wenn (wahr) o wenn (false) die Verzweigungsvorhersage würde perfekt funktionieren und die Ausführung würde weniger als 1 CPU-Befehl betragen.

Ich bin mir ziemlich sicher, dass alle Compiler auf dem Markt diese Optimierung haben, aber ich würde meinen Favoriten zitieren, wenn es um die Leistung geht: "Vorzeitige Optimierung ist die Wurzel allen Übels" y "Es gibt nur 3 Regeln für die Optimierung: Messen, messen und messen" .

Answer 5

Wenn Sie sich absolut absurd für schnelle siehe Code:

(ein geschickter Compiler, oder einer, der dies mit Direktiven oder Intrinsics andeutet, könnte dies parallel mit SIMD tun; CUDA und OpenCL würden dies natürlich zum Frühstück essen).

int count_odd(const int* array,size_t len) {
   int count = 0;
   const int* const sentinal = array+len;
   while(array<sentinal)
      count += (*array++ & 1);
   return count;
}

int count_even(const int* array,size_t len) {
   return len-count_odd(array,len);
}