Newsgroup: it.comp.lang.c++
Titolo: vectors vs arrays

Il codice non è completamente portabile comunque, se potete, provatelo. 
Da me, a meno di errori, gli arrays sono molto più veloci dei vettori.
---
#include <iostream>
#include <vector>
#include "windows.h"
void use_vectors(unsigned N)
{
     srand(0x12345678);
     std::vector<char> v1(N), v2(N), v3(N);
     for (unsigned i = 0; i < N; ++i)
     {
         v1[i] = (char)rand();
         v2[i] = (char)rand();
         v3[i] = (char)rand();
     }
     int sum = 0;
     for (unsigned i = 0; i < N; ++i)
     {
         unsigned l = rand()%N;
         for (unsigned i = 0; i <= l; ++i)
             v1[i] += v2[i]+v3[i];
         sum += v1[rand()%N];
     }
     std::cout << sum << std::endl;
}
void use_arrays(unsigned N)
{
     srand(0x12345678);
     char *v1 = new char[N];
     char *v2 = new char[N];
     char *v3 = new char[N];
     for (unsigned i = 0; i < N; ++i)
     {
         v1[i] = (char)rand();
         v2[i] = (char)rand();
         v3[i] = (char)rand();
     }
     int sum = 0;
     for (unsigned i = 0; i < N; ++i)
     {
         unsigned l = rand()%N;
         for (unsigned i = 0; i <= l; ++i)
             v1[i] += v2[i]+v3[i];
         sum += v1[rand()%N];
     }
     std::cout << sum << std::endl;
     delete[] v1;
     delete[] v2;
     delete[] v3;
}
int main()
{
     DWORD t1, t2, t3;
     unsigned N;
     std::cout << "elements = ";
     std::cin >> N;
     unsigned T;
     std::cout << "loops = ";
     std::cin >> T;
     std::cout << std::endl;
     DWORD ta = 0;
     DWORD tv = 0;
     // Pre-loop.
     use_arrays(N);
     use_vectors(N);
     while (T--)
     {
         t1 = GetTickCount();
         use_arrays(N);
         t2 = GetTickCount();
         use_vectors(N);
         t3 = GetTickCount();
         ta += t2-t1;
         tv += t3-t2;
     }
     std::cout << std::endl;
     std::cout << "------------" << std::endl;
     std::cout << "arrays = " << ta << std::endl;
     std::cout << "vectors = " << tv << std::endl;
     std::cout << "------------" << std::endl;
}
---
Kiuhnm

 Da me, a meno di errori, gli arrays sono molto più veloci dei vettori.
Ops... gli "array" ;)
Kiuhnm

 me, a meno di errori, gli arrays sono molto piů veloci dei vettori.
Dipende da come č implementata la libreria standard. Io su tre compilatori ne 
ho trovato uno (BCC55) in cui gli array sono piů veloci dei vector e due 
(DJGPP e VC++Toolkit2003) in cui sono piů veloci i vector (ho sostituito 
GetTickCount() con std::clock() per essere portabile).
EMG
--
EMAG Software Homepage:     
http://www.emagsoftware.it
The EMG's ZX-Spectrum Page: 
http://www.emagsoftware.it/spectrum
The Best of Spectrum Games: 
http://www.emagsoftware.it/tbosg
The EMG Music page:         
http://www.emagsoftware.it/emgmusic
 

 Da me, a meno di errori, gli arrays sono molto più veloci dei vettori.
Sulla mia piattaforma (Linux + GCC 3.3) non riscontro differenze
significative se compilo con il massimo delle ottimizzazioni.
 
 g++ -O6 arrayvsvector.cpp
 maxim@afton:~$ ./a.out
 elements = 25000
 loops = 2
 -610
 -610
 -610
 -610
 -610
 -610
 ------------
 arrays = 145
 vectors = 148
 -----------
Senza ottimizzazioni, 'use_arrays' è un ordine di grandezza più veloce.
Max

 }
All'interno della misura hai inserito anche delle istruzioni che non
andrebbero conteggiate (es: i tempi di allocazione/deallocazione). Io
proverei a fare un test piu' accurato, e magari controllare i flag di
ottimizzazione.
In teoria, se la libreria standard e' implementata con cognizione e il
compilatore ottimizza in modo decente, i tempi dovrebbero essere molto
simili.
Ciao,
Francesco.

 andrebbero conteggiate (es: i tempi di allocazione/deallocazione).
