Warum verarbeitet Javascript ein Array von Strukturen schneller als eine Struktur von Arrays?

9

Ich habe nach einer effizienten Möglichkeit gesucht, große Listen von Vektoren in Javascript zu verarbeiten. Ich habe eine Performance-Suite erstellt Tests , die eine skalare Vektormultiplikation unter Verwendung verschiedener Datenstrukturen durchführen:

AoS-Implementierung:

%Vor%

SoA-Implementierung:

%Vor%

Die AoS-Implementierung ist mindestens 5-mal schneller. Das hat mich überrascht. Die AoS-Implementierung verwendet eine weitere Indexsuche pro Iteration als die SoA-Implementierung, und die Engine muss ohne einen garantierten Datentyp arbeiten.

Warum passiert das? Liegt das an der Browser-Optimierung? Cache-Fehler?

Nebenbei bemerkt, SoA ist immer noch etwas effizienter bei der Ausführung von Ergänzung über eine Liste von Vektoren :

AoS:

%Vor%

SoA:

%Vor%

Gibt es eine Möglichkeit, dass ich weiß, wann eine Operation für eine gegebene Datenstruktur mehr / weniger effizient sein wird?

BEARBEITEN: Ich habe es versäumt, die SoA-Implementierung hervorzuheben, die von typisierten Arrays verwendet wurde, weshalb dieses Leistungsverhalten mir merkwürdig vorkam. Trotz der Gewährleistung des Datentyps, der von typisierten Arrays bereitgestellt wird, ist das Plain-Old-Array von assoziativen Arrays schneller. Ich habe noch ein Duplikat dieser Frage zu sehen.

EDIT2: Ich habe festgestellt, dass das Verhalten nicht mehr auftritt, wenn die Deklaration für vector in den Vorbereitungscode verschoben wird. AoS ist scheinbar schneller, wenn vector direkt neben der for -Schleife deklariert wird. Das macht für mich wenig Sinn, zumal der Motor ihn sowieso nur an der Spitze des Scope verankern sollte. Ich werde das nicht weiter hinterfragen, da ich ein Problem mit dem Test-Framework vermute.

EDIT3: Ich habe eine Antwort von den Entwicklern der Testplattform erhalten, und sie haben den Leistungsunterschied bestätigt aufgrund der äußeren Umfangssuche. SoA ist immer noch der effizienteste, wie erwartet.

    
16807 30.09.2016, 20:49
quelle

1 Antwort

2

Die Struktur der Tests, die für das Benchmarking verwendet werden, scheint sich überlagert zu haben, was zu undefiniertem oder unerwünschtem Verhalten führte. Ein sauberer Test ( Ссылка ) zeigt wenig Unterschied zwischen den beiden und hat SOA Ausführung leicht (30%) schneller.

Nichts davon ist jedoch in Bezug auf die Leistung von untergeordneter Bedeutung. Dies ist eine Anstrengung in der Mikrooptimierung. Was Sie im Wesentlichen vergleichen, ist O (n) zu O (n) mit Nuance beteiligt. Der kleine prozentuale Unterschied wird insgesamt keinen Effekt haben, da O (n) als eine akzeptable Zeitkomplexität angesehen wird.

    
Travis J 30.09.2016, 21:54
quelle

Tags und Links