std :: pair vs Struktur mit zwei int des

StackOverflow https://stackoverflow.com/questions/1606894

  •  05-07-2019
  •  | 
  •  

Frage

In einem ACM Beispiel, ich hatte einen großen Tisch für die dynamische Programmierung zu bauen. Ich hatte zwei ganze Zahlen in jeder Zelle zu 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 Zuweisung: 

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

Danach habe ich diesen Code geändert 

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

und die Zuordnung nahm 0 Sekunden.

Was erklärt diesen großen Unterschied in der Zeit?

War es hilfreich?

Lösung

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, um jedes Feld zu schreiben, das eine ganze Menge Speicher benötigt Zugriffe, die relativ zeitaufwendig sind. Mit struct Cell ist nichts stattdessen getan und nichts zu tun, ist ein bisschen schneller.

Andere Tipps

Die Antworten bisher nicht erklären, das volle Ausmaß des Problems.

Wie Sharptooth ausgeführt hat, initialisiert das Paar Lösung, um die Werte auf Null. Wie Lemurik wies darauf hin, ist das Paar Lösung nicht nur einen zusammenhängenden Block von Speicher initialisiert, sondern es wird das Paar Konstruktor für jedes Element in der Tabelle aufrufen. Doch das macht Konto auch nicht für sie 1,5 Sekunden unter. Etwas anderes geschieht.

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. 2E6 Paare zu konstruieren, so irgendwie jedes Paar Konstruktor nimmt 1000 Zyklen Du hast. Es braucht nicht mehr als 1000 Zyklen einen Konstruktor aufrufen, die nur zwei ganzen Zahlen auf Null setzt. Ich kann nicht sehen, wie Cache-Misses würde es so lange dauern machen. Ich würde es glauben, wenn die Zahl weniger als 100 Zyklen.

Ich dachte, es wäre interessant, wo sonst alle diese CPU-Zyklen sehen werden. Ich benutzen den crappiest ältesten C ++ Compiler, den ich finden konnte, um zu sehen, ob ich die Höhe der Verschwendung erforderlich erreichen könnte. Das Compiler war VC ++ v6. Im Debug-Modus, macht es etwas, das ich nicht verstehe. Es hat eine große Schleife, die das Paar Konstruktor für jedes Element in der Tabelle nennt - fair genug. Das Konstruktor setzt die beiden Werte auf Null - fair genug. Aber kurz bevor das zu tun, setzt er alle Bytes in einem 68-Byte-Bereich zu 0xcc. Diese Region ist kurz vor dem Start des großen Tisches. Er überschreibt dann das letzte Element dieser Region mit 0x28F61200. Jeder Aufruf des Paares Konstruktor wiederholt dies. Vermutlich ist dies eine Art der Buchhaltung durch den Compiler, damit sie weiß, welche Bereiche initialisiert werden, wenn für Zeigerfehler zur Laufzeit überprüft. Ich würde gerne wissen, was genau das ist für.

Wie auch immer, das würde erklären, wo die Verlängerung geht. Offensichtlich ein anderer Compiler kann nicht so schlimm sein. Und sicherlich ein optimierte Release-Build wäre nicht.

Meine Vermutung, es ist die Art und Weise std :: pair erstellt wird. Es ist mehr Aufwand ein Paar Konstruktor 1001x1001 Zeiten während Aufruf, als wenn Sie nur einen Speicherbereich zugewiesen werden.

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

Ich würde sagen, nur zufällig pausieren es innerhalb dieser 1,5 Sekunden , aber man müsste ziemlich schnell sein. Wenn Sie jede Dimension um einen Faktor von etwa 3 erhöht, man könnte es mehr wie 10+ Sekunden dauern, so wäre es einfacher, zu pausieren.

Oder könnten Sie es unter einem Debugger erhalten, brechen sie in dem Paar Konstruktorcode, und dann Schritt, um zu sehen, was es tut.

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

Es ist wirklich ein gutes Beispiel über eine C ++ und sorgfältig verwendet STL schreiben soll. irgendwelche Gedanken?

mein Projekt arbeitet an einem C & C ++ Code-Ebene Benchmark-Test-Tool, in dem wir eine Menge Codebeispiele machen würden herausgefunden, was „gut“ Code ist und was eine „schlechte“ Codierung Gewohnheit. finden Sie unter http://effodevel.googlecode.com erfahren Sie mehr über C9B.M. Planung. jemand, wenn Sie viele solcher Fälle erlebt hatte, benutzen Sie bitte das Projekt zu helfen, uns freundlich zu verbinden.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top