Die Tatsache, dass das trotzdem noch doppelt so schnell ist wie der Quadtree, demonstriert schön, wie wichtig Cache Utilization heutzutage ist, die beim Quadtree natürlich völlig im Eimer ist...
Das musst du jetzt aber mal erklären, warum bei einem Grid der Cache besser genutzt werden können soll.
Ich könnte das nachvollziehen, wenn man das Grid Zelle für Zelle durchlaufen würde, aber das ist ja wie schon gesagt Schwachsinn.
Also durchläuft man Partikel für Partikel. Partikel N kann räumlich total weit weg von Partikel N+1 liegen, wo bringt mir da der Cache etwas?
Selbst die Partikel, die in der selben Zelle sind, befinden sich im Speicher "verstreut" - schließlich speichert ja jeder Partikel nur einen Zeiger auf seine Zelle, und nicht die Zelle "enthält" die Partikel.
Beachte außerdem, dass er die Nachbarschafts-Suche noch gar nicht eingebaut hat.
(wenn er das hätte, dann gäbe es dort sicherlich einen Vorteil beim Grid, eben wegen des Caches)