O žroutech paměti, Mexičanech a Japoncích

8.12.2007 01:10 | Přečteno: 1159× | Ani zbla | poslední úprava: 8.12.2007 01:11

V tomto postu Miguel de Icaza porovnává paměťovou náročnost uložení pole čísel. Ukazuje to na příkladu pole pro 8 milionů integerů (tedy 32 MiB dat).

Pokud se v Monu int uloží do obecného pole objektů, tedy:

object [] e = new object [size];

for (int i = 0; i < size; i++)
    e [i] = 1;

Pak konstrukce sežere 178 MiB, což je hodně. Jedná se v podstatě o pole referencí na objekty a každý objekt má třeba ještě svůj mutex. Tedy režie je nezanedbatelná.

Pokud se použije generická konstrukce, tedy:

public class D<T> {
    public T [] t;
			
    public D (int size)
    {
        t = new T [size];
    }
}

D<int> d = new> (size);
for (int i = 0; i < size; i++)
    d.t [i] = 1;

Pak to podle něj sežere jenom 38 MiB, což je slušné. Zkoušel ještě Javu 6, ta mu zabrala také "slušných" 248 MiB.

Můj přínos k téhle věci

Napadlo mě podrobit tomuto testu Python a Ruby. Nejprve jsem zkusil "implementovat" jeho příklad v Javě, abych se ujistil, že měřím to samé, co on. Můj kód vypadá takto:

public class M
{
	public static void main(String[] args) throws Exception
	{
		int n = 8*1024*1024;
		Object [] x = new Object [n];

	      for (int i = 0; i < n; i++)
                     x [i] = new Integer(i);
                     
		int c = System.in.read();
		System.out.println(x.length);
	}
}

Měřil jsem tak, že jsem pustil htop a koukal se na sloupec RES. Vykoukal jsem 181 MiB. No dobrá, je to řádově stejné. Tak co náš Python?

n = 8*1024*1024
x = range(n)
q = raw_input()
print len(x)

Tento program zabral 131 MiB, což je IMO docela slušné. Přece jenom int je v Pythonu objekt se vším všudy. Dech mi ale vyrazilo Ruby:

x = []
n = 8*1024**2
for i in 0..n do
	x << i
end
$stdin.getc
print x.size

Tento skript zabral pouhých (a naprosto neuvěřitelných) 34 MiB! To jsem opravdu nečekal. Asi je to díky jednomu triku, který Matz používá: integery skladuje přímo (žádné reference) s tím, že nejnižší bit určuje, jestli se jedná o číslo, nebo o referenci. Pak jsou integery jen 31 bitové, ale což. Navíc lze využít toho, že pointery bývají zarovnané (tedy sudé).

       

Obrázky

Komentáře

[Luboš Doležel (Doli)]

Když už je Ruby takto zvýhodněno, je vhodné dodat, že v Javě to spotřebuje 43,5 MB, pokud je to alokováno jako obyčejný int. To není tak zlé.

[alblaho]

Já bych neřekl, že Ruby bylo zvýhodněno. Prostě je tam šikovná optimalizace, který nikde jinde není.

[Luboš Doležel (Doli)]

To sice je, ale takhle to ztrácí trochu smysl porovnávat, protože taková konkrétní situace nebude moc častá.

[podlesh]

Já bych neřekl, že Ruby bylo zvýhodněno. Prostě je tam šikovná optimalizace, který nikde jinde není.

LISP pro jistotu z diskuse vynecháme úplně. Koho by zajímala prehistorie, že?

Pro hnidopichy: trou prehistorií myslím to, že tato technika v lispu již dávno vyšla z módy (alespoň pokud jsem dobře informován).

[Kyosuke]

Spíš špatně informován... (link) Aneb když něco funguje, proč to měnit?

[podlesh]

No, viz ta diskuse která se tu rozjela A kterou jsem již jednou viděl, před deseti lety...

[Kyosuke]

Ta optimalizace je ve všech Lispech od konce šedesátých let... A hádej, odkud ji Matz vzal.

[Martin Tůma]

