Paměťová a výpočetní náročnost JVM vs .NET

[javaman ((]

Podívejte se třeba, jak pomáhá Miniboxing ve Scale. Nebo na to, jaký je rozdíl, když se data v poli čtou v náhodném pořadí nebo postupně od začátku do konce (30. minuta).

Kde je tam ta Java a moderní HW? Tyhle optimalizace klidně může dělat JVM, ale programátor by se moc starat neměl.

[Reklama]

[Radek Miček]

Podívejte se třeba, jak pomáhá Miniboxing ve Scale. Nebo na to, jaký je rozdíl, když se data v poli čtou v náhodném pořadí nebo postupně od začátku do konce (30. minuta).

Tyhle optimalizace klidně může dělat JVM, ale programátor by se moc starat neměl.

Ano, ale většina JVM to nedělá (možná, že některé implementace, které neznám, to dělají). Místo toho se plánuje, že se část toho, co .NET umí už 10 let (od C# 2.0), přidá do Javy 10 (viz Project Valhalla).

Kde je tam ta Java a moderní HW?

Myslím, že výsledky Miniboxingu lze vztáhnout i na Javu - Scala byla měřena nad JVM. Ta měření jsou dělána na moderním HW.

[javaman ((]

Asi to zase taková pecka nebude. Čistě teoreticky by to určitě JVM mohlo při nějakých případech dělat. Programátora by to zajímat moc nemělo. To, že to přidají, je fajn, ale třeba to také nebude až tak využívané, když .Net se nepoužívá a Java je nejrozšířenější.

S tou Scalou máš asi pravdu, ale moc nebudu zkoumat ty testy. Většinou bývají trochu nereálné. Každopádně i kdyby to byla nejlepší věc na světě, tak jsem získal dvojnásobný výkon při nějakých operacích a čtyřnásobný při jiných. To mě moc jako nebere, pokud je to tvoje dobré využití cache. Pokud je to na něco jiného, tak OK, ale i tak je to moc slabé. Když optimalizovat, tak pořádně. Ale lepší než nic, to je jasné.

[Radek Miček]

když .Net se nepoužívá a Java je nejrozšířenější.

V tom máte pravdu. Hlavní problém .NETu je IMO závislost na Microsoftu (zvláště, když si člověk vzpomene, jak se MS chová).

Navíc Java má kvalitnější nástroje (např. nejrozšířenější build systémy pro .NET jsou celkem katastrofální oproti Gradlu nebo Mavenu).

[gl]

Zkus si porovnat rychlost průchodu dlouhého pole.

Porovnat s čím? A co znamená „průchod pole“?

Kód: [Vybrat]

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define DIST(x1,x2,y1,y2) \
  (sqrt((x2 - x1)*(x2 - x1) + ((y2 - y1)*(y2 - y1))))

#define ARR_LEN 1000000

typedef struct Point {
  int x;
  int y;
} Point;

int main()
{
  struct Point *points = malloc(ARR_LEN * sizeof(struct Point));
  struct Point **ppoints = malloc(ARR_LEN * sizeof(struct Point*));
  struct Point **ppoints2 = malloc(ARR_LEN * sizeof(struct Point*));
  double path_length = 0;
  int i;
  int index;
  for(i = 0; i < ARR_LEN; ++i){
    index = i % 2 == 0 ? i>>1 : ARR_LEN - (i>>1) - 1;
    ppoints2[index] = malloc(sizeof(struct Point));
  }
  for(i = 0; i < ARR_LEN; ++i){
    points[i].x = rand() % 20;
    points[i].y = rand() % 20;
    ppoints[i] = &points[i];
    ppoints2[i]->x = points[i].x;
    ppoints2[i]->y = points[i].y;
  }
  clock_t begin = clock();
  for(i = 1; i < ARR_LEN; ++i){
    path_length += DIST(points[i].x, points[i - 1].x,
                        points[i].y, points[i - 1].y);
  }
  clock_t end = clock();
  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("length %f time spent %f\n", path_length, time_spent);
  begin = clock();
  path_length = 0;
  for(i = 1; i < ARR_LEN; ++i){
    path_length += DIST(ppoints[i]->x, ppoints[i - 1]->x,
                        ppoints[i]->y, ppoints[i - 1]->y);
  }
  end = clock();
  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("length %f time spent %f\n", path_length, time_spent);
  begin = clock();
  path_length = 0;
  for(i = 1; i < ARR_LEN; ++i){
    path_length += DIST(ppoints2[i]->x, ppoints2[i - 1]->x,
                        ppoints2[i]->y, ppoints2[i - 1]->y);
  }
  end = clock();
  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("length %f time spent %f\n", path_length, time_spent);
  return 0;
}

ne úplně umělý příklad. Výpočet délky cesty ze seznamu bodů. Na mém počítači je průchod points dvakrát rychlejší než průchod ppoints2 a asi o 50% rychlejší než ppoints. Uznávám, čekal jsem větší rozdíl.

[Reklama]

[ava]

Souhlasím, že pole structů by v Javě mohlo občas pomoci. Teďka implementuju kolaborativní filtr, který má v reálném čase ohodnotit uživatele podle toho, jak by se jim mohl líbit nějaký produkt, když se jim líbily podobné produkty, podobnost dvou produktů se pozná podle toho, že  byly často kupované spolu. Při výpočtu jde opravdu o rychlost za každou cenu. Po předělání z HashMap na Array a reorganizaci dat v paměti se výpočet zrychlil 200x bez faktické změny algoritmu.

Mám předpočítanou mapu podobností, která má cca 50 000 000 položek, konceptuálně jde o páry (uživatel: Int, podobnost: Float). Co s tím? Ideální by bylo mít jedno velké pole struktur (user, similarity), ale to v Javě nejde. Takže si buďto udělám dvě velké pole, jedno pouze s uživateli, druhé s podobnostmi, a budu je procházet souběžne (tím přijdu o jednu cache linku, což zrovna v tomto případě tolik nevadí), nebo budu mít jedno velké pole, a vždy lichý prvek bude uživatel, a na sudý udělám Float.intBitsToFloat/Float.floatToRawIntBits. Kdybych v tom poli měl reference na tuple (uživatel, podobnost), tak se to celé šíleně zpomalí kvůli dereferencím (šahání do paměti), a navíc to bude zabírat místo 400 MB (8 bajtů na položku) cca 1400 MB (kvůli headeru a alignmentu očekávám 24 bajtů na instanci tuplu + 4 bajty reference v poli) To celé jen kvůli tomu, že Java nemá struct.

Jak by se tohle implementovalo v nějaké databázi si nedovedu představit, hlavně jak ji donutit, aby si přes všechny databázové abstrakce zorganizovala data v paměti a použila algoritmus průchodu přesně tak, jak potřebuji.

Takže určitě jsou scénáře, kde by se structy hodily, i když to není nijak superčasté. Otázka je, jak hodně by to zkomplikovalo jazyk, docela by mě zajímalo, jestli to v C# nepřináší nějaké nečekané trable? Každopádně umět vhodně data zorganizovat v paměti je pro rychlé výpočty zásadní, přístup do hlavní paměti je dnes obrovskou brzdou.

[atarist]

Souhlasím, že pole structů by v Javě mohlo občas pomoci. Teďka implementuju kolaborativní filtr, který má v reálném čase ohodnotit uživatele podle toho, jak by se jim mohl líbit nějaký produkt, když se jim líbily podobné produkty, podobnost dvou produktů se pozná podle toho, že  byly často kupované spolu. Při výpočtu jde opravdu o rychlost za každou cenu. Po předělání z HashMap na Array a reorganizaci dat v paměti se výpočet zrychlil 200x bez faktické změny algoritmu.

Mám předpočítanou mapu podobností, která má cca 50 000 000 položek, konceptuálně jde o páry (uživatel: Int, podobnost: Float). Co s tím? Ideální by bylo mít jedno velké pole struktur (user, similarity), ale to v Javě nejde. Takže si buďto udělám dvě velké pole, jedno pouze s uživateli, druhé s podobnostmi, a budu je procházet souběžne (tím přijdu o jednu cache linku, což zrovna v tomto případě tolik nevadí), nebo budu mít jedno velké pole, a vždy lichý prvek bude uživatel, a na sudý udělám Float.intBitsToFloat/Float.floatToRawIntBits. Kdybych v tom poli měl reference na tuple (uživatel, podobnost), tak se to celé šíleně zpomalí kvůli dereferencím (šahání do paměti), a navíc to bude zabírat místo 400 MB (8 bajtů na položku) cca 1400 MB (kvůli headeru a alignmentu očekávám 24 bajtů na instanci tuplu + 4 bajty reference v poli) To celé jen kvůli tomu, že Java nemá struct.

Jak by se tohle implementovalo v nějaké databázi si nedovedu představit, hlavně jak ji donutit, aby si přes všechny databázové abstrakce zorganizovala data v paměti a použila algoritmus průchodu přesně tak, jak potřebuji.

Takže určitě jsou scénáře, kde by se structy hodily, i když to není nijak superčasté. Otázka je, jak hodně by to zkomplikovalo jazyk, docela by mě zajímalo, jestli to v C# nepřináší nějaké nečekané trable? Každopádně umět vhodně data zorganizovat v paměti je pro rychlé výpočty zásadní, přístup do hlavní paměti je dnes obrovskou brzdou.

Teoreticky pokud to neni extra ridke pole muze byt index == (ID_uzivatele - nejaky_offset) + nejaky NaN pro neexistujici ID_uzivatele ale to skutecne zalezi na datech, nekdy to jde, nekdy ne. Usetris tedy v idealnim pripade 50% dat (i cache!), v neidealnim pripade budes mit ridke pole floatu...

OT: prosim snaz se to naprogramovat inteligentne a ne tak, ze kdyz si koupim kolo, tak se ma dalsich x mesicu objevuje reklama na dalsi kola. Docela bych rekl ze jezdit a opravovat kolo umim, takze par desitek tisic kilometru vydrzi, nebudu kupovat dalsi takze by me reklama zahackovala na spotrebak (plaste, retezy...).

[ava]

Teoreticky pokud to neni extra ridke pole muze byt index == (ID_uzivatele - nejaky_offset) + nejaky NaN pro neexistujici ID_uzivatele ale to skutecne zalezi na datech, nekdy to jde, nekdy ne. Usetris tedy v idealnim pripade 50% dat (i cache!), v neidealnim pripade budes mit ridke pole floatu...

OT: prosim snaz se to naprogramovat inteligentne a ne tak, ze kdyz si koupim kolo, tak se ma dalsich x mesicu objevuje reklama na dalsi kola. Docela bych rekl ze jezdit a opravovat kolo umim, takze par desitek tisic kilometru vydrzi, nebudu kupovat dalsi takze by me reklama zahackovala na spotrebak (plaste, retezy...).

Vynechal jsem nějaké detaily, tohle pole už je tak husté jak je to možné, nejsou tam položky s nulovou similaritou, uživatelé co nic nekoupili atp., to už je všechno vyoptimalizované.

Co se týče OT, jasně, snažíme se, tvoje reklama bude tak super, že už ani nebudeš mít čas na kole jezdit, budeš jen nakupovat nejlepší spotřebák

[atarist]

OT: prosim snaz se to naprogramovat inteligentne a ne tak, ze kdyz si koupim kolo, tak se ma dalsich x mesicu objevuje reklama na dalsi kola. Docela bych rekl ze jezdit a opravovat kolo umim, takze par desitek tisic kilometru vydrzi, nebudu kupovat dalsi takze by me reklama zahackovala na spotrebak (plaste, retezy...).

Co se týče OT, jasně, snažíme se, tvoje reklama bude tak super, že už ani nebudeš mít čas na kole jezdit, budeš jen nakupovat nejlepší spotřebák

Hehe super, konecne pozitivni zprava na diskuzich na rootu. cekam s kreditkou v ruce...

[Kolemjdoucí]

Zkus si porovnat rychlost průchodu dlouhého pole.

Porovnat s čím? A co znamená „průchod pole“?

Diskuse se točí dokola, Jirsák odmítá uznat naprosto elementární fakta. Konkrétní příklady procházení pole jsem jsem popisoval už v příspěvku #32.

[Filip Jirsák]

Diskuse se točí dokola, Jirsák odmítá uznat naprosto elementární fakta. Konkrétní příklady procházení pole jsem jsem popisoval už v příspěvku #32.

Elementární fakta já uznávám. První, kdo sem nějaká fakta napsal, byl gl, a potvrdil, co tady celou dobu píšu:

Na mém počítači je průchod points dvakrát rychlejší než průchod ppoints2 a asi o 50% rychlejší než ppoints. Uznávám, čekal jsem větší rozdíl.

[podlesh]

Mám předpočítanou mapu podobností, která má cca 50 000 000 položek, konceptuálně jde o páry (uživatel: Int, podobnost: Float). Co s tím? Ideální by bylo mít jedno velké pole struktur (user, similarity), ale to v Javě nejde. Takže si buďto udělám dvě velké pole, jedno pouze s uživateli, druhé s podobnostmi, a budu je procházet souběžne (tím přijdu o jednu cache linku, což zrovna v tomto případě tolik nevadí),...

Jenom technická: takto se to implementuje prakticky všude (např. Python), protože se pak používají vektorové a maticové operace. Ty jsou extrémně rychlé nejenom kvůli nativní implementaci (tj. v C, Fortranu nebo dokonce asm), ale také kvůli tomu že je optimalizovali matematici :-)

[gamer]

ne úplně umělý příklad. Výpočet délky cesty ze seznamu bodů. Na mém počítači je průchod points dvakrát rychlejší než průchod ppoints2 a asi o 50% rychlejší než ppoints. Uznávám, čekal jsem větší rozdíl.

Ten test je značně syntetický, normálně objekty vznikají v různém čase a nejsou v paměti za sebou. Tato úprava ho trochu zreální:

Kód: [Vybrat]

@@ -28,7 +28,7 @@ int main()
   for(i = 0; i < ARR_LEN; ++i){
     points[i].x = rand() % 20;
     points[i].y = rand() % 20;
-    ppoints[i] = &points[i];
+    ppoints[i] = &points[rand() % ARR_LEN];
     ppoints2[i]->x = points[i].x;
     ppoints2[i]->y = points[i].y;
   }

Což je u mě (po zvětšení ARR_LEN) skoro 6x pomalejší:

Kód: [Vybrat]

length 1041522432.408077 time spent 0.760000
length 1041511428.008295 time spent 4.350000


[gl]

ne úplně umělý příklad. Výpočet délky cesty ze seznamu bodů. Na mém počítači je průchod points dvakrát rychlejší než průchod ppoints2 a asi o 50% rychlejší než ppoints. Uznávám, čekal jsem větší rozdíl.

Ten test je značně syntetický, normálně objekty vznikají v různém čase a nejsou v paměti za sebou. Tato úprava ho trochu zreální:

Kód: [Vybrat]

@@ -28,7 +28,7 @@ int main()
   for(i = 0; i < ARR_LEN; ++i){
     points[i].x = rand() % 20;
     points[i].y = rand() % 20;
-    ppoints[i] = &points[i];
+    ppoints[i] = &points[rand() % ARR_LEN];
     ppoints2[i]->x = points[i].x;
     ppoints2[i]->y = points[i].y;
   }

Což je u mě (po zvětšení ARR_LEN) skoro 6x pomalejší:

Kód: [Vybrat]

length 1041522432.408077 time spent 0.760000
length 1041511428.008295 time spent 4.350000


Snažil jsem se alokovat ppoints2 současně od konce a od začátku, ale asi to nepomohlo. ppoints mělo být pro srovnání za sebou.

[Filip Jirsák]

Ten test je značně syntetický, normálně objekty vznikají v různém čase a nejsou v paměti za sebou.

Ten test má porovnávat použití pole struktur a pole referencí. Pole struktur, které vznikají v různém čase, je velmi netypické použití. A pole struktur, které nejsou v paměti za sebou, není pole struktur. Pokud chcete porovnávat kód, kde objekty vznikají v různém čase a nejsou v paměti za sebou, zařaďte do testu i to, že ty struktury musíte do toho pole nejprve zkopírovat. A když už budete v tom testování, doporučuju změřit i paměťovou náročnost.