Částicový filtr na Raspberry Pi v Javě

robot

Částicový filtr na Raspberry Pi v Javě
« kdy: 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:

Kód: [Vybrat]
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.)


xsdfasfasdf

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #1 kdy: 27. 05. 2017, 12:49:16 »
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.

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #2 kdy: 27. 05. 2017, 13:14:17 »
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


gll

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #3 kdy: 27. 05. 2017, 13:19:37 »
Zbytečně znovuvynalézáš kolo. Použij hotovou knihovnu.

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #4 kdy: 27. 05. 2017, 13:21:11 »
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á.


Jenda

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #5 kdy: 27. 05. 2017, 13:24:34 »
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?

Jenda

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #6 kdy: 27. 05. 2017, 13:28:21 »
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.

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #7 kdy: 27. 05. 2017, 13:31:42 »
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.

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #8 kdy: 27. 05. 2017, 13:34:07 »
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.

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #9 kdy: 27. 05. 2017, 13:40:27 »
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.

Jenda

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #10 kdy: 27. 05. 2017, 17:08:08 »
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.

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #11 kdy: 27. 05. 2017, 17:54:21 »
To zadání je tak triviální, že tam není algoritmicky co optimalizovat.

Spíš typově, jak už lépe rozvedli jiní.

balki

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #12 kdy: 27. 05. 2017, 18:36:32 »
Skuste pouzit oracle jre miesto openjdk jre.

gll

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #13 kdy: 27. 05. 2017, 19:02:01 »
Kdyby vám stačil python, tak vektorizovaná funkce exp je součástí numpy.

Homo Buzerantus

Re:Částicový filtr na Raspberry Pi v Javě
« Odpověď #14 kdy: 27. 05. 2017, 19:03:41 »
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.