Standard container benchmark

[ Dragi Tata @ 03.06.2003. 21:54 ] @

Evo, pre neki dan tata Bjarne je objavio benchmark za standardne C++ kontejnere.

http://groups.google.com/group...=HFnqCB.6Js%40research.att.com

Evo koje sam ja rezultate dobio na VC 7.0 (nije baš čitljivo ali može lako da se importuje npr u Excel):

size array vector with pointers vector with iterators deque list
set multiset
10 3.81 4.35 6.04 18.80 31.39 7.55 14.35
100 2.02 2.10 3.24 11.22 10.73 4.56 8.00
1000 1.76 1.79 2.81 10.13 9.02 4.08 7.06
10000 1.73 1.73 2.60 9.84 10.65 5.14 11.45
100000 1.88 1.97 2.82 10.85 16.44 11.67 26.04
1000000 2.01 2.05 2.91 11.87 13.35 14.00 23.65

[ leka @ 03.06.2003. 23:17 ] @

Code:

dejan@gnu ~/prj/cxx
$ gmake benchmark
g++     benchmark.cc   -o benchmark
dejan@gnu ~/prj/cxx
$ ./benchmark
size    array    vector with pointers    vector with iterators    deque    list    set    multiset
10    2.06    2.17    4.32    6.57    22.25    6.00    9.11
100    1.37    1.42    2.78    4.06    9.74    4.80    6.26
1000    1.44    1.45    2.98    3.85    8.87    4.14    5.24
10000    1.37    1.37    2.57    3.06    12.22    6.34    9.92
100000    1.16    1.14    2.37    2.90    13.53    9.29    10.67
1000000    1.17    1.14    2.33    2.90    11.77    10.96    13.52
dejan@gnu ~/prj/cxx
$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --with-system-zlib --enable-__cxa_atexit --host=i386-redhat-linux
Thread model: posix
gcc version 3.2.2 20030222 (Red Hat Linux 3.2.2-5)

[ leka @ 03.06.2003. 23:19 ] @

Ne pitah da li veci brojevi znace bolje, ili manji ;)

[ Reljam @ 03.06.2003. 23:33 ] @

A na kojim vi to masinama terate?

[ leka @ 04.06.2003. 00:50 ] @

Code:
$ cat /proc/cpuinfo
processor    : 0
vendor_id    : GenuineIntel
cpu family    : 15
model        : 2
model name    : Intel(R) Celeron(R) CPU 2.00GHz
stepping    : 7
cpu MHz        : 1999.979
cache size    : 8 KB
fdiv_bug    : no
hlt_bug        : no
f00f_bug    : no
coma_bug    : no
fpu        : yes
fpu_exception    : yes
cpuid level    : 2
wp        : yes
flags        : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm
bogomips    : 3984.58

[ Dragi Tata @ 04.06.2003. 00:50 ] @

Ja na jednoj kršini, ali nije to poenta. Bitno je da se pokaže koliko pravilan izbor kontejnera ima uticaja na performanse.

[ Dragi Tata @ 04.06.2003. 00:55 ] @

Hehehe, mislio sam da se Bjarnetova rečenica

"The secondary purpose of the benchmark is to encourage compiler and library vendors to
keep improving performance. For example, it is not acceptable that some compilers give
you a sizable penalty for using vector iterators instead of pointer."

odnosi na VC, ali sudeći po Lekinim rezultatima, pre bi se reklo da je u pitanju gcc.

[ leka @ 04.06.2003. 12:25 ] @

Nemanja ja ne razumem sta si hteo reci time :)
Ja ne vidim nista lose u GCC rezultatima - ako ti vidis - objasni. :)

[ leka @ 04.06.2003. 13:30 ] @

Zapravo shvatio sam , gledao si odnos rezultata u "vectors with pointers" i "vectors with iterators" kolonama - ali veruj mi na rec da ono sto sam ja gore dao nije bas najmerodavnije. ILI, moze da se desi da se takve stvari desavaju kod GCC-a v3.2.x! Ovo kazem jer sam odradio jos par benchmark-a sa GCC-om 2.9.x i rezultate cu dati u narednom tekstu.

[ leka @ 04.06.2003. 13:36 ] @

Code:

dejan@cray:~/prj/cxx$ gmake bench
g++     bench.cc   -o bench
dejan@cray:~/prj/cxx$ ./bench
size    array   vector with pointers    vector with iterators   deque   list   s
et      multiset
10      2.8     3.1     3       11      35      11      16
100     1.9     1.9     1.9     6.5     14      7.6     10
1000    1.8     1.8     1.8     5.5     11      6.5     8
10000   1.8     1.8     1.8     5.4     11      6.3     8.8
100000  2.2     2.2     2.2     5.7     14      8.9     11
1000000 2.5     2.5     2.4     5.9     13      10      12
dejan@cray:~/prj/cxx$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-linux/2.95.4/specs
gcc version 2.95.4 20011002 (Debian prerelease)

Test je izvrsen na dvoprocesorskoj PIII masini (1GHz). Interesantno je primetiti da je odnos vector with pointers i vector with iterators maltene isti. Isto pokazuje i sledeci test koji sam napravio na jednoj SUN masini (nastavak u sledecem tekstu).

