funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Velikost objektů v Javě

21. 1. 2013 (před 7 lety) — k47

Na root.cz mi dneska vyšel článek Ve­li­kost ob­jektů v Javě, kde se do­zvíte, jak Java alo­kuje paměť pro ob­jekty a pole, jak od­had­nout kolik paměti ta, která datová struk­tura po­tře­buje (a vět­ši­nou je to pře­kva­pivě hodně) a jak bo­jo­vat s re­pu­tací Javy jako pa­mě­ťově ne­na­žra­ného jazyka.

Dál plá­nuji pár dal­ších článků, kde budu přímo měřit spo­třebu paměti ně­kte­rých da­to­vých struk­tur a jejich im­ple­men­tací. Ale ty nej­spíš pu­b­li­kuji jenom tady.

Ve­li­kost ob­jektů v Javě

O Javě se říká, že je pa­mě­ťově příliš ná­ročná. Z části je to pravda, ale často jde jen o ne­še­trné pro­gramy, které ne­re­spek­tují jak Java alo­kuje paměť. V článku si uká­žeme jak spo­čí­tat ve­li­kost ob­jektů a polí. To ob­vykle stačí k tomu, abychom psali apli­kace, které si místo gi­ga­bajtů vy­stačí se stov­kami me­ga­bajtů.


Než můžeme začít mluvit o ve­li­kosti celých ob­jektů a polí, musíme vědět, kolik paměti za­bí­rají jed­not­livé pri­mi­tivní typy. To uka­zuje ná­sle­du­jící ta­bulka. Za po­všim­nutí stojí fakt, že bo­o­lean vy­ža­duje 1 bajt i když re­pre­zen­tuje jenom jeden bit in­for­mací. To stejné platí i o poli, kde si každý bool vyžádá celý jeden bajt1.

typve­li­kost
byte, bo­o­lean1 B
short, char2 B
int, float4 B
long, double8 B

Ob­jekty

Každý objekt (aspoň na Ope­n­JDK2) začíná hla­vič­kou, které ob­sa­huje ha­shCode iden­tity ob­jektu3, uka­za­tel na třídu ob­jektu a nějaké další pří­znaky. Na 32 bi­to­vých plat­for­mách (nebo 64 bi­to­vých s kom­pri­mo­va­nými poin­tery) je velká 12 bajtů a na 64 bi­to­vých plat­for­mách 16 bajtů. Za hla­vič­kou ná­sle­dují všechny atri­buty ob­jektu (fields, in­stanční pro­měnné). Jejich pořadí se řídí pěti pra­vi­dly:

  1. Každý objekt je za­rov­nán na ná­so­bek 8 bajtů.
  2. Atri­buty ob­jektů jsou řazeny podle ve­li­kosti: nejdřív long/double, pak int/float, char/shorts, byte/bo­o­lean a jako po­slední re­fe­rence na jiné ob­jekty. Atri­buty jsou vždy za­rov­nány na ná­so­bek vlastní ve­li­kosti.
  3. Atri­buty pa­t­řící různým třídám hi­e­rar­chie dě­dič­nosti se nikdy ne­mí­chají do­hro­mady. Atri­buty předka se v paměti na­chá­zejí před atri­buty po­tomků.
  4. První atri­but po­tomka musí být za­rov­nán na 4 bajty, takže za po­sled­ním atri­bu­tem předka může být až tří­baj­tová mezera.
  5. Pokud je první atri­but po­tomka long/double před kterým by za­rov­ná­ním vznikla čtyř­baj­tová mezera (předek není za­rov­nán na 8 bajtů, nebo ná­sle­dují po 12 baj­tové hla­vičce), long/double se může pře­su­nout tak, aby menší typy vy­pl­nily čtyř­baj­to­vou mezeru.

Atri­buty jsou za­rov­nány na ná­so­bek vlastní ve­li­kosti proto, že pro pro­ce­sor je ob­vykle rych­lejší načíst na­pří­klad 4 bajty paměti do čtyř­baj­to­vého re­gis­tru pokud se na­chází na adrese za­rov­nané právě na 4 bajty. Kdyby JVM za­cho­vá­valo pořadí atri­butů a zá­ro­veň je za­rov­ná­valo, ob­jekty by byly plné ne­vy­u­ži­tých děr. Tím, že atri­buty seřadí od nej­vět­ších (long/double) po nejmenší (byte/bool) do­sáhne mi­ni­mální ve­li­kosti ob­jektu, ve kterém jsou všechny atri­buty při­ro­zeně za­rov­nány.

