Geschwindigkeit von Referenzen in C ++

Question

Ich habe an einem Projekt arbeiten und versuchen, die Quelle einer großen Verlangsamung der Ausführungszeit zu finden und haben es auf eine einzige Methode verengt, die ich es geschafft haben, aus der Logik zu optimieren. Das Problem ist, dass meine Lösung beinhaltet eine Referenz verwendet wird, die einen anderen Abschnitt des Codes macht ganz langsam laufen ... Die Frage, die ich beantworten möchte ist, warum die innere Schleife so viel länger dauert, zu bewerten, wenn die Karte eine Referenz im Gegensatz zu eine lokale Variable?

Hier ist die alte Art und Weise vor der Optimierung:

// old method: create an empty map, populate it
// and then assign it back to the path object later
map<int,float> screenline_usage; 

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here. 
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[it->first] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~12 seconds
}

// This function call is evaluated 400k times for an overall execution time of ~126 seconds
path->set_zone_screenline_usage(access_mode, zone_id, screenline_usage); 

// TOTAL EXECUTION TIME: 138 seconds. 

Neue Art und Weise nach der Optimierung:

// new method: get a reference to internal path mapping and populate it
map<int, float>& screenline_usage =
  path->get_zone_screenline_usage(access_mode, zone_id);
screenline_usage.clear();

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[it->first] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~76 seconds
}

// New method... no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: 76 seconds (62 second time saving) ... but should be able to do it in just 12 seconds if the use of reference didn't add so much time :(

Hier sind die zugehörigen Subroutinen aus diesem Code aufgerufen:

// This is the really slow routine, due to the copy assignment used. 
void set_zone_screenline_usage(int access_mode, int zone_id,
  map<int,float>& screenline_usage)
{
  m_container[access_mode][zone_id] = screenline_usage; 
}

map<int,float>& get_zone_screenline_usage(int access_mode, int zone_id)
{
  return m_container[access_mode][zone_id]; 
}

NOTES: Timing-Informationen ist für einen einzigen Durchlauf, in dem der obige Code etwa 400k mal ausgewertet. Der Zeitpunkt erfolgt einige Klassen, die ich den RDTSC Zeitstempelzähler zugreifen gebaut (ja ich weiß, TSC Zeitstempelzähler bedeutet), der Durchschnittswert von numCandidates ist 10 und die durchschnittliche Anzahl der Elemente in die screenline_usage Karte gesetzt ist 25.

---

UPDATE: Zunächst vielen Dank an alle, die hier beteiligt bekommen hat. Ich denke, dass dies am Ende gar nichts c ++ Referenzen zu tun hatte, und hatte mehr mit Cache-Konsistenz zu tun. Ich habe den optimierten Code oben mit einem Vektor ersetzt & und eine Hash-Funktion als Mitglied variable Karte implementiert

// newest method: get a reference to internal path mapping (as vector) and populate it 
// map<int,int> m_linkNum_to_SlNum declared in header and populated in constructor. 
vector<float>& screenline_usage = path->get_zone_screenline_usage(access_mode, zone_id);

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[m_linkNum_to_SlNum[it->first]] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~9 seconds
}

// Newest method... again no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: just 9 seconds (129 second time saving) ... this is even better than using a locally constructed map which took 12 seconds in the inner loop :)

Es scheint mir hier, dass, da der Vektor nicht lokal ist, sondern ein zusammenhängender Speicherblock und die Hash-Funktion (m_linkNum_to_SlNum) ist eine lokale Membervariable, führt dieser Ansatz zu Code / Daten, die fähig ist, passen in den Cache, ohne Daten in den Hauptspeicher zu gehen, die in der erheblichen Geschwindigkeit bis zur Folge hat. Weitere Schlussfolgerungen angesichts dieser Ergebnisse werden sehr geschätzt.

Answer 1

Wie pro meinem Updates, ich denke, das ist wahrscheinlich ein Cache-Konsistenzproblem eher als ein C ++ Referenz Problem.

Answer 2

Vielleicht C ++ Sie Compiler in der Lage ist, einen Code für die lokale Karte Inline, aber nicht, wenn die Karte ist eine Referenz.

Answer 3

Ihre Frage ist unklar. Haben Sie vor zu fragen, warum eine Karte durch Bezugnahme vergeht schneller als mit dem Wert vorbei? Wenn ja, ist die Antwort einfach: a. Karte von Wert zurückgibt, bedeutet das Kopieren es in seiner Gesamtheit, und das Kopieren einer großen Karte eine sehr teure Operation ist

Auf der anderen Seite, wenn Ihre Frage ist: Warum ist schneller einen Verweis auf eine bereits bestehende Karte zu bekommen und dass bevölkert, als es eine neue Karte zu machen, so eine Hypothese ist, dass es mit

 screenline_usage[it->first] += usage * it->second; 

Da die Taste [it-> Erste] existiert bereits in der Karte innerhalb Weg-> get_zone_screenline_usage, dann ist dies einfach eine Update-Operation und erfordert keine Speicherzuweisung. Wenn jedoch screenline_usage ist eine leere Karte, dann wird jeder Zugriff auf einen neue [it-> Erste] bedeutet, dass es zunächst einen neuen Map-Knoten aus dem Heap zuzuweisen hat, und das ist teuer.

