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.

( 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. ;) )