Java vs C++ containers

A legutóbbi(?) Phoronix cikk kapcsán turul16
felvetette, hogy a Java containerek lassúak. Miután numerikus benchmarkot már futtatam most kíváncsi lettem mi a helyzet a tárolókkal.

Sajnos nem találtam olyat ami nem túl régi (ha valaki tud ilyet az megírhatná), ezért összetákoltam egyet magamnak a tárolókból amiket én gyakran használok Javaban ArrayList és HashMap ezek "megfelelőit" használtam C++-ban vector, map. A "tesztgép" a "szokásos" a sw:
gcc --version
gcc (GCC) 4.3.2 20081105 (Red Hat 4.3.2-7)

java -server -version
java version "1.6.0_11"
Java(TM) SE Runtime Environment (build 1.6.0_11-b03)
Java HotSpot(TM) Server VM (build 11.0-b16, mixed mode)

Java-t client módban nem mértem egyértelműen lassú, gcj-t próbáltam most is, még mindig lassú...

A tesztekről:
egy "lightweight" objektum (egy int mező, konstruktor, getValue() metódus valamint Javaban map miatt equals(), hashCode(), C++-ban map miatt compare metódus) 5000/10000 példányát tárolom map-ban (value) illetve vectorban 100000-szer (minden (második) menetben a tárolót ürítem).
C++-ban pointeres verziók is készültek (vector<Cont*> *v) itt "természetesen" a memória felszabadítást is beleszámolom a futásidőbe (kivéve utolsó menet, bár Javaban nem volt explicit gc() hívás a tesztek között).
Java-ban SortedMap verziók is készültek bár azt ritkábban használom.

Map esetén a kulcsok: int, string és fent vázolt objektum szerepeltek.

Eredmények:

Java vs GCJ: 


                                  sec                 "speedup"
Gcj -O4 -march=k8-sse3
ArrayList:                       140.48                 12.21
Map Integer:                     261.41                  6.56
Map String:                      359.38                  4.77
SortedMap String:               1366.23                  1.26
Map Object:                      200.73                  8.55
SortedMap Object:               1525.89                  1.12

Java -server
ArrayList:                        21.75                 78.88
Map Integer:                      29.53                  58.1
Map String:                       88.67                 19.35
SortedMap String:                246.89                  6.95
Map Object:                       37.53                 45.72
SortedMap Object:                195.36                  8.78

a második oszlopban az 1 jelenti a SortedMap Object idejét gcj-vel (paraméterek nélkül) fordítva, ez volt a leglassabb "java" futás.

Java -server vs GCC -O4 -march=k8-sse3: 


                              Java (sec)   C++ (sec)   Java/C++
ArrayList/vector                 21.75        2.1        0.1
ArrayList/vector*                21.75      62.27       2.86
Map Integer/Map int              29.53      28.88       0.98
Map String/Map string            88.67     1656.2      18.68
SortedMap String/Map string     246.89     1656.2       6.71
Map Object/Map object            37.53      28.88       0.77
Map Object/Map object*           37.53     119.94        3.2
SortedMap Object/Map object     195.36      28.88       0.15
SortedMap Object/Map object*    195.36     119.94       0.61

a harmadik oszlop mutatja a java relatív telesítményét, ha >1 akkor a java gyorsabb.
A vector teszt-ben csak 10%-ot ért el a java pontosabban a C++ feltünően gyors volt. A string tesztnél viszont a C++ volt feltűnően lassú, próbáltam többféle int->string konverziót, a fenti eredményeket ezzel az ajánlott módszerrel értem el. Ez után próbálkoztam nem ajánlott módszerekkel is sprintf (string generálás:3min46sec), illetve a stringstream buffer manipulálásával (

s.rdbuf()->pubsetbuf(buf, 10);

2min17sec).
Ez utóbbi módszerrel mérve (sajnos már nem rendes teszt környezetben single user módban... de "nem futott semmi" és -20-as nice-al): 


Map string2:	                501.35

tehát ha ebből levonjuk a 2 perc string generálást még akkor is jóval lassasbb mint a java 1.5 perces eredménye (még mindig lassabb mint a 4 perces sortedmap eredmény) főleg hogy abban a String.valueOf(i) is benne van.