Uká­žeme si ně­ko­lik pří­kladů, jak vypadá paměť alo­ko­vaná hy­po­te­tic­kými ob­jekty (všechny pří­klady uva­žují 64bitové JVM s kom­pri­mo­va­nými poin­tery):

class X { byte b; int i; long l; }
| header                | int   | long          |b|xxxxxxxxxxxxxxxxxxx|
| 12B                   | 4B    | 8B            |1| 7B padding        |
|-----------------------|-------|---------------|-|-------------------|
class Parent               { int pi; short ps; }
class Child extends Parent { int ci; short cs; }
| header                | pi    |ps |xxx| ci    |cs |xxx|
| 12B                   | 4B    |2B |2B | 4B    |2B |2B |
|-----------------------|-------|---|---|-------|---|---|
class Parent               { int i; short s; byte b; }
class Child extends Parent { long l; int ii; }
| header                | i     |s  |b|x| int   | long          |
| 12B                   | 4B    |2B |1|1| 4B    | 8B            |
|-----------------------|-------|---|-|-|-------|---------------|
class Cons { Object head; Object tail; }
| header                | head  | tail  |xxxxxxx|
| 12B                   | 4B    | 4B    | 4B    |
|-----------------------|-------|-------|-------|

Pole

Pole jsou na tom po­dobně jako ob­jekty, ale jejich hla­vička ob­sa­huje navíc jeden čtyř­baj­tový in­te­ger udá­va­jící délku pole. Pak ná­sle­duje sa­motný obsah pole, zase za­rov­nán na ná­so­bek 8 bajtů.

Pokud pole ob­sa­huje os­mi­baj­tové pri­mi­tivní typy (long nebo double), hod­noty stále musí být za­rov­nány na 8 bajtů, takže na 64bit plat­for­mách je za hla­vič­kou čtyř­baj­tová mezera a teprve po ní ná­sle­dují data.

new byte[] { 0, 0 }
| header                |length |b|b|xxxxxxxxxxx|
| 12B                   | 4B    |1|1|6B         |
|-----------------------|-------|-|-|-----------|
new long[] {0}
| header                |length | long          |
| 12B                   | 4B    | 8B            |
|-----------------------|-------|---------------|

Si­tu­ace se dá shr­nout do ně­ko­lika vzorců:

32 bitové plat­formy

Ob­jekty
12B hla­vičky + ve­li­kost atri­butů předků za­rov­na­ných na 4 bajty + součet ve­li­kostí všech typů za­rov­naný nahoru na 8B
Pole typů byte, bool, short, char, int, float, long, double
16B hla­vičky + length * ve­li­kost typu to celé za­rov­nané nahoru na 8 bajtů
Pole re­fe­rencí
16B hla­vičky + length * 4B to celé za­rov­nané nahoru na 8 bajtů

64 bitové plat­formy

Ob­jekty
16B hla­vičky + ve­li­kost atri­butů předků za­rov­na­ných na 4 bajty + součet ve­li­kostí všech typů za­rov­naný nahoru na 8B
Pole typů byte, bool, short, char, int, float
20B hla­vičky + length * ve­li­kost typu to celé za­rov­nané nahoru na 8 bajtů
Pole typů long, double nebo re­fe­rencí
20B hla­vičky + 4B pad­ding + length * 8B

Pří­klady

Na­ko­nec si uká­žeme ně­ko­lik pří­kladů uka­zu­jí­cích, kolik paměti spo­tře­bují ně­které běžně po­u­ží­vané typy.

String

Ře­tě­zec je re­pre­zen­to­ván jako objekt, který od­ka­zuje na vnitřní pole znaků.

Sa­motný objekt String má: 12B hla­vi­ček, 4B ha­shcode, 4B délka stringu, 4B offset, 4B re­fe­rence a 4B pad­ding.

Vnitřní pole má: 12B hla­vičky, 4B délku pole + (počet znaků) * 2B