E chi lo dice che non adrebbero conteggiate?
Kiuhnm

Kiuhnm wrote:
[...]
Con 50000 elementi e 5 cicli, ottengo (13797, 37859) con il MSVC8 e 
(21469, 18968) con il Dev-C++.
Kiuhnm


Si, ma con che ottimizzazioni?
  bye
	av.

  g++ -O6 arrayvsvector.cpp
il massimo e' -O3.  valori superiori non hanno effetto.
[OT] mi ricordo una puntata di 'star trek' in cui il comandante ordina
     a scotty (l'ingegnere di macchina, che parla con un pesante
     accento scozzese) qualcosa come "porta l'energia a dieci unita'
     sopra il massimo"; scotty muove qualche leva, poi grida "ecco
     fatto!".
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy              ROT13: 
ybe...@cq.vasa.vg

 18968) con il Dev-C++.
Appunto.


 Si, ma con che ottimizzazioni?
Ho abilitato in entrambi i casi le ottimizzazioni piů comuni (livello 
massimo dove possibile, ma niente MMX, ecc...).
Kiuhnm


Ho scoperto l'arcano, ispirato da un thread di questi giorni su
comp.lang.c++.moderated a proposito delle scarse prestazioni della
libreria standard di VC++2005.
In pratica di default sono attivi controlli di accesso
indipendentemente dalle opzioni di ottimizzazione. Mettendo in testa al
tuo sorgente la seguente define:
#define _SECURE_SCL 0
ottengo
arrays = 8779
vectors = 8299
Ciao,
Nicola

 vectors = 8299
Io invece ottengo (11624, 19845).
E' già meglio di (11613, 31528)!
I due cicli sono:
(array)
00401170  mov         ecx,dword ptr [esp+20h]
00401174  mov         edx,dword ptr [esp+28h]
00401178  add         ecx,eax
0040117A  mov         dl,byte ptr [ecx+edx]
0040117D  add         dl,byte ptr [ecx]
0040117F  add         eax,1
00401182  add         byte ptr [eax-1],dl
00401185  sub         esi,1
00401188  jne         use_arrays+0B0h (401170h)
(vector)
00401700  mov         edx,dword ptr [esp+20h]
00401704  mov         dl,byte ptr [edx+eax]
00401707  mov         ebx,dword ptr [esp+30h]
0040170B  add         dl,byte ptr [ebx+eax]
0040170E  mov         ecx,dword ptr [esp+40h]
00401712  add         byte ptr [ecx+eax],dl
00401715  add         eax,1
00401718  cmp         eax,esi
0040171A  jbe         use_vectors+0D0h (401700h)
Il primo è più veloce, ma direi che si tratta di un "caso".
In particolare, nel secondo c'è un accesso alla memoria in più.
Se sostituisco i char con gli int, ottengo (13109, 11360).
Comunque questo fa capire che scrivere codice asm a mano per i cicli è 
ancora molto utile. Non ci si può affidare ciecamente all'ottimizzatore, 
date le notevoli fluttuazioni di performance.
Kiuhnm

ancora molto utile.
Ma per favore!!

 Kiuhnm

 dell'architettura hardware.
Non serve. Dato che il codice da ottimizzare è spesso molto piccolo, è 
sufficiente usare un metodo genetico. Si selezionano n versioni 
(relative ad n cpu diverse) e quindi si seleziona quella migliore a 
run-time.
Kiuhnm

processori)
I processori evolvono continuamente, non si può star al passo con la
loro tecnologia, alla ricerca di una tecnica migliore, perché domani
sicuramente un altro processore ci avrà superati.  D'altronde, con
tutte le logiche di "prediction", con tutti i meccanismi di "cache"
che hanno, arrivare a fare meglio per via manuale è veramente dura.

 elaborazioni.
O limitarsi ad usare una qualche libreria di calcolo in C e quindi in
C++.
-- 
blog:  
http://www.akropolix.net/rik0/blogs
 | Uccidete i filosofi,
site:  
http://www.akropolix.net/rik0/
      | tenetevi riso e
forum: 
http://www.akropolix.net/forum/
     | bacchette per voi.