Ta optimalizace je ve všech Lispech od konce šedesátých let...

Něco, co znemožňuje nad datovým typem integer efektivně provádět aritmetické operace, bych optimalizací rozhodně nenazýval...

[Kyosuke]

Znemožňuje efektivně provádět? A na to jsi přišel jak?

[Martin Tůma]

Na vlastní oči jsem viděl věci, které jsou vyznavačům Lispu zapovězené...

Jak si představuješ, že při aritmeticko-logickejch operacích zachováš bez dodatečný režie spodní bity tak, aby pro lisp měl výsledek stále stejnej typ? Jak bez dodatečný režie použiješ instrukce porovnání (které jsou závislé na příznacích, které jsou závislé na výsledcích aritmetických operací...)?! Instrukce prakticky všech CPU jsou zkrátka navržený (a tudíž optimální) na to, že integer má n (8, 16, 32, ...) bitů, ne n-3...

[Kyosuke]

; SLIME 2007-11-23
CL-USER> (declaim (optimize (speed 3) (safety 0) (debug 0)))
; No value
CL-USER> (defun sel (x y z)
	   (declare (type fixnum x y z))
	   (the fixnum (if (< x 42)
			   (+ y z)
			   (* y z))))
SEL
CL-USER> (disassemble #'sel)
; 03689D6F:       4881FA50010000   CMP RDX, 336               ; no-arg-parsing entry point
;       76:       7C17             JL L1
;       78:       488BD7           MOV RDX, RDI
;       7B:       48C1FA03         SAR RDX, 3
;       7F:       480FAFD6         IMUL RDX, RSI
;       83: L0:   488D65F0         LEA RSP, [RBP-16]
;       87:       F8               CLC
;       88:       488B6DF8         MOV RBP, [RBP-8]
;       8C:       C20800           RET 8
;       8F: L1:   488D1437         LEA RDX, [RDI+RSI]
;       93:       EBEE             JMP L0
;       95:       90               NOP
;       96:       90               NOP
;       97:       90               NOP
;       98:       90               NOP
;       99:       90               NOP
;       9A:       90               NOP
;       9B:       90               NOP
;       9C:       90               NOP
;       9D:       90               NOP
;       9E:       90               NOP
;       9F:       90               NOP
; 
NIL
CL-USER> 

Já nevím. Lispu je IMHO úplně ukradený, kolik bitů má slovo, 16, 32, 18, 36, 48 - není problém, byl implementovaný na tolika šílených architekturách, že se s tím autoři implementací naučili žít (a porvat). Ale můžeš zkusit tenhle stroják ještě urychlit. Osobně si ale myslím, že současné implementace jsou pro většinu aplikací Good Enough(TM).

[Martin Tůma]

Například:

;       7B:       48C1FA03         SAR RDX, 3

je krásná ukázka dodatečný režie (hodnotu proměnné musíš o 3, tedy počet bitů zabraný LISPem na informace o typu, aritmeticky zrotovat do prava, aby si proměnnou mohl pomocí IMUL vynásobit a výsledek byl správně), kterou daný způsob reprezentace přináší.

[Martin Tůma]

Ehm, tím "zrotováním" je samozřejmě myšlen klasickej aritmetickej shift... ale moji assembleristé mi jistě rozumí

[Kyosuke]

No jasně, ten 1 uOP (SHR mreg64, imm8; DirectPath, latence 1 takt) v barrel shifteru úplně zabije výkon, mnohem víc, než násobení (IMUL reg64, mreg64; DirectPath, latence 4 takty), volání neinlinovaných funkcí, cache misses, branch prediction misses, nekoherentní přístupy do paměti a nekompaktní datové struktury (jako by byla hlavička objektu, kdybych chtěl int na celých 32 bitů). Že mě to hned nenapadlo. Ne, vážně, přestaň rejpat tam, kde to nemá smysl.

[Martin Tůma]

Ptal ses na to, jak tato implementace znemožňuje efektivně provádět operace na integerech. To jsem ti snad ukázal jasně, i na tvém příkladu "optimálního" kódu.

To že máš představu, že jenom díky takové implementaci můžeš mít efektivní práci s pamětí a tudíž je to optimalizace je tvůj problém. Já prostě takovej handl za optimalizaci nepovažuju, když vím, že můžu mít obojí (minimální paměťové nároky i maximální rychlost vykonávání kódu)

[Kyosuke]

"Ukázal"? Chichi, to jsem viděl, a patřičně se k tomu vyjádřil. A vůbec, já taky můžu mít obojí i bez typetagů. Tohle jsou jen neboxované samostatné fixnumy, nikdo netvrdí, že uvnitř struktur, složitějších objektů a polí potřebuju typetagy. Porušovat přírodní zákony ovšem nejde, a samostatný 64b integer není objekt (tj. nezná svůj typ).

[zde]

Ten kod je sice moc hezky, ale uplne chybny. Chybi typova kontrola, dispatch na pretizene operatory v pripade ze nejde o integery, a zejmena generovani vyjimky nebo koerce do bignumu pokud dojde k preteceni. Nebo snad lisp pouziva nejaky nedokumentovany rezim i386, kde IMUL i LEA delaji automaticky INTO?

Tyhle veci jsou pro bezpecny vysokourovnovy kod nezbytne, a jejich inlinovani na dnesnich CPU vede k nechutnemu bloatu v drahocenne iCache. Interpret + bajtkod je kupodivu nejen jednodussi, ale casto i rychlejsi (viz Java vs Python)

[Kyosuke]

Chybný? Dělá přesně to, co se mu řekne. Myslíš, že kompilátor neprovede ty kontroly jinde, třeba v případě, že se ta funkce někde použije? Koneckonců ví, co vygeneroval, myslíš, že je sklerotický? Ostatně:

1) Tohle je jen ilustrace fixnumů s type tagy - čteš i kontext, že jo? Tudíž mi šlo čistě jen o to, co je třeba provádět s type-tagged integery navíc v porovnání s untagged integery. Koerce do bignumu a generování výjimky se obojího dotýká úplně stejně. Nebo snad C/C++ používá nějaký nedokumentovaný režim i386, kde IMUL i LEA dělaji pro untagged integery automaticky INTO?

