dlaczego valarray jest taki wolny?

Question

Przepraszam za moje pytanie do Valarray ponownie. Próbuję go użyć, ponieważ jest bardzo podobny do Matlaba podczas pracy z macierzami wektorowymi &. Najpierw sprawdziłem wydajność i stwierdziłem, że valarray nie może osiągnąć wydajności zadeklarowanej w języku programowania C++ książki stroustrup.

Program testowy faktycznie pomnożył 5M dubletów. Pomyślałem, że c = a * b będzie co najmniej porównywalne do mnożenia elementu podwójnej pętli for, ale całkowicie się mylę. Próbowałem na kilku komputerach i vc6.0 i vs2008.

Nawiasem mówiąc, ja testowałem na Matlab używając następującego kodu:

len=5*1024*1024; 
a=rand(len,1);b=rand(len,1);c=zeros(len,1); 
tic;c=a.*b;toc; 

a wynik jest 46ms. Ten czas nie jest wysoką precyzją, działa tylko jako odniesienie.

Kod jest:

#include <iostream> 
#include <valarray> 
#include <iostream> 
#include "windows.h" 

using namespace std ; 
SYSTEMTIME stime; 
LARGE_INTEGER sys_freq; 

double gettime_hp(); 

int main() 
{ 
    enum { N = 5*1024*1024 }; 
    valarray<double> a(N), b(N), c(N) ; 
    QueryPerformanceFrequency(&sys_freq); 
    int i,j; 
    for( j=0 ; j<8 ; ++j) 
    { 
     for( i=0 ; i<N ; ++i) 
     { 
      a[i]=rand(); 
      b[i]=rand(); 
     } 

     double* a1 = &a[0], *b1 = &b[0], *c1 = &c[0] ; 
     double dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c1[i] = a1[i] * b1[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "double operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     c = a*b ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c[i] = a[i] * b[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray[i] operator* " << dtime<< " ms\n" ; 

     cout << "------------------------------------------------------\n" ; 
    } 
} 

double gettime_hp() 
{ 
    LARGE_INTEGER tick; 
    extern LARGE_INTEGER sys_freq; 
    QueryPerformanceCounter(&tick); 
    return (double)tick.QuadPart*1000.0/sys_freq.QuadPart; 
} 

Wyniki bieżących: (tryb uwalniania z maksymalną optymalizację prędkości) tryb

double operator* 52.3019 ms 
valarray operator* 128.338 ms 
valarray[i] operator* 43.1801 ms 
------------------------------------------------------ 
double operator* 43.4036 ms 
valarray operator* 145.533 ms 
valarray[i] operator* 44.9121 ms 
------------------------------------------------------ 
double operator* 43.2619 ms 
valarray operator* 158.681 ms 
valarray[i] operator* 43.4871 ms 
------------------------------------------------------ 
double operator* 42.7317 ms 
valarray operator* 173.164 ms 
valarray[i] operator* 80.1004 ms 
------------------------------------------------------ 
double operator* 43.2236 ms 
valarray operator* 158.004 ms 
valarray[i] operator* 44.3813 ms 
------------------------------------------------------ 

debugowanie z samej optymalizacji:

double operator* 41.8123 ms 
valarray operator* 201.484 ms 
valarray[i] operator* 41.5452 ms 
------------------------------------------------------ 
double operator* 40.2238 ms 
valarray operator* 215.351 ms 
valarray[i] operator* 40.2076 ms 
------------------------------------------------------ 
double operator* 40.5859 ms 
valarray operator* 232.007 ms 
valarray[i] operator* 40.8803 ms 
------------------------------------------------------ 
double operator* 40.9734 ms 
valarray operator* 234.325 ms 
valarray[i] operator* 40.9711 ms 
------------------------------------------------------ 
double operator* 41.1977 ms 
valarray operator* 234.409 ms 
valarray[i] operator* 41.1429 ms 
------------------------------------------------------ 
double operator* 39.7754 ms 
valarray operator* 234.26 ms 
valarray[i] operator* 39.6338 ms 
------------------------------------------------------ 

Answer 1

Podejrzewam, że powód c = a*b jest o wiele wolniejszy niż wykonywanie operacji elementu w tym samym czasie operator musi przydzielić pamięć, aby umieścić wynik w, a następnie zwraca tę wartość przez wartość.

Nawet jeśli „swaptimization” służy do wykonywania kopii, że funkcja ma jeszcze napowietrznej

• przydzielenie nowego bloku do powstałego valarray
• inicjowania nowy valarray (możliwe, że ten może być zoptymalizowane dalej)
• wprowadzanie wyników do nowego valarray
• przywoływania z pamięci na nową valarray jak to jest inicjowana lub zestawu z rezultatem val tości
• dealokując starą valarray że zostanie zastąpiony przez wynik

Answer 2

Właśnie próbowałem go na systemie Linux x86-64 (Sandy Bridge CPU):

gcc 4.5.0:

double operator* 9.64185 ms 
valarray operator* 9.36987 ms 
valarray[i] operator* 9.35815 ms 

Intel ICC 12.0.2:

double operator* 7.76757 ms 
valarray operator* 9.60208 ms 
valarray[i] operator* 7.51409 ms 

W obu cas es Właśnie użyłem -O3 i żadnych innych flag związanych z optymalizacją.

Wygląda na to, że kompilator MS C++ i/lub implementacja valarray suck.

---

Oto kod PO za zmodyfikowane dla Linux:

#include <iostream> 
#include <valarray> 
#include <iostream> 
#include <ctime> 

using namespace std ; 

double gettime_hp(); 

int main() 
{ 
    enum { N = 5*1024*1024 }; 
    valarray<double> a(N), b(N), c(N) ; 
    int i,j; 
    for( j=0 ; j<8 ; ++j) 
    { 
     for( i=0 ; i<N ; ++i) 
     { 
      a[i]=rand(); 
      b[i]=rand(); 
     } 

     double* a1 = &a[0], *b1 = &b[0], *c1 = &c[0] ; 
     double dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c1[i] = a1[i] * b1[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "double operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     c = a*b ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c[i] = a[i] * b[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray[i] operator* " << dtime<< " ms\n" ; 

     cout << "------------------------------------------------------\n" ; 
    } 
} 

double gettime_hp() 
{ 
    struct timespec timestamp; 

    clock_gettime(CLOCK_REALTIME, &timestamp); 
    return timestamp.tv_sec * 1000.0 + timestamp.tv_nsec * 1.0e-6; 
} 

Answer 3

Mam kompilacji w wersji x64, VS 2010. Zmieniłem kod bardzo nieznacznie:

double* a1 = &a[0], *b1 = &b[0], *c1 = &c[0] ; 
    double dtime=gettime_hp(); 
    for( i=0 ; i<N ; ++i) a1[i] *= b1[i] ; 
    dtime=gettime_hp()-dtime; 
    cout << "double operator* " << dtime << " ms\n" ; 

    dtime=gettime_hp(); 
    a *= b; 
    dtime=gettime_hp()-dtime; 
    cout << "valarray operator* " << dtime << " ms\n" ; 

    dtime=gettime_hp(); 
    for( i=0 ; i<N ; ++i) a[i] *= b[i] ; 
    dtime=gettime_hp()-dtime; 
    cout << "valarray[i] operator* " << dtime<< " ms\n" ; 

    cout << "------------------------------------------------------\n" ; 

Tutaj można zobacz, że użyłem * = zamiast c = a * b. W nowocześniejszych bibliotekach matematycznych stosowane są bardzo złożone mechanizmy szablonów wypowiedzi, które eliminują ten problem. W tym przypadku otrzymałem bardzo nieznacznie szybsze wyniki z valarray, chociaż prawdopodobnie dlatego, że zawartość była już w pamięci podręcznej. Koszty ogólne, które widzisz, są po prostu zbędnymi tymczasowymi i nic nieodłącznie związanego z walvarą, a konkretnie - zobaczysz to samo zachowanie z czymś takim, jak std::string.

Answer 4

W końcu udało mi się to przez zastosowanie opóźnionej oceny. Kod może być brzydki, ponieważ dopiero zaczynam uczyć się tych zaawansowanych pojęć w C++. Popraw mnie, jeśli masz lepszy pomysł, proszę. Wielkie dzięki za twoją pomoc. Oto kod:

#include <iostream> 
#include <valarray> 
#include <iostream> 
#include "windows.h" 

using namespace std ; 
SYSTEMTIME stime; 
LARGE_INTEGER sys_freq; 

double gettime_hp(); 
//to improve the c=a*b (it will generate a temp first, assigned to c and delete the temp 
//which causes the program really slow 
//the solution is the expression template and let the compiler to decide when all the expression is known 
//delayed evaluation 
//typedef valarray<double> Vector; 
class Vector; 
class VecMul 
{ 
public: 
    const Vector& va; 
    const Vector& vb; 
    //Vector& vc; 
    VecMul(const Vector& v1,const Vector& v2):va(v1),vb(v2){} 
    operator Vector(); 
}; 

class Vector:public valarray<double> 
{ 
    valarray<double> *p; 
public: 
    explicit Vector(int n) 
    { 
     p=new valarray<double>(n); 
    } 
    Vector& operator=(const VecMul &m) 
    { 
     for(int i=0;i<m.va.size();i++) (*p)[i]=(m.va)[i]*(m.vb)[i];//ambiguous 
     return *this; 
    } 
    double& operator[](int i) const {return (*p)[i];} //const vector_type[i] 
    int size()const {return (*p).size();} 
}; 



inline VecMul operator*(const Vector& v1,const Vector& v2) 
{ 
    return VecMul(v1,v2); 
} 


int main() 
{ 
    enum { N = 5*1024*1024 }; 
    Vector a(N), b(N), c(N) ; 
    QueryPerformanceFrequency(&sys_freq); 
    int i,j; 
    for( j=0 ; j<8 ; ++j) 
    { 
     for( i=0 ; i<N ; ++i) 
     { 
      a[i]=rand(); 
      b[i]=rand(); 
     } 

     double* a1 = &a[0], *b1 = &b[0], *c1 = &c[0] ; 
     double dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c1[i] = a1[i] * b1[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "double operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     c = a*b ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray operator* " << dtime << " ms\n" ; 

     dtime=gettime_hp(); 
     for( i=0 ; i<N ; ++i) c[i] = a[i] * b[i] ; 
     dtime=gettime_hp()-dtime; 
     cout << "valarray[i] operator* " << dtime<< " ms\n" ; 

     cout << "------------------------------------------------------\n" ; 
    } 
} 

double gettime_hp() 
{ 
    LARGE_INTEGER tick; 
    extern LARGE_INTEGER sys_freq; 
    QueryPerformanceCounter(&tick); 
    return (double)tick.QuadPart*1000.0/sys_freq.QuadPart; 
} 

Wynik działa w Visual studio jest:

double operator* 41.2031 ms 
valarray operator* 43.8407 ms 
valarray[i] operator* 42.49 ms 

Answer 5

Sensem valarray ma być szybki na maszynach wektorów, które maszyny x86 po prostu nie mają. Dobrym realizacja na maszynie nonvector powinien być w stanie dopasować wydajność, że można dostać coś jak
for (i=0; i < N; ++i) c1[i] = a1[i] * b1[i];

i złego oczywiście nie będzie. O ile w sprzęcie nie ma czegoś, co przyspieszy równoległe przetwarzanie, będzie to prawie najlepsze, co możesz zrobić.

Answer 6

hmm..I przetestowany Blitz i jego samo jak valarray..and więcej blitz ++ [] operatpr jest bardzo powolny

#include <blitz/array.h> 
    #include <iostream> 
    #ifdef WIN32 
    #include "windows.h" 
    LARGE_INTEGER sys_freq; 
    #endif 
    #ifdef LINUX 
    <ctime> 
    #endif 
     using namespace std ; 
    SYSTEMTIME stime; 


    __forceinline double gettime_hp(); 
    double gettime_hp() 
    { 
    #ifdef WIN32 
     LARGE_INTEGER tick; 
     extern LARGE_INTEGER sys_freq; 
     QueryPerformanceCounter(&tick); 
     return (double)tick.QuadPart*1000.0/sys_freq.QuadPart; 
    #endif 
    #ifdef LINUX 
     struct timespec timestamp; 

     clock_gettime(CLOCK_REALTIME, &timestamp); 
     return timestamp.tv_sec * 1000.0 + timestamp.tv_nsec * 1.0e-6; 
    #endif 
    } 
    BZ_USING_NAMESPACE(blitz) 

    int main() 
    { 
     int N = 5*1024*1024 ; 

     // Create three-dimensional arrays of double 
     Array<double,1> a(N), b(N),c(N); 


     int i,j; 
    #ifdef WIN32 
     QueryPerformanceFrequency(&sys_freq); 
    #endif 
     for( j=0 ; j<8 ; ++j) 
     { 
      for( i=0 ; i<N ; ++i) 
      { 
       a[i]=rand(); 
       b[i]=rand(); 
      } 

      double* a1 = a.data() , *b1 = b.data(), *c1 = c.data() ; 
      double dtime=gettime_hp(); 
      for( i=0 ; i<N ; ++i) c1[i] = a1[i] * b1[i] ; 
      dtime=gettime_hp()-dtime; 
      cout << "double operator* " << dtime << " ms\n" ; 

      dtime=gettime_hp(); 
      c = a*b ; 
      dtime=gettime_hp()-dtime; 
      cout << "blitz operator* " << dtime << " ms\n" ; 

      dtime=gettime_hp(); 
      for( i=0 ; i<N ; ++i) c[i] = a[i] * b[i] ; 
      dtime=gettime_hp()-dtime; 
      cout << "blitz[i] operator* " << dtime<< " ms\n" ; 

      cout << "------------------------------------------------------\n" ; 
     } 
    } 

Answer 7

myślę odpowiedź Michaela Burr jest prawo. Możliwe, że możesz utworzyć wirtualny typ jako typ zwracanej wartości operatora + i ponownie załadować innego operatora = dla tego typu wirtualnego, jak operator = (typ wirtualny & v) {& valarray = & v; v = NULL;} (w przybliżeniu mówiąc). Oczywiście, trudno jest zrealizować pomysł na walvarę. Ale kiedy tworzysz nową klasę, możesz wypróbować ten pomysł. A następnie, wydajność operatora + jest prawie taka sama jak operator + =