Strin­gová část zabírá 32 bajtů, vnitřní pole má režii 16 bajtů + 0 až 6 bajtů, které se ztratí za­rov­ná­ním pole. Do­hro­mady to dělá 48 – 52 extra bajtů na jeden String nebo 62 – 68 bajtů pro 64 bitové plat­formy.

(pozn: V nej­no­vější verzi Javy se změ­nila im­ple­men­tace ře­tězců a už ne­ob­sa­hují atri­buty pro délku a offset. Režie je tedy o 8 bajtů menší).

List

Ne­měnný spo­jový seznam (jaký se po­u­žívá ve Scale) je slo­žený z řetězu Cons buněk ukon­če­ných buňkou Nil. Nil má jenom jednu in­stanci v celém vir­tu­ál­ním stroji a tak se jí ne­mu­síme za­bý­vat. Cons ob­sa­huje dva atri­buty: vlastní hod­notu head a re­fe­renci tail na ná­sle­du­jící buňku v řadě. Pro­tože je List ge­ne­rický a JVM pro­vádí type era­sure, head je vždy re­fe­rence. Pokud od­ka­zuje na pri­mi­tivní typ, ten je au­to­bo­xin­gem za­ba­len do ob­jektu.

Cons tedy zabírá: 12B hla­vičky, 2 re­fe­rence po 4B a 4B, které padly na oltář za­rov­nání paměti, tedy 24 bajtů na jednu Cons buňku (32 na 64 bi­to­vých plat­for­mách). To je celkem při­ja­telná daň za to, že můžeme v kon­stant­ním čase číst a ma­ni­pu­lo­vat za­čá­tek se­znamu.

Ale teď si před­stavme, že v této datové struk­tuře budeme chtít uklá­dat celá čísla a ty musejí projít au­to­bo­xin­gem.

Objekt Integer má: 12B hla­vi­ček a 4B dat, což před­sta­vuje dal­ších 12 extra bajtů režie. Do­hro­mady tedy po­tře­bu­jeme 40 bajtů (nebo 56 bajtů na 64 bi­to­vých plat­for­mách), abychom mohli uložit 4 bajty dat do spo­jo­vého se­znamu. Na­proti tomu pole pri­mi­tiv­ních in­te­gerů má pouze kon­stantní režii 16B, která je velice rychle amor­ti­zo­vána. V ta­ko­vých pří­pa­dech stojí za to zvážit, jestli nebude vhod­nější použít ně­ja­kou kom­pakt­nější da­to­vou struk­turu jako třeba pole, Vector ze Scaly nebo pro ex­trémní pří­pady zvolit spe­ci­a­li­zo­vané ko­lekce jako Trove nebo Colt.

Ha­shMap

Exis­tuje mnoho způ­sobů, jak im­ple­men­to­vat ha­shmapu, ale my budeme uva­žo­vat způsob, jak je im­ple­men­to­vána ve stan­dardní knihovně Javy – tedy polem, které uka­zuje na spo­jový seznam (tzv. closed ad­d­res­sing):

class Map<K, V> {
  Entry<K, V>[] buckets;
}
class Entry<K, V> {
  Bucket<K, V> next;
  K key;
  V value;
}

Po­tře­bu­jeme pole re­fe­rencí, které je velké při­bližně jako počet ele­mentů v mapě. Každá re­fe­rence, která ob­sa­huje ně­ja­kou hod­notu, vede na Entry, která má tři re­fe­rence: další Entry v řadě, klíč mapy a hod­notu.

Entry má 12B hla­vičky + 12B re­fe­rence. Do­hro­mady to dává 24B (nebo 40B na 64 bi­to­vých plat­for­mách) + 4B re­fe­rence na jeden pár klíč/hod­nota v poli a to ne­po­čí­táme data, která za­be­rou sa­motné ob­jekty klíčů a hodnot a pří­padné pa­mě­ťové ná­klady spo­jené s au­to­bo­xin­gem.


Odkazy:

Pozn:

  1. Pokud chceme kom­paktní pole, můžeme použít BitSet nebo BitMap
  2. Jed­not­livé vir­tu­ální stroje se od sebe mohou lišit tím, jak v paměti re­pre­zen­tují ob­jekty.
  3. Vrací ho stan­dardní im­ple­men­tace metody ha­shCode, nebo se k němu můžeme dostat vo­lá­ním java.lang.System.iden­ti­ty­Ha­shCode
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články