std :: pair <int, int> vs struct mit zwei int

Question

In einem ACM-Beispiel musste ich einen großen Tisch für die dynamische Programmierung erstellen. Ich musste zwei ganze Zahlen in jeder Zelle speichern, also entschied ich mich für eine std::pair<int, int> zu gehen. Um jedoch eine riesige Auswahl von ihnen nahm 1,5 Sekunden Zuteilen:

std::pair<int, int> table[1001][1001]; 

Danach habe ich diesen Code zu

geändert

struct Cell { 
    int first; 
    int second; 
} 

Cell table[1001][1001]; 

und die Zuordnung nahm 0 Sekunden.

Was erklärt diesen enormen Unterschied in der Zeit?

Answer 1

std::pair<int, int>::pair() Konstruktor initialisiert die Felder mit Standardwerten (Null bei int) und Ihr struct Cell nicht (da Sie nur eine automatisch generierte Standard-Konstruktor haben, der nichts tut).

Initialisierung erfordert Schreiben in jedes Feld, das eine ganze Menge Speicherzugriffe erfordert, die relativ zeitaufwendig sind. Mit struct Cell wird nichts getan und nichts ist ein bisschen schneller.

Answer 2

Meine Vermutung ist die Art, wie std :: pair erstellt wird. Es gibt mehr Overhead beim Aufrufen eines Paarkonstruktors 1001x1001 Mal als wenn Sie nur einen Speicherbereich zuweisen.

Answer 3

es ist wirklich ein gutes Beispiel darüber sollte man C++ schreiben und STL vorsichtig verwenden. irgendwelche Gedanken?

mein Projekt arbeitet an einem C++ - Code-Level-Benchmark-Test-Tool, in dem wir viele Codebeispiele erstellen, um herauszufinden, was "guter" Code ist und was eine "schlechte" Codierungsgewohnheit ist. siehe http://effodevel.googlecode.com, um mehr über C9B.M zu erfahren. Planung. jemand, wenn Sie viele solcher Fälle erlebt haben, bitte bitte das Projekt, um uns zu helfen.

Answer 4

Die Antworten erklären bisher nicht die volle Größe des Problems.

Wie spitztooth darauf hingewiesen hat, initialisiert die Paarlösung die Werte auf Null. Wie Lemurik darauf hingewiesen hat, initialisiert die Paarlösung nicht nur einen zusammenhängenden Speicherblock, sondern ruft den Paarkonstruktor für jedes Element in der Tabelle auf. Aber selbst das ist nicht dafür verantwortlich, dass es 1,5 Sekunden dauert. Etwas anderes passiert.

Hier ist meine Logik:

Angenommen, Sie auf einer alten Maschine waren, sagen wir bei 1,33 GHz läuft, dann 1,5 Sekunden ist 2E9 Taktzyklen. Sie haben 2e6 Paare zu konstruieren, also nimmt jeder Paarkonstruktor irgendwie 1000 Zyklen. Es dauert nicht 1000 Zyklen, um einen Konstruktor aufzurufen, der nur zwei ganze Zahlen auf Null setzt. Ich kann nicht sehen, wie Cache-Misses es so lange dauern würde. Ich würde es glauben, wenn die Anzahl weniger als 100 Zyklen wäre.

Ich dachte, es wäre interessant zu sehen, wo sonst alle diese CPU-Zyklen gehen. Ich benutzte den ältesten C++ - Compiler, den ich finden konnte, um zu sehen, ob ich die benötigte Verschwendung erreichen konnte. Dieser Compiler war VC++ v6. Im Debug-Modus macht es etwas, was ich nicht verstehe. Es hat eine große Schleife, die den Paarkonstruktor für jedes Element in der Tabelle aufruft - fair genug. Dieser Konstruktor setzt die beiden Werte auf Null - also gut genug. Aber bevor das getan wird, setzt es alle Bytes in einem 68-Byte-Bereich auf 0xcc. Diese Region ist kurz vor dem Beginn des großen Tischs. Dann überschreibt es das letzte Element dieser Region mit 0x28F61200. Jeder Aufruf des Paarkonstruktors wiederholt dies.Vermutlich ist dies eine Art Buchführung durch den Compiler, so dass er weiß, welche Bereiche initialisiert werden, wenn zur Laufzeit auf Zeigerfehler geprüft wird. Ich würde gerne genau wissen, wofür das ist.

Wie auch immer, das würde erklären, wo die zusätzliche Zeit läuft. Offensichtlich ist ein anderer Compiler möglicherweise nicht so schlecht. Und sicherlich wäre ein optimierter Release-Build nicht möglich.

Answer 5

Das sind alles sehr gute Vermutungen, aber wie jeder weiß, sind Vermutungen nicht zuverlässig.

Ich würde sagen, nur zufällig pause it innerhalb dieser 1,5 Sekunden, aber Sie müssten ziemlich schnell sein. Wenn Sie jede Dimension um einen Faktor von etwa 3 erhöhen, können Sie mehr als 10 Sekunden benötigen, um das Pausieren zu erleichtern.

Oder Sie könnten es unter einem Debugger bekommen, brechen Sie es in der Paar-Konstruktor-Code und dann Einzelschritt, um zu sehen, was es tut.

So oder so, Sie würden eine feste Antwort auf die Frage bekommen, nicht nur eine Vermutung.