Java: tablica Wielowymiarowa vs jednowymiarowa

Na obecnych procesorach dostęp do pamięci niebuforowanej jest setki razy wolniejszy od arytmetyki (zobacz tę prezentację i przeczytaj to, co każdy programista powinien wiedzieć o pamięci). Opcja a) spowoduje około 3 wyszukiwanie pamięci, podczas gdy opcja b) spowoduje około 1 wyszukiwanie pamięci. Również algorytmy wstępnego ustawiania procesora mogą nie działać. Tak więc opcja b) może być szybsza w niektórych sytuacjach(jest to hot spot i tablica nie mieści się w pamięci podręcznej procesora). Ile szybciej? - to zależy od aplikacji.

Osobiście najpierw użyłbym opcji a), ponieważ spowoduje to prostszy kod. Jeśli profiler pokazuje, że dostęp do tablicy jest wąskim gardłem, to przekonwertowałbym go do opcji b), tak że istnieje para metod pomocniczych do odczytu i zapisu wartości tablicy (w ten sposób niechlujny kod będzie ograniczony do tych dwóch metod).

Zrobiłem benchmark do porównywania 3-wymiarowych tablic int (Kolumna "Multi") do odpowiednika 1-wymiarowe tablice int (Kolumna" pojedyncza"). Kod jest tutaj i testy tutaj. Uruchomiłem go na 64-bitowym jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3.0 GHz, 4 GB DDR2, używając opcji JVM -server -Xmx3G -verbose:gc -XX:+PrintCompilation (usunąłem wyjście debugowania z poniższych wyników). Wyniki były następujące:

Out of 20 repeats, the minimum time in milliseconds is reported.

Array dimensions: 100x100x100 (1000000)
            Multi   Single
Seq Write   1       1
Seq Read    1       1
Random Read 99      90    (of which generating random numbers 59 ms)

Array dimensions: 200x200x200 (8000000)
            Multi   Single
Seq Write   14      13
Seq Read    11      8
Random Read 1482    1239    (of which generating random numbers 474 ms)

Array dimensions: 300x300x300 (27000000)
            Multi   Single
Seq Write   53      46
Seq Read    34      24
Random Read 5915    4418    (of which generating random numbers 1557 ms)

Array dimensions: 400x400x400 (64000000)
            Multi   Single
Seq Write   123     111
Seq Read    71      55
Random Read 16326   11144    (of which generating random numbers 3693 ms)

To pokazuje, że tablica 1-wymiarowa jest szybsza. Chociaż różnice są tak małe, że dla 99% aplikacji nie będzie to zauważalne.

Zrobiłem też kilka pomiarów, aby oszacować narzut generowania liczb losowych w Random Read benchmark przez zastąpienie preventOptimizingAway += array.get(x, y, z); przez preventOptimizingAway += x * y * z; i dodanie pomiarów do powyższej tabeli wyników ręcznie. Generowanie liczb losowych zajmuje 1/3 lub mniej całkowitego czasu badania losowego odczytu, więc dostęp do pamięci dominuje w badaniu zgodnie z oczekiwaniami. Interesujące byłoby powtórzenie tego wzorca z tablicami o wymiarach 4 i więcej. Prawdopodobnie zwiększyłoby to różnicę prędkości, ponieważ wielowymiarowa tablica jest najwyższe poziomy będą pasowały do pamięci podręcznej procesora, a tylko pozostałe poziomy będą wymagały wyszukiwania pamięci.

Użyj pierwszego wariantu (3-wymiarowego), ponieważ jest łatwiejszy do zrozumienia i jest mniej szans na popełnienie błędu logicznego (zwłaszcza jeśli używasz go do modelowania przestrzeni 3-wymiarowej)

Jeśli wybierzesz tę ostatnią trasę, będziesz musiał wykonać arytmetykę dla każdego dostępu do tablicy. To będzie podatne na ból i błędy (chyba, że owiniesz go w klasie zapewniającej tę funkcjonalność).

Nie wierzę, że jest jakaś (znacząca) optymalizacja w wyborze tablicy płaskiej (zwłaszcza biorąc pod uwagę arytmetykę wziętą do indeksu). Jak zawsze w przypadku optymalizacji, musisz wykonać kilka pomiarów i określić, czy naprawdę warto.