[ leka @ 04.06.2003. 13:38 ] @

Evo i Solaris testa...

Code:
bash-2.03$ gcc -v
Reading specs from /usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/specs
gcc version 2.95.3 20010315 (release)
bash-2.03$ editor bench.cc
Cannot find default scheme
bash-2.03$ gmake bench
g++     bench.cc   -o bench
bash-2.03$ ./bench
size    array   vector with pointers    vector with iterators   deque   list
set     multiset
10      7       8.4     8.4     26      66      25      35
100     4.6     4.7     4.7     15      28      16      22
1000    3.9     3.9     3.9     13      22      14      18
10000   3.8     3.8     3.8     12      20      13      17
100000  4.1     4.1     4.1     12      25      17      22
1000000 4.2     4.2     4.2     11      22      19      24

U pitanju je SunOS 5.8 Generic_108528-13 sun4u sparc SUNW,UltraAX-i2 .

[ Dragi Tata @ 04.06.2003. 18:17 ] @

Hmmm, ako je verovati ovom dasi, Comeau 4.3 razbija:

http://groups.google.com/group...=bbc8hp%24mk2%241%40sunsite.dk

On Comeau 4.3.0.1 with visual 7.1 backend, libcomo (como /O2 )
--------------------------------------------------------
size array vector with pointers vector with iterators deque
listsetm
ultiset
10 1.52 1.60 1.59 7.27 40.10 5.48 6.94
100 0.76 0.78 0.78 3.69 15.68 3.21 4.06
1000 0.69 0.70 0.70 3.17 12.32 2.43 3.00
10000 0.83 0.78 0.67 3.04 11.15 2.15 3.05
100000 1.00 1.00 1.00 3.34 13.91 3.78 5.34
1000000 1.19 1.19 1.19 3.40 11.07 3.56 4.44

Je li neko radio sa tim kompajlerom?

[ leka @ 04.06.2003. 18:36 ] @

Nikad cuo, pogledacu danas-sutra... Poprilicno sam bizi ovih dana... :(

[ Dragi Tata @ 05.06.2003. 22:29 ] @

Hehehe, u stvari sam se zeznuo. Ono gore su bili rezultati sa /clr opcijom (managed C++). Evo kako izgleda uporedni test za VC6, VC7(native), VC7 (managed) i gcc 3.2

Code:

E:\bjarnebenchmark>bjarnevc6
size    array   vector with pointers    vector with iterators   deque   list
set     multiset
10      1.27    1.35    1.38    3.42    19.97   7.21    13.30
100     0.92    1.02    0.99    2.38    7.18    3.87    6.83
1000    0.86    0.89    0.89    2.17    5.22    3.02    5.91
10000   0.92    0.96    0.95    2.31    7.77    4.26    8.39
100000  1.35    1.40    1.40    2.64    8.53    8.51    10.67
1000000 1.82    1.74    1.84    3.06    19.19   7.77    11.03

E:\bjarnebenchmark>bjarnevc7
size    array   vector with pointers    vector with iterators   deque   list    set     multiset
10      4.04    4.17    4.21    13.06   22.72   6.50    12.11
100     2.18    2.19    2.35    7.91    7.50    3.97    7.10
1000    1.90    1.91    2.05    6.77    5.35    3.11    6.01
10000   1.78    1.82    1.93    6.99    7.02    4.39    9.25
100000  2.04    2.10    2.17    7.32    8.35    6.65    10.57
1000000 2.15    2.19    2.27    7.40    8.87    8.22    12.15

E:\bjarnebenchmark>bjarnevcmanaged
size    array   vector with pointers    vector with iterators   deque   list    set     multiset
10      3.83    4.37    6.13    18.81   31.37   7.58    14.39
100     2.02    2.10    3.25    11.26   10.75   4.57    8.04
1000    1.76    1.80    2.82    10.15   9.03    4.09    7.08
10000   1.74    1.75    2.62    9.93    10.77   5.25    11.46
100000  1.90    1.97    2.85    11.03   16.42   11.70   27.14
1000000 2.02    2.07    2.93    11.94   13.42   14.05   23.66

E:\bjarnebenchmark>bjarnegcc
size    array   vector with pointers    vector with iterators   deque   list    set     multiset
10      2.04    2.12    2.27    4.12    11.55   3.60    6.29
100     1.15    1.14    1.35    2.60    4.19    2.52    4.00
1000    1.01    1.01    1.19    2.19    3.40    2.10    3.17
10000   1.12    1.08    1.20    2.15    4.37    2.33    4.60
100000  1.31    1.32    1.49    2.40    6.16    4.10    5.81
1000000 1.85    1.86    2.03    2.96    5.28    4.14    5.52

E:\bjarnebenchmark>dir *.exe
Volume in drive E is 19gb
Volume Serial Number is DC54-815F

Directory of E:\bjarnebenchmark

06/03/2003  02:36p             485,933 bjarnegcc.exe
06/05/2003  09:46a             126,976 bjarnevc6.exe
06/05/2003  09:55a             196,608 bjarnevc7.exe
06/02/2003  12:59p             348,160 bjarnevcmanaged.exe
               4 File(s)      1,157,677 bytes
               0 Dir(s)  15,239,086,080 bytes free

Po ovome, VC6 ispada još i najbolji - moram da još malo proverim VC 7 - nemoguće da su ga baš toliko unazadili.

Nego, onaj gcc pravi malo "debele" exe fajlove, a Leko? :)