2) Nikdy bych nedal (safety 0) do provozního kódu, pokud bych neměl nade vší pochybnost zaručené (třeba kontrolami okolo nebo invarianty dat), že tím něco nezbourám, přeci nejsem magor. BTW, spousta kódu psaného v Cčku pořád ještě funguje, dokonce i ten zabugovaný binární search v poli v Javě celé roky nikomu nevadil.

3) Povětšinou se zúženou deklarací typu můžu i tomu přetečení vyhnout staticky, koneckonců 64b čísla jsou dost velká takřka pro cokoli a aplikační data většínou mají nějaký konkrétní smysl.

4) Netuším, proč předpokládáš, že aplikační kód musí být uniformní. Není přeci problém mít většinu kódu kompaktní a vnitřní smyčky a exponovaná místa rychlá. To se přeci dělá úplně normálně, ne? Take bezpečný vysokoúrovňový kód můžu mít 99 % aplikace a tam, kde potřebuju, si prostě zamažu ruce.

S floaty to bude u SBCL asi horší, ale stejně bych si moc nestěžoval - stejně přemýšlím o tom, že na intenzivní floating-point aritmetiku udělám takový menší framework, protože s vektorovým kódem jsou dneska tak trošku na štíru i kompilátory Cčka a dokopat je k něčemu rozumnému asi nebude triviální (i když už se situace lepší a dokážou už rozpoznávat nějaké ty smyčky). Možná bych se mohl naučit Fortran, ale integrace kódu v několika jazycích mě moc nebere.

[zde]