A hozzászólások alapján még egy kis adalék, azért így jobban néz ki a map C++-ban is.
Végül nem a boost-al hanem -std=c++0x és unordered_map -al mértem a string-et és object-et (-20 -s nice) 


                              Java (sec)   C++ (sec)   Java/C++
Map String/Map string:         88.67        301.05       3.4
Map Object/Map object:         37.53         14.21      0.38

( imp | 2008. 12. 27., szo – 20:49 )

A rosszul teljesítő c++ kódokat megoszthatnád, érdekelne, hogy lehet-e esetleg emberi módszerrel jobban optimalizálni..

igazából a map(string) teljesít nagyon rosszul, meg a pointereket használó kód ezt a kettőt ide is másolom: 


void vecp() {
    vector<Cont*> *v = new vector<Cont*>();
    int count1 = 5000, count2 = 100000;
    struct timeval tvs, tve;
    long long sum = 0;
    gettimeofday(&tvs, NULL);
    for (int i = 0; i < count2; i++) {
        if (i % 2 == 0) {
            for(int k = 0; k < v->size(); k++)
                delete v->at(k);
            v->clear();
        }
        for (int j = 0;j < count1; j++) {
            v->push_back(new Cont(i));
            sum += j;
        }
        sum += i;
    }

    cout << v->size() << "\n";

    for (int j = count1 - 1;j >= 0; j--)
        sum += v->at(j)->getValue();

    cout << sum << "\n";
    gettimeofday(&tve, NULL);
    cout << (tve.tv_sec*1000000 + tve.tv_usec) - (tvs.tv_sec*1000000 + tvs.tv_usec);
}

void ms() {
    map<string, Cont> m;
    int count2 = 5000, count1 = 100000;
    struct timeval tvs, tve;
    long long sum = 0;
    char buff[10];
    stringstream s;
    gettimeofday(&tvs, NULL);
    for (int i = 0; i < count2; i++) {
        for (int j = 0;j < count1; j++) {
            s << i;
            //sprintf(buff, "%d", i);
            m[s.str()]=Cont(j);
            char buf[10] = {'\0','\0','\0','\0','\0','\0','\0','\0','\0','\0',};
            s.rdbuf()->pubsetbuf(buf, 10);
            sum += j;
        }
        sum += i;
    }

    cout << m.size() << "\n";

    for (int j = count2 - 1;j >= 0; j--) {
        stringstream s;
        s << j;
        //sprintf(buff, "%d", j);
        sum += m[s.str()].getValue();
    }

    cout << sum << "\n";
    gettimeofday(&tve, NULL);
    cout << (tve.tv_sec*1000000 + tve.tv_usec) - (tvs.tv_sec*1000000 + tvs.tv_usec);

}

ha van jobb módszered int->string átalakításra arra kiváncsi lennék

Udv, ha nem almat akarsz naranccsal hasonlitani, akkor Java-ban is TreeMap-et kellene hasznalnod. A HashMap konstans idoben tudja kezelni az adatokat, mig a TreeMap logn-es.
Az int->string atalakitas termeszetesen megoldhato nyers for ciklussal is.
(A Cont(x) mit csinal? Nem lehet, hogy az a lassu?)

Ui.: Szerintem igy szebb: for (int j = count2; j-->0;) {...} Es igy csak egyszer lehet elrontani a valtozo nevet. ;)

én nem almákat meg narancsokat akarok hasonlítani, hanem tárolókat ha mondasz stl tárolót ami map és nem rendez akkor azt használom (elég ritkán használok rendezett map-et) viszont a SortedSet sorban megtalálod amit keresel.

A Cont(x) "semmit" sem csinál: 