Answer 4

Wenn ich Ihre Frage richtig verstanden, Sie bedeuten, dass auf einer lokale Stack zugewiesen Karte Einfügen <> ist viel schneller als das Einfügen zu einer vorhandenen Heap zugeordnet Karte <>, die Sie durch Verweis abgerufen werden.

Es gibt mehrere Möglichkeiten, die Leistung zu beeinträchtigen werden. Ich bezweifle es etwas mit C ++ Referenz Leistung zu tun, aber.

Die erste Möglichkeit ist, dass durch screenline_usage zu einem Referenz Ändern Sie „im wesentlichen“ Abrufen eines Zeigers auf ein vorhandenes Objekt sind. Die eigentliche Instanz des Objekts nicht map<int,float> werden kann, könnte es etwas durch, die von der Karte erbt. Zum Beispiel könnte es sich um eine Karte mit einer benutzerdefinierten Vergleichsfunktion für sie definiert sein. Oder eine Unterklasse mit gewinde syncronization Logik. Da Sie nicht wissen, welche Art Sie von dem Anruf erhalten m_container[access_mode][zone_id], kann man sehr gut eine Unterklasse bekommen, die nicht gut auf dem Einsatz nicht durchführt. (Sie können sehen, welche Art Sie im Debugger zurück, übrigens.) Die durch eine leere map<int,float> Erstellen Sie eine Garantie haben, dass der Typ eine aktuelle Karte ist <>, und nicht eine Unterklasse.

Nehmen wir an, dass Sie eine tatsächliche Karte erhalten <> Instanz zurück.

Die zweite Möglichkeit ist, dass in dem besonderen Geschmack von STL, die Sie verwenden, funktioniert die map::clear() Funktion interner Datenstrukturen nicht effizient ausräumen verwendet, um die assoziative Indizes zu halten. Soweit ich mich erinnere, stl :: map <> verwendet einige komplexe interne Hashing und Eimer Strukturen effizienter Einsatz und Abruffunktionen zur Verfügung zu stellen. Allerdings ist es unklar, was mit denen passiert, wenn man klar () aufrufen. So möglich ist es, dass screenline_usage.clear() führt zu einer weniger effizienten Karte gegen einzufügen, als wenn Sie mit einer leeren Karte gestartet.

Schließlich nehmen wir an, dass ich falsch bin, und es ist keine dieser beiden Möglichkeiten. Es ist ein einfacher Weg, um zu bestimmen, ob die Differenz das Ergebnis ist eine Bezugsgröße zu verwenden. Sie können versuchen, eine neue Karte auf dem Heap Aufteilung und es zu einer Referenz in Ihrem Code, wie diese Zuordnung:

map<int, float>& screenline_usage = new map<int,float>();

Dies wird Ihnen helfen festzustellen, ob es beim Einsetzen in eine vorhandene Map gegen eine neue Karte ein paar Unterschied ist, oder wenn es sich in der Tat die Tatsache, dass screenline_usage eine Referenz auf die Leistung auswirkt. BTW, Vergessen Sie nicht, diese Haufen zugewiesenen Karten zu befreien, oder Sie werden mit einem Speicherverlust enden.

Answer 5

Referenzen sind meist hinter den Kulissen als Zeiger umgesetzt. Eine Ausnahme hiervon wäre, wenn ein vorübergehend sie zugewiesen wird, dann wird die Lebensdauer des Wertes auf die Lebensdauer der Referenz verlängert; im Wesentlichen ist die Referenz auf das Objekt. Also, es hängt davon ab, ob:

get_combined_screenline_usage

Rückgabe von Verweise oder Wert. Wenn es durch Referenz, die Referenz Art und Weise Macht schneller sein. Wenn es von Wert ist, dann ist die alte Art und Weise und neue Art und Weise im wesentlichen das gleiche tun, die Compiler unter der Annahme haben eine Rückgabewert-Optimierung.

In jedem Fall andere Optimierungen der Compiler tut (zB inlining) könnten die Auswirkungen der beiden Entscheidungen Maske; effektiv, ohne die genaue Linie Ihren langsamen Teil zu wissen, macht es sich hierbei um ein bisschen ein Ratespiel.

Ich würde vorschlagen, versuchen, feineres Korn Informationen zu erhalten, und es einzuengen genau auf die Linie, die so lange dauert, macht es viel einfacher zu optimieren.

(als Anmerkung:

map<int, float>::iterator it = my_screenline_usage.begin(); 
for (; it != my_screenline_usage.end(); ++it) 

könnte effizienter sein, wenn geschrieben als

for (map<int, float>::const_iterator it(my_screenline_usage.begin()), end(my_screenline_usage.begin()); it != end; ++it)

)

Answer 6

  

Das Problem ich versuche herauszufinden, warum die innere Schleife so viel länger dauert, zu bewerten, wenn die Karte ist eine Referenz?

Ich denke, dass das, was eine lange Zeit ist, nimmt der Anruf get_zone_screenline_usage: und dass der Grund, warum das eine lange Zeit ist, nehmen ist, dass das spezifische Element bereits existiert nicht in m_container und daher erstellt und eingefügt werden muss, bevor es sein kann, zurückgegeben.