[ filmil @ 05.06.2003. 23:00 ] @

Tata, jesi li skinuo debug info sa programa?

Code:

strip bjarnegcc.exe

[ Dragi Tata @ 06.06.2003. 00:16 ] @

Nisam Filipe. Neznanje, šta ćeš. Kad ga "stripnem" onda je 233,984.

Uzgred, koristio sam optimizaciju -O2.

[ Dragi Tata @ 06.06.2003. 00:33 ] @

A evo ga i sa -O3:

Code:

E:\bjarnebenchmark>bjarnegcc
size    array   vector with pointers    vector with iterators   deque   list    set     multiset
10      1.62    1.65    2.08    4.00    12.19   3.59    5.97
100     1.03    1.03    1.34    2.58    4.52    2.53    3.77
1000    0.93    0.94    1.19    2.18    3.63    2.10    3.02
10000   1.05    1.03    1.20    2.15    4.54    2.33    4.46
100000  1.38    1.39    1.64    2.61    6.84    4.46    6.20
1000000 1.80    1.81    2.00    2.96    5.34    4.11    5.40

Sve u svemu, uopšte nije loše, moram da priznam.

[ Reljam @ 06.06.2003. 00:52 ] @

Evo mogu ja da posaljem VS2K3 verziju za poredjenje, ako DT hoce da izvrti.

[ Dragi Tata @ 06.06.2003. 01:16 ] @

Pošalji čim stigneš.

[ filmil @ 06.06.2003. 02:37 ] @

Tata, imaš li vremena da daš neki kvalitativni komentar gornjih rezultata da ne bismo ostali samo na

brojeva, i da se ne bi svelo samo na to čiji je (rezultat) veći?

Zahvalan,
f

[ Dragi Tata @ 06.06.2003. 02:58 ] @

Evo kako radi VC 7.1 (hvala Relji)

Code:

E:\bjarnebenchmark>BjarneVS2K3.exe
size    array   vector with pointers    vector with iterators   deque   list
set     multiset
10      3.48    3.65    4.33    12.33   23.91   6.23    12.32
100     1.88    1.89    2.19    7.41    7.40    3.73    6.81
1000    1.65    1.67    1.89    6.28    5.26    2.86    5.74
10000   1.50    1.51    1.69    6.42    6.83    4.15    8.66
100000  1.78    1.77    1.95    6.83    8.26    6.45    9.80
1000000 1.89    1.88    2.03    6.92    8.80    8.01    11.87

A što se tiče komentarisanja, prihvatam, samo ne mogu baš sada. Javiću se sutra.

[ leka @ 07.06.2003. 15:34 ] @

Sutra je odavno prošlo...

[ Dragi Tata @ 09.06.2003. 21:07 ] @

... a meni je crk'o kućni kompjuter, pa moram da se javim sa posla. Čim uhvatim vremena, poslaću komentar.

[ leka @ 10.06.2003. 16:49 ] @

U USA firme jos uvek koriste Windows? - Ja sam mislio da su sve vec presle na Linux ;)

[ Dragi Tata @ 10.06.2003. 18:00 ] @

Linux? Hahahahahaha....

[ Dragi Tata @ 10.06.2003. 19:00 ] @

Elem, da budemo malo ozbiljni.

Cilj testa je da se uporede performanse standardnih kontejnera. Za 7 različitih vrsta kontejnera (C niz, vector sa pointerom kao iteratorom, vector sa "default" iteratorom, deque, list, set i multiset) izvršeno je uklanjanje duplikata iz zadate sekvence double brojeva. Način na koji je to urađeno naravno zavisi od kontejnera: tako je za set dovoljno da se inicijalizuje i on je automatski eliminisao duplikate - vector mora da se sortira pa da se pozove funkcija unique.

Razni kontejneri predstavljaju kolone matrice. Redove predstavljaju različite veličine sekvence.

Rezultati nam govore sledeće: nizovi (C nizovi i obe vrste vector-a) su se najbolje pokazali, dok je multiset imao najslabije rezultate. Kompajler sa idealnom optimizacijom STL-a bi morao da za C-nizove i obe vrste vektora proizvede identičan mašinski kod, ali ako je suditi prema rezultatima jedino možda Comeau 4.3 ispunjava ovaj zadatak.

Naravoučenije: ako nam je potrebno da radimo sa nekom sortiranom strukturom podataka, često ćemo dobiti bolje performanse ako koristimo sortirani vector, nego recimo set (koji je implementiran preko stabla i samim tim uvek sortiran). Priznajem da je ovo za mene otkrovenje, jer sam do sad po inerciji uvek koristio set u takvim situacijama.