class Cont {
public:
    Cont(int a = -1):value(a){}
...

ez a tároló osztály amiről beszéltem.

Lehet tevedek, de szerintem az ms()-nel lehetne gyorsitani ugy, hogy:

1. a ciklus-invarians valtozot cikluson kivulre rakod (char buf[10]-et igy 5000*100000-szer inicializalja).

2. a stringstream-nel a buffer beallitasat kicsereled egy irasi pointer allitasra (es valoszinu egy olvasasi pointert is kell akkor mar allitani) a seekg() es seekp() tagfuggvenyekkel. Ilyenkor mar lehet nem is kell a buf[] valtozo.

--
ahan nem

Most vegre linuxos gephez kerultem, es kiprobaltam az ms()-el egy ket dolgot. Meg mindig tartom az 1. felvetest, hogy a ciklus invarians dolgokat rakd cikluson kivulre, en igy tesztelve jelentos sebessegnovekedest tapasztaltam: 


string ix;
for (int i = 0; i < count2; i++) {
	s << i;
	ix = s.str();
	for (int j = 0;j < count1; j++) {
		m[ix] = Cont(j);
		sum += j;
	}
	s.str(string(""));
	sum += i;
}

Igy sokkal kevesebbszer kell az integerre alakitast elvegezni.
Az alabbi kimeneteket kaptam:

eredeti:
5001
24999762497500
492626718

modositott:
5000
25000262492500
322749746

Mivel a tesztkornyezet mas, ez igy onmagaban nem tul relevans sajnos (es a teljes eredeti tesztkod sem volt meg). Ha van idod/kedved kiprobalni igy, kivancsi lennek nalad milyen idovel fut le modositas utan.

--
ahan nem

i++ helyett ++i, egyel kevesebb művelet :) Na ez volt aztán a durva optimalizálás, hínye!

Egyébként érdekes módon ezeket az STL tárolókat Qt-ben mint újraimplementálták, talán nem is véletlenül. Ezt írják:

"These container classes are designed to be lighter, safer, and easier to use than the STL containers. If you are unfamiliar with the STL, or prefer to do things the "Qt way", you can use these classes instead of the STL classes.

The container classes are implicitly shared, they are reentrant, and they are optimized for speed, low memory consumption, and minimal inline code expansion, resulting in smaller executables. In addition, they are thread-safe in situations where they are used as read-only containers by all threads used to access them."

Érdekes lenne ezeket a teszteket QVectorral és a többi Qt konténerrel :) végigverni, de meglehetősen lusta vagyok és ha már programozni kell, akkor inkább a munkát csinálom most. De ahhoz is lusta vagyok.

i++ helyett ++i, egyel kevesebb művelet :)

megoszlanak a vélemények:

preinc.cpp: 


int main(int argc, char** argv) {
    long long sum;
    for(int i=0;i<44444;++i)
      for(int j=0;j<555555;++j)
         sum += j;
}

posinc.cpp: 


int main(int argc, char** argv) {
    long long sum;
    for(int i=0;i<44444;i++)
        for(int j=0;j<555555;j++)
            sum += j;
}

g++ posinc.cpp -o pos -S ;g++ preinc.cpp -o pre -S;diff pre pos
1c1
<       .file   "preinc.cpp"
---
>       .file   "posinc.cpp"

A konvertáláshoz egy ilyet használok:

http://hup.pastebin.com/f6f5a3a23

g++ -O2 -vel ezek lettek az idők:

Conv_0 - 20 sec (nincs konvertálás, üres stringet adunk vissza mindig)
Conv_1 - 686 sec (stringstream)
Conv_2 - 235 sec (a linkelt konvertáló osztály)

A vecp() példában lehetne még optimalizálni memory poolt használva, saját new/delete-tel, de annak nem látom most értelmét, meg a java-ban eleve sokkal jobban meg van csinálva, mint ahogy azt az egyszeri c++ programozó meg tudná csinálni.

C++-ban inkább általánosítottak, a stringstreammel elég sok mindent meg lehet csinálni, cserébe kevésbé gyors. Egyébként érdekességképpen kipróbáltam, hogy a már konvertált értékeket egy map-be raktam, amiből kiderült, hogy ez a fajta konvertálás már egyáltalán nem szűk keresztmetszet.

( aborg | 2008. 12. 27., szo – 21:07 )

Udv, ha nem csak az alapertelmezett tarolokat tartod tesztelesre erdemesnek, akkor Javahoz ajanlom a trove konyvtarat.
A C++ string-je 8 bites adatokkal dolgozik, ha igazan korrekt szeretnel lenni, akkor ugy remlik, hogy a wstring a megoldas, ami mar 16 bites lehet. (Persze nem tudom, hogy az architekturadhoz tartozo gcc-nel milyen a char merete... Es meg az is lehet, hogy nincs wstring. ;) )