Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: robot 27. 05. 2017, 12:21:24
-
Ahoj, mám menší problém, se kterým mi doufám pomůžete nebo mě nasměrujete k řešení. Mám robota řízeného pomocí Raspberry Pi, kde jsem potřeboval implementovat částicový filtr. Na malých datech všechno funguje správně, ale jakmile zvětším matici póz na řádově tisíce v jednom rozměru, implementace v Javě začne haprovat. Obecně to začne drhnout na funkci exp(), viz zjednodušená třída ilustrující problém:
class Matrix {
Complex comps[];
int width, height, stride;
Matrix (int h, int w) {
comps = new Complex[h * w];
height = h; width = w; stride = w;
}
Complex comp(int row, int col) {
return comps[row*stride+col];
}
void setComp(int row, int col, Complex x) {
comps[row*stride+col] = x;
}
Matrix exp() {
Matrix m = new Matrix(height, width);
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
m.setComp(i, j, comp(i, j).exp());
}
}
return m;
}
}
Při rozměrech 5000x5000 už mi to nic nespočítá (matice se vytvoří, ale pak OOM nebo zabřednutí ve swapování, což na RPi není zrovna ono na SD kartě). Musel jsem to přepsat do C++, tam to jede bez problémů (vytvoření matice asi 4x rychlejší, výpočet pak zhruba stejně rychlý) a je mi vlastně jedno, v čem to je implementované, ale z principu bych rád věděl, jak by se to mělo v Javě napsat, aby to fungovalo? (Kód jsem zkoušel i na desce s ARM64 se stejným výsledkem.)
-
a nejsou ty data v matici ridke, ze je velka cas hodnot nulova?
pak jdou pouzit sparse matice, ulozis si do vektoru pozici i, pozici j a hodnotu.
-
Záleží kolik je dostupné paměti a jak je nastavená. Každopádně obecnou radou je:
- debugovat aplikaci a ověřit, kde ta paměť mizí
- podívat se, jak to dělají ostatní, tj. jak ostatní ten filtr v javě pro RPi implementují, zda už na to třeba není nějaká optimalizovaná knihovna která třeba používá nějaké triky
-
Zbytečně znovuvynalézáš kolo. Použij hotovou knihovnu.
-
V kódu nemáte třídu Complex, takže můžeme spíš jen hádat.
Matici máte uloženou jako jedno velké pole, takže v paměťovém prostoru JVM to musí být uložené jako jeden velký souvislý kus paměti. Ušetříte tím reference a mohlo by to být výhodné, pokud by se ta paměť alokovala jednou a efektivně a pak už se s tím nemuselo hýbat. Vy to pole ale při volání exp() alokujete pokaždé znova. Takže bych zvážil, zda nemůžete použít pool objektů Matrix, možná dokonce můžete pole modifikovat na místě a stačí vám jediná instance. Také bych zvážil změnit matici na pole polí.
A pak je tu ten tajemný typ Complex. Každý prvek matice je objekt, tedy v poli je jen reference, která ukazuje bůhvíkam do paměti. V nejhorším případě musí procesor v každé iteraci toho dvojitého cyklu čekat, až mu dorazí data z hlavní paměti. Tipoval bych, že typ Complex bude ve skutečnosti něco velmi jednoduchého, třeba dva inty. Ty by pak bylo mnohem lepší uložit přímo do pole, bez referencí – procesor pak bude mít všechny hodnoty pěkně vedle sebe a pojede po řádku cache. Sice to pak nebude hezké objektové, ale to už nemáte stejně, když tam používáte to pole a cyklus přes všechny prvky.
Když už to budete „deobjektovat“, odstranil bych i ta volání funkcí compa setComp, a pokud matici necháte jako jedno velké pole, pak bych i ten dvojitý cyklus přepsal na jednoduchý. Co jsem slyšel, runtime optimalizace v JVM na ARMech nejsou žádná sláva, takže bych nespoléhal, že to inlinuje JVM a udělal bych to ručně. Stejně už teď ten kód není objektový a hezký :-)
A samozřejmě, jak napsal předřečník, nejvíc ušetříte tím, pokud správně popíšete problém, který řešíte – a zjistíte třeba, že ta vaše matice není úplně obecná matice, ale má některé speciální vlastnosti, které můžete s výhodou použít pro optimalizaci.
Jinak RPi a Java je pro řízení robota zajímavá kombinace, ani RPi (předpokládám s Linuxem) ani obecná Java nejsou realtimeové systémy, není tam garantovaná odezva. Všechno může dlouho krásně fungovat, a pak Java spustí GC nebo něco naplánuje Linux a váš program se najednou zastaví na mnohem delší dobu, než obvykle. Rozmyslete si, co to s robotem udělá.
-
Pár nástřelů:
- Možná se GC prostě spouští pozdě.
- Možná je tvůj Complex v jednom jazyku float a v jednom double (tj. matice je 2x větší, v jednom případě potřebuješ 400 MB a ve druhém 800 MB, což už se do RPi vedle ostatních věcí, JVM a tak nevejde) a navíc výpočty trvají 2x i víc déle.
- Kdysi dávno se na Raspbianu používala softfloat verze JVM.
- Javě nerozumím, není tam nějaký overhead s boxingem Complexu?
- Neošetřil ti někdo v jednom z jazyků denormalized floaty?
-
A pak je tu ten tajemný typ Complex. Každý prvek matice je objekt, tedy v poli je jen reference, která ukazuje bůhvíkam do paměti. V nejhorším případě musí procesor v každé iteraci toho dvojitého cyklu čekat, až mu dorazí data z hlavní paměti.
Aha, tak tady by mohl být ten problém. Protože pokud má poitry + dvě čísla a objekt má třeba hlavičku a spol. (nebo nemá a jsou to doubly), tak se to do 1 GB paměti RPi prostě vejít nemůže.
-
Záleží kolik je dostupné paměti a jak je nastavená. Každopádně obecnou radou je:
- debugovat aplikaci a ověřit, kde ta paměť mizí
- podívat se, jak to dělají ostatní, tj. jak ostatní ten filtr v javě pro RPi implementují, zda už na to třeba není nějaká optimalizovaná knihovna která třeba používá nějaké triky
To zadání je tak triviální, že tam není algoritmicky co optimalizovat.
-
A pak je tu ten tajemný typ Complex. Každý prvek matice je objekt, tedy v poli je jen reference, která ukazuje bůhvíkam do paměti. V nejhorším případě musí procesor v každé iteraci toho dvojitého cyklu čekat, až mu dorazí data z hlavní paměti.
Aha, tak tady by mohl být ten problém. Protože pokud má poitry + dvě čísla a objekt má třeba hlavičku a spol. (nebo nemá a jsou to doubly), tak se to do 1 GB paměti RPi prostě vejít nemůže.
Otázka je, jak pak typ pro komplexní čísla v Javě udělat. Tady to bez hodnotových typů prostě nijak objektově nejde.
-
a nejsou ty data v matici ridke, ze je velka cas hodnot nulova?
pak jdou pouzit sparse matice, ulozis si do vektoru pozici i, pozici j a hodnotu.
U póz pro částicový filtr asi řídká nebude. Některé věci prostě v Javě nejdou, zvlášť na RPi.
-
To zadání je tak triviální, že tam není algoritmicky co optimalizovat.
S pamětí ne, ale třeba pro exp() jsou v SSE a AVX vektorové instrukce + se to dá aproximovat (i na NEONu). Na mém Ivy Bridge je AVX aproximace 40x rychlejší než skalární expf, na NEON se mi to přepisovat nechce.
-
To zadání je tak triviální, že tam není algoritmicky co optimalizovat.
Spíš typově, jak už lépe rozvedli jiní.
-
Skuste pouzit oracle jre miesto openjdk jre.
-
Kdyby vám stačil python, tak vektorizovaná funkce exp je součástí numpy.
-
Je to pole pointerů na objekty typu Complex, což žere hodně paměti a zpomaluje garbage collector.
Správně tam udělej dvě pole typu double, jedno pro reálnou část a druhé pro imaginární část. Třídu Complex vůbec nepoužívej, metodu exp rozepiš na operace nad hodnotami typu double.
Musíš zajistit, že v jádru toho cyklu se nebude alokovat žádný objekt, mohou tam být pouze operace s primitivními typy. Pokud tam nějaký objekt alokuješ, pak se z toho garbage collector posere.
Případně můžeš použít jazyk go, ve kterém je možné vyrobit pole struktur (aniž by to byly pointery jako v javě) a je možné se strukturami pracovat jako s primitivními typy, bez zatěžování garbage collectoru.
-
Je to pole pointerů na objekty typu Complex, což žere hodně paměti a zpomaluje garbage collector.
Správně tam udělej dvě pole typu double, jedno pro reálnou část a druhé pro imaginární část. Třídu Complex vůbec nepoužívej, metodu exp rozepiš na operace nad hodnotami typu double.
Musíš zajistit, že v jádru toho cyklu se nebude alokovat žádný objekt, mohou tam být pouze operace s primitivními typy. Pokud tam nějaký objekt alokuješ, pak se z toho garbage collector posere.
Případně můžeš použít jazyk go, ve kterém je možné vyrobit pole struktur (aniž by to byly pointery jako v javě) a je možné se strukturami pracovat jako s primitivními typy, bez zatěžování garbage collectoru.
Nejen Go, tak to má i C++, C#, Swift...
-
To zadání je tak triviální, že tam není algoritmicky co optimalizovat.
S pamětí ne, ale třeba pro exp() jsou v SSE a AVX vektorové instrukce + se to dá aproximovat (i na NEONu). Na mém Ivy Bridge je AVX aproximace 40x rychlejší než skalární expf, na NEON se mi to přepisovat nechce.
To jo, ale to už chce něco v nativním kódu, ne Javu.
-
S pamětí ne, ale třeba pro exp() jsou v SSE a AVX vektorové instrukce + se to dá aproximovat (i na NEONu). Na mém Ivy Bridge je AVX aproximace 40x rychlejší než skalární expf, na NEON se mi to přepisovat nechce.
To jo, ale to už chce něco v nativním kódu, ne Javu.
Ano, "nějaká optimalizovaná knihovna která třeba používá nějaké triky" nejspíš bude v nativním kódu.
-
Pro práci s maticemi použijte toto https://developer.arm.com/technologies/compute-library
-
Otazkou je, jestli ve skutecnosti vubec chces matici 5000x5000 a jeste na ni volat exp(). V kontextu casticovyho filtru a poloh robota si tim zdaleka nejsem jist (podobnou vec jsem delal). Krome toho je teda zjevnej nesmysl delat to na RPi zrovna v Jave (v ni muze bejt klidne zbylejch 99% programu na vyssich vrstvach) a kdyz uz, tak pri kazdym volani znova alokovat pole, to je taky volovina.
-
Otazkou je, jestli ve skutecnosti vubec chces matici 5000x5000 a jeste na ni volat exp(). V kontextu casticovyho filtru a poloh robota si tim zdaleka nejsem jist (podobnou vec jsem delal). Krome toho je teda zjevnej nesmysl delat to na RPi zrovna v Jave (v ni muze bejt klidne zbylejch 99% programu na vyssich vrstvach) a kdyz uz, tak pri kazdym volani znova alokovat pole, to je taky volovina.
Alokace jednoho pole je levná, jenže Java alokuje ještě všechny prvky znova, to je ten problém. C++/C#/Swift/Go/ADL provede jen jednu alokaci a pak počítá. Ten exp má být správně z matice reálných čísel do matice komplexních čísel, když už teda.
-
Ten exp má být správně z matice reálných čísel do matice komplexních čísel, když už teda.
Proč?
-
Otazkou je, jestli ve skutecnosti vubec chces matici 5000x5000 a jeste na ni volat exp(). V kontextu casticovyho filtru a poloh robota si tim zdaleka nejsem jist (podobnou vec jsem delal). Krome toho je teda zjevnej nesmysl delat to na RPi zrovna v Jave (v ni muze bejt klidne zbylejch 99% programu na vyssich vrstvach) a kdyz uz, tak pri kazdym volani znova alokovat pole, to je taky volovina.
Alokace jednoho pole je levná, jenže Java alokuje ještě všechny prvky znova, to je ten problém. C++/C#/Swift/Go/ADL provede jen jednu alokaci a pak počítá. Ten exp má být správně z matice reálných čísel do matice komplexních čísel, když už teda.
Java nic nealokuje, to ji programator musi prikazat, v poli jsou leda tak reference na null.
-
to jako filtruješ softwarově prach nebo co? A co jsou ty pózy?
-
To je nějaký masochismus, srát nesmysly v Javě na šrot typu RPi s naprosto nevyhovujícím množstvím paměti?
-
Hele a nechtěl by si ten částicovej filtr rozběhat na něčem perspektivnějším ?
http://www.viatech.com/en/boards/pico-itx/
navíc to mužeš programovat normálně ve visual studiu
-
Hele a nechtěl by si ten částicovej filtr rozběhat na něčem perspektivnějším ?
Ne a ne a ne... Poslední dobou vidím celou řadu podobných geniálních nápadů, např. zrovna včera pokus rozběhat FreeBSD-based NAS s ZFS (!!!) na tom samém šrotu.
-
to jako filtruješ softwarově prach nebo co? A co jsou ty pózy?
Co takhle se dovzdělat?
-
to jako filtruješ softwarově prach nebo co? A co jsou ty pózy?
Co takhle se dovzdělat?
Zbytocny prispevok, ked viete co to je, mozete odporucit robotronovi literaturu. Ale to by som vela od vas cakal.