verlinkte Listen, Arrays und Hardware-Speicher-Caches

Question

Während Fragen haben, bevor über verkettete Listen gegenüber Arrays gefragt, die Antworten meist einkochen zu dem, was die meisten von uns haben wahrscheinlich schon irgendwann gelernt:

• Listen sind gut Einsetzen und
• Arrays sind gut random access

Jetzt anständig Leute wie Bjarne Stroustrup argued haben zu löschen, die Arrays praktisch immer verkettete Listen übertreffen, weil sie viele bessere Nutzung des cachin machen g Architektur implementiert in moderner Hardware. Er stellt außerdem fest, dass der Leistungsvorteil von Arrays mit ihrer Größe zunimmt.

Während ich im Grunde seine Argumente verstehe und stimme ihm zu, frage ich mich, ob dies immer noch wahr ist, wenn die Größe des Arrays deutlich größer als die Größe des Caches ist. Ich würde sagen, dass dies der Fall ist, wenn Leistung wirklich zählt.

Zusammenfassend: Sind Arrays in den meisten Fällen immer noch besser als Listen, auch wenn ihre Größe viel größer ist als die Cache-Größe und ein großer Prozentsatz der Operationen Einfügungen oder Löschungen sind? Wenn ja, wie kann das erklärt werden?

Answer 1

Arrays funktionieren nicht nur wegen des Caching, sondern auch wegen des Prefetching.

Caching hat 2 Hauptvorteile - sequenzielle Elemente können sich in derselben Zeile befinden. Sie können also einmal abrufen und die gesamte Zeile mehrmals verwenden (während in einer verknüpften Liste Ihr nächstes Element an anderer Stelle liegt)). Dieser Vorteil wird verringert, je größer die Elemente werden, und ist verschwunden, sobald Ihr Element eine Liniengröße überschreitet.

Der zweite Vorteil ist subtiler - Sie erhalten eine bessere Ausnutzung des Caches, da er in einer Weise organisiert ist, die der sequentiellen Zuweisung zugute kommt. Dies bedeutet, dass ein Array bis zur Cachegröße immer noch passen kann, während eine zufällig zugewiesene Liste einige Kollisionen aufweisen kann, die zu einem Thrashing führen würden, selbst wenn die Listengröße kleiner als der Cache ist.

Abgesehen vom Caching ist der Vorteil von räumlich zugewiesenen Strukturen jedoch der Prefetch. Die meisten CPUs würden automatisch die nächsten Zeilen in einem Strom von Zugriffen, wie z. B. einen Array-Zugriff, vorausholen und würden daher alle Fehler in einem Szenario eines sequentiellen Zugriffs eliminieren. Auf der anderen Seite sind all diese Vorteile nur Optimierungen, so dass sie die Leistung nur linear beschleunigen können, aber niemals einen asymptotischen Komplexitätsunterschied wie die O (1) -Einfügung, die die Liste bietet, mildern können. Schließlich müssen Sie Ihren Code benchmarken, um zu sehen, ob solche Fälle erforderlich sind und einen Engpass verursachen - wenn dies der Fall ist, ist möglicherweise ein hybrider Ansatz erforderlich.