Takže když pak tu funkci 10x zavolám někde jinde, tak se mi v 9 případech před ten CALL rozbalí ještě typová kontrola argumentů? Dělat stejnou věc na devíti místech místo na jednom mi nepřijde jako dobrý nápad. Horká cesta bude beztak bez skákání, takže když se typecheck opravdu zázračně ušetří, beztak to bude nula nic... Teď mě napadá, fajn věc by byl dual entry point- když překladač zná typ a ví že je ok, skočí jen místo na začátek funkce o kousek dál a zbytečnou kontrolu ušetří. Ale podle listingu to na tohle moc nevypadá.

Ad overflow: Ano, data která mají smysl obvykle nepřetečou. Ale často je někde chyba, a z nějaké smyčky se včas nevypadne. Pak se data po wraparoundu stále tváří rozumně, a mnohem déle trvá než se na chybu přijde. Když dostanu výjimku, nebo program zastavím a v debuggeru vidím číslo s padesáti ciframa tam kde být nemá, hned vídím co se děje. Geniálně se s kontrolou přetečení vyrovnala LUA. Nemusí ho detekovat, ani nemusí umět bignumy. Jednoduše nemá integery a všecko ukládá v double floatech.

[Kyosuke]

Přinejmenším Allegro CL dual entry pointy implementuje, i když to není v oficiální dokumentaci. Tohle je spíš věc implementace, ne věc jazyka, i když je v pravda, že v dynamickém a interaktivním systému se některé věci dělají složitěji než treba v Haskellu. Do SBCL bohužel nikdo tolik peněz nenapumpoval , ale firmě by to asi bylo stejně jedno, tak pro ni tak drahé ACL zase není a mně osobně je to víceméně ukradený. Já se spokojím s možností psát inline SSE assembler a zbytek výkonu je mi putna, pokud to nebude pomalý jako Python, což není.

[Kyosuke]

BTW, ty double floaty jsou dobrý trik , ale co když podteče přesnost? To se taky dá detekovat, že kupříkladu poslední součet byl nepřesný? Taky se mi to nějak nezdá.

[zde]

No, exception při precision loss se na 387+ zapnout dá, ale krom fortranu to snad nikdo nepodporuje. LUA zřejmě precision loss tiše ignoruje, viz:

$ lua -e 'print((0x100000000000000 + 1) % 2)'
0

[Kyosuke]

Masakr, to jsem netušil. Kdyby to měly všechny FPU jednotky, dalo by se uvažovat o nové implementaci bignumů pro OpenMCL, hmm... Mně totiž štve, že jen CLISP má tak brutálně rychlou multiprecision aritmetiku a jiné implementace v porovnání s ním mají prd. Asi do něj autor nasypal při vaření špetku černé magie.

[Kyosuke]

Jinak tuhle filosofii, kterou zmiňuješ, docela pěkně ilustruje CLISP. Ten má opravdu brutálně kompaktní kód. Chvílemi se to opravdu hodí, takže si ho taky držím při ruce. A s tím, jak se rozevírají nůžky mezi rychlostí ALU a rychlostí paměti, jeho dřívější nevýhody postupně mizí. (Akorát si nejsem jist, zda se u něj dá mluvit o jednoduchosti, ono napsat si vlastní nadstavbu Cčka bylo sice od Bruna Haibla geeky, ale vůbec tomu kódu nerozumím. )

[Ondrej 'SanTiago' Zajicek]

> Něco, co znemožňuje nad datovým typem integer efektivně provádět aritmetické operace,

Je otazka, zda na dnesnich procesorech je horsi udelat navic nejaky ty shifty, andy a ory, nebo tahat z RAM vic dat a pripadne nasledovat indirekci.

[Martin Tůma]

Tahání více dat z RAM je dneska určitě větší zlo, než nějaké ty instrukce navíc, o tom žádná. Smysle příspěvku bylo ukázat, že neexistuje nic jako "optimální (ve smyslu rychlosti vykonávání kódu) vysokoúrovňový jazyk", ať se marketingové oddělení SUNu nebo Kyosuke snaží sebevíc. Vždy je to "něco za něco".

[Kyosuke]

To snad tady nikdo netvrdí, že nikdy nejde něco udělat líp. Fakt ovšem je, že typetag nad immediate hodnotou ušetří hlavičku u typovatelných objektů, paměť a její bandwidth, a to za mizivou ztrátu výkonu, a to ještě jen na některých architekturách (i když je pravda, že hardwarová podpora type tagů poslední dobou vypadla z módy, nicméně na dnešních procesorech bude SHR reg, x trvat více než jeden tak jedině na Netburstu, a pro ten stejně nemá smysl něco optimalizovat, leda upgradem ) a navíc ne ve všech aplikacích.

[Ondrej 'SanTiago' Zajicek]

> Smysle příspěvku bylo ukázat, že neexistuje nic jako "optimální (ve smyslu rychlosti vykonávání kódu).

Nicmene tahle implementace integeru je optimalizace oproti naivnim type tagum ci boxovanym integerum. To, ze tam nejake type tagy budou, vyplyva ze zadani - najit implementaci integeru pro dynamicky typove jazyky. A toto reseni je ze znamych reseni asi nejblize optimalnimu (ve smyslu "nejlepsimu reseni splnujici zadane pozadavky").

[Kyosuke]

Díky, náčelníku, že ses mě zastal.

[Heron]

že v Javě to spotřebuje 43,5 MB

No jo, ale on potřebuje, aby sloupeček s Javou byl pětkrát vyšší, než Ruby. To tam nemůže dát 43.5MB.

[alblaho]

No tak já myslím, že pole čistých "machine" integerů bude zabírat ve všech jazycích stejně, o tom jaksi nemá cenu se bavit.

[Honza Jaroš]

A pro srovnání - na 64bit systému (Gentoo@Core2Duo) to dělá s Javou6 a polem obyčejných int 108MB (autorova ukázka sežere 335MB). Python si pak vezme 263MB a Ruby 67MB.

Škoda že javovská generika pracují pouze s referenčními typy...

[Ondrej 'SanTiago' Zajicek]

> Asi je to díky jednomu triku, který Matz používá: integery skladuje přímo (žádné reference) s tím, že nejnižší bit určuje, jestli se jedná o číslo, nebo o referenci.

Hmm, myslel jsem, ze tohle pouziva snad kazdy interpret ci kompilator dynamicky typovanych jazyku. Dost me prekvapuje, ze to Mono a Java dela jinak

[Tom.š Ze.le.in]

Nejmenované prastaré jazyky (respektive jejich implementace) umožňují lepší z obou situací dle vyjádření programátora:

• typ fixnum, který se vejde do 32bitu i s tagem o typu,
• typ (signed-byte 32), který má danou délku,
• v obecných polích která mohou obsahovat cokoliv zabere fixnum strojové slovo, bignum (větší číslo) víc - boxed reprezentace
• v polích deklarovaných jako obsahující (signed-byte 32) zabere 32bitový integer 32bitu (unboxed reprezentace).

Jinými slovy, je zbytečné u obrovského pole 32bitových integeru mít informaci u typu u každého integeru, když stačí jednou u pole.

Jediným problémem je možná terminologie, která na bytu délky 36bitu nevidí nic nelogického.

[miho]

Zkousel jsem jeste MS implementaci .net ve virt. stroji.

int[] pole;
pole = new int[8*1024*1024];

ma cely proces: 36900kiB.

skoro ekvivalent pomoci generiky jak bylo uvedeno v blogpostu: 37140kiB.

Pole typu object do ktereho se nasazeji zaboxovane Inty taktez podle blogpostu: 141648kiB

[zde]

Tak nevím, ať dělám co dělám, víc než 32MiB mi python sebrat nechce...

>>> from array import array
>>> a = array('I', xrange(8*1024*1024))
>>> a[:5]
array('I', [0L, 1L, 2L, 3L, 4L])
>>> a[-5:]
array('I', [8388603L, 8388604L, 8388605L, 8388606L, 8388607L])
>>> len(a.tostring())
33554432

[Martin Tůma]

Ukazuje to na příkladu pole pro 8 milionů integerů (tedy 32 MiB dat)

Co je to za platformu, kde má integer velikost 4.19B?

[Josef Kufner]

Není to zas nějaký nový Celeron?