Czy porządek w deklaracji wielowymiarowej macierzy ma wpływ na zużytą pamięć?

Question

Ile bajtów zostanie przydzielonych na a i b?

import android.graphics.Bitmap; 

Bitmap[][][] a = new Bitmap[1000][2][2]; 
Bitmap[][][] b = new Bitmap[2][2][1000]; 

Zauważ, że pytam tylko o pamięć zajmowaną przez czyste tablice, żadnych obiektów w środku.

_{Dlaczego pytam? Ponieważ piszę grę na Androida. Dla mnie kolejność nie ma znaczenia, ale jeśli jest różnica w pamięci, dobrze będzie ją zapisać.}

Answer 1

Tak, to robi różnicę.

W języku Java tablica 2D jest tablicą tablic 1D, a tablice (podobnie jak wszystkie obiekty) mają dodatkowo nagłówki oprócz przestrzeni potrzebnej do przechowywania samych elementów.

Należy więc rozważyć int[10][2] w porównaniu do int[2][10] i przyjąć 32-bitową maszynę JVM.

• int[2][10] składa się z jednej tablicy złożonej z 2 elementów i 2 tablic składających się z 10 elementów. Łącznie - 3 obiekty tablicowe + 22 elementy.
• int[10][2] składa się z jednej tablicy złożonej z 10 elementów i 10 tablic złożonych z 2 elementów. Łącznie - 11 obiektów tablicowych + 30 elementów.

Jeśli założymy, że rozmiar nagłówka jest 3 32bit słowa (typowe dla JVM 32bit) i odniesienia jest 1 32bit słowo, następnie

• int[2][10] trwa 3 * 3 + 22 * 1 = 31 słowa = 124 bajtów
• int[10][2] trwa 11 * 3 + 30 * 1 = 63 słowa = 252 bajtów

Stosuje się taką samą logiką można oszacować wielkość matryc o większej liczbie wymiarów.

Jest jednak oczywiste, że zużywa się mniej miejsca, jeśli największy wymiar jest najodpowiedniejszy.

---

_{Zrobiłem matematyki z int tablicach, lecz na komputerze 32-bitowym int i reference zajmują tę samą liczbę bajtów. Na komputerze 64-bitowym odniesienie może mieć taki sam rozmiar, jak int lub long, w zależności od opcji maszyny JVM. Rozmiary nagłówków mogą być różne ... nie do końca jasne ... potencjalnie zależne od platformy.}

_{Ja nie wyliczyłem przestrzeni wymaganej do przechowywania samych obiektów Bitmap, ale to jest tak samo, jak organizujesz tablice.}

Answer 2

Brak różnicy w pamięci, ale kolejność indeksów macierzy może - teoretycznie - mieć wpływ na szybkość programu.

Zazwyczaj przetwarza się wielowymiarową zawartość tablicy w zagnieżdżonych pętlach. Zatem twoja tablica powinna być zorganizowana w taki sposób, aby adresować sąsiednie elementy w wewnętrznej pętli, aby umożliwić kompilatorowi stworzenie najbardziej wydajnego kodu. Nie wiem, jak Java organizuje pamięć, ale myślę, że nie różni się od C/C++:

int a[10][100]; 
for (i = 0; i < 10; ++i) { 
    for (j = 0; j < 100; ++j) { 
     do_something_with(a[i][j]); 
    } 
} 

Answer 3

Gdy próbuje go na hotspot (dokładne dane liczbowe mogą różnić się od tych, które można dostać na Dalvik, ale wnioski powinny być podobny), otrzymuję następujące wyniki:

tablicę Object (1000x2x2): 76034 bajtów
tablicy Object (2x2x1000): 16137 bajtów

jest to zgodne z przybliżonych obliczeń:

[2][2][1000]      
Array #  Header Size Memory Number Total 
1    16  2  24  1  24 
2    16  2  24  2  48 
3    16 1000 4016  4 16,064 

         Grand Total  16,136 


[1000][2][2]      
Array #  Header Size Memory Number Total 
1    16 1000 4016  1 4,016 
2    16  2  24 1000 24,000 
3    16  2  24 2000 48,000 

         Grand Total  76,016 

---

kod testowy poniżej, należy uruchomić z -XX:-UseTLAB, aby uzyskać bardziej dokładne wyniki.

public class TestMemory { 

    private static final int SIZE = 100; 
    private static Runnable r; 
    private static Object o; 

    private static void test(Runnable r, String name, int numberOfObjects) { 
     long mem = Runtime.getRuntime().freeMemory(); 
     r.run(); 
     System.out.println(name + ": " + (mem - Runtime.getRuntime().freeMemory())/numberOfObjects + " bytes"); 
    } 

    public static void main(String[] args) throws Exception { 
     r = new Runnable() { public void run() { for (int i = 0; i < SIZE; i++) o = new Object[1000][2][2];} }; 
     test(r, "Object array (1000x2x2)", SIZE); 

     r = new Runnable() { public void run() { for (int i = 0; i < SIZE; i++) o = new Object[2][2][1000];} }; 
     test(r, "Object array (2x2x1000)", SIZE); 
    } 
} 

Answer 4

Tak, to robi różnicę. Po prostu spróbuj to z -Xmx8M:

// throws OutOfMemoryError 
public static void main(String[] args) { 
    int[][] a = new int[500000][2]; 
    System.out.println("a.length: '" + (a.length) + "'"); 
} 

// works 
public static void main(String[] args) { 
    int[][] a = new int[2][500000]; 
    System.out.println("a.length: '" + (a.length) + "'"); 
} 

pierwsza rzuci OutOfMemoryError, drugi minie.

Powodem jest to, że pierwsza wersja tworzy 500 000 tablic o długości 2, a druga tworzy 2 tablice o długości 500 000.

Reference:

W języku takim jak C, macierz dwuwymiarowe (lub też w jakiejkolwiek wielowymiarową macierz) jest zasadniczo jednowymiarową tablicę z rozsądne manipulowanie kursorem. Tak nie jest w przypadku Javy, gdzie tablica wielowymiarowa jest w rzeczywistości zbiorem zagnieżdżonych tablic. Oznacza to, że każdy wiersz dwuwymiarowej tablicy ma narzut obiektu, ponieważ w rzeczywistości jest oddzielnym obiektem!