почему valarray такой медленный?

19

Простите за мой вопрос к valarray снова. Я пытаюсь использовать его, так как он очень похож на matlab при работе с вектором & amp; матрицы. Сначала я сделал некоторую проверку производительности и обнаружил, что valarray не может достичь производительности, объявленной stroustrup, как в книге «Язык программирования c ++».

Тестовая программа на самом деле сделала 5M умножения двойников. Я думал, что c = a * b будет, по крайней мере, сравнимо с умножением элемента цикла типа double, но я совершенно не прав. Пробовал на нескольких компьютерах и vc6.0 и vs2008.

Кстати, я тестировал на Matlab, используя следующий код:

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

и результат 46мс. На этот раз нет высокой точности, работает только как ссылка.

Код:

#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;
}

Результаты выполнения: (режим выпуска с оптимизацией максимальной скорости)

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
------------------------------------------------------

режим отладки с такой же оптимизацией:

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
------------------------------------------------------
    
задан shangping 27.07.2011 в 22:27
источник
  • Запустил ли исполняемый файл? или вы попробовали его в отладчике (через визуальную студию)? –  Yochai Timmer 27.07.2011 в 22:34
  • Какие настройки оптимизации вы используете? –  Alan Stokes 27.07.2011 в 22:37
  • Там нет разницы ни в отладчике, ни в exe –  shangping 27.07.2011 в 22:38
  • VC6? В самом деле? Это 13 лет и предшествует стандарту. –  Alan Stokes 27.07.2011 в 22:38
  • В GCC 4.6.1 с -flto -O3 -march = native -std = c ++ 0x, я получаю почти идентичную производительность для всех трех случаев с небольшим увеличением от первого до третьего. –  Kerrek SB 27.07.2011 в 22:56
Показать остальные комментарии

7 ответов

12

Я подозреваю, что причина c = a*b намного медленнее, чем выполнение операций элемента за раз, в том, что

template<class T> valarray<T> operator*
    (const valarray<T>&, const valarray<T>&);
Оператор

должен выделить память для помещения результата, а затем вернуть его по значению.

Даже если «swaptimization» используется для выполнения копирования, эта функция по-прежнему имеет накладные расходы

  • выделение нового блока для результирующего valarray
  • инициализация нового valarray (возможно, это может быть оптимизировано)
  • положить результаты в новый valarray
  • листание в памяти для нового valarray , когда он инициализируется или задается со значениями результата
  • освобождает старый valarray , который заменяется результатом
ответ дан Michael Burr 27.07.2011 в 22:46
  • Я только что искал, он фактически возвращает ссылку: template <class_Ty> inline valarray <_Ty> & operator * = (valarray <_Ty> & _L, const _Ty & _R) {_VALGOP2 (* = _R); } –  shangping 27.07.2011 в 22:57
  • В объявлении, опубликованном в комментарии выше, есть два отличия от того, что будет использоваться в коде, размещенном в вопросе: 1) operator * = отличается от использования оператора * (), за которым следует оператор = (), и 2) это объявление для оператора * =, которое принимает скалярный аргумент для умножения ванармы на –  Michael Burr 27.07.2011 в 23:02
  • Майкл, вы правы, я слишком спешу –  shangping 27.07.2011 в 23:09
  • Майкл, согласно анализу, мы не имеем возможности использовать valarray, если производительность необходима. Однако, согласно книге, этот класс специально разработан для повышения производительности. Не могли бы вы дать мне несколько моментов? Любой другой метод, позволяющий мне обрабатывать массивы в целом так же, как valarray в c ++? благодаря –  shangping 27.07.2011 в 23:13
  • Вспышка новостей: арифметика valarray разрешена, но не требуется использовать шаблоны выражений (en.wikipedia.org/wiki/Expression_templates). Использование шаблонов выражений может полностью устранить временные проблемы в проблеме OP и, таким образом, полностью исключить выделение кучи и освобождение для выражения c = a * b. Очевидно, что gcc делает это (и немного исправленный libc ++), а MS C ++ - нет. –  Howard Hinnant 28.07.2011 в 01:47
Показать остальные комментарии
23

Я только что попробовал это в системе Linux x86-64 (процессор Sandy Bridge):

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

В обоих случаях я просто использовал -O3 и никаких других флагов, связанных с оптимизацией.

Похоже, компилятор MS C ++ и / или реализация valarray - отстой.

Вот код ОП, модифицированный для 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;
}
    
ответ дан Paul R 27.07.2011 в 23:24
  • Ницца - просто для справки, можете ли вы добавить параметры, используемые в сборке (сегодня я могу поиграть с этим материалом ...) –  Michael Burr 28.07.2011 в 00:27
  • +1. Я выполнил этот тест в реализации libc ++. Это было не так медленно, как MS, но было не так быстро, как gcc (это была примерно такая же скорость, как и для ICC). Оказывается, у меня отсутствовал оператор присваивания ключей в движке шаблона выражения. Добавлено это. Теперь libc ++ работает так же быстро, как gcc. К OP: Спасибо за тест скорости! (+1 на вопрос тоже) :-) –  Howard Hinnant 28.07.2011 в 01:24
  • Спасибо за то, что оба - я добавил реплики компилятора (только -O3 в обоих случаях), а также добавил код OP, измененный для Linux, который я использовал для этих тестов. –  Paul R 28.07.2011 в 08:55
4

Я, наконец, получил это с помощью отложенной оценки. Код может быть уродливым, так как я только начинаю изучать эти продвинутые концепции c ++. Поправьте меня, если у вас есть идея получше, пожалуйста. Большое спасибо за вашу помощь. Вот код:

#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;
}

Результат выполнения в Visual Studio:

double operator* 41.2031 ms
valarray operator* 43.8407 ms
valarray[i] operator* 42.49 ms
    
ответ дан shangping 28.07.2011 в 08:18
  • Почему у вашего класса Vector есть два объекта valarray? Один как базовый класс, а другой выделен на кучу? Кажется, вы используете только тот, что есть в куче, но для этого требуются дополнительные ассигнования. Просто используйте базовый класс! –  Jonathan Wakely 06.04.2018 в 01:33
4

Смысл valarray в том, чтобы работать на векторных машинах быстрее, чем на x86-машинах. Хорошая реализация на машине без вектора должна быть в состоянии соответствовать производительности, которую вы получаете с чем-то вроде
for (i=0; i < N; ++i) c1[i] = a1[i] * b1[i];

и плохой конечно не будет. Если в оборудовании нет чего-то для ускорения параллельной обработки, это будет очень близко к лучшим из того, что вы можете сделать.

    
ответ дан Leo Bellantoni 06.09.2011 в 23:12
1

Я компилирую в выпуске x64, VS 2010. Я немного изменил ваш код:

    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" ;

Здесь вы можете видеть, что я использовал * = вместо c = a * b . В более современных математических библиотеках используются очень сложные механизмы шаблонов выражений, которые устраняют эту проблему. В этом случае я получил результаты от valarray немного быстрее, хотя, возможно, это только потому, что содержимое уже было в кеше. Затраты, которые вы видите, являются просто избыточными временными файлами и ничем не присущими valarray, в частности, вы увидите то же поведение с чем-то вроде std::string .

    
ответ дан Puppy 27.07.2011 в 23:32
  • Я проверил ваши результаты. Однако это изменение незначительно. Множество рецептурных выражений не всегда можно сделать, используя * =, + = / = –  shangping 28.07.2011 в 00:19
  • @shangping: в этом случае, если вы выделили новый массив результатов для каждой из необходимых временных переменных, вы увидите аналогичное замедление для double, как для valarray. –  Puppy 28.07.2011 в 10:58
  • +1 в качестве одного года празднования этого сообщения –  Johan Lundberg 27.07.2012 в 16:51
  • «В более современных математических библиотеках используются очень сложные механизмы шаблонов выражений, которые устраняют эту проблему». А также в высококачественных реализациях std :: valarray. –  Jonathan Wakely 06.04.2018 в 01:38
-1

хм .. я тестировал блиц и тот же, что и у valarray .. и еще блиц ++ [] operatpr очень медленный

 #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" ;
        }
    }
    
ответ дан user2778496 14.09.2013 в 06:48
  • ... и каков был результат? –  quant 11.08.2014 в 06:50
-1

Я думаю, что ответ Майкла Барра правильный. И может быть, вы можете создать виртуальный тип как тип, возвращаемый значением оператора +, и перезагрузить другой оператор = для этого виртуального типа, например operator = (виртуальный тип & amp; v) {& amp; valarray = & amp; v; v = NULL; }(грубо говоря). Конечно, сложно реализовать идею на valarray. Но когда вы создаете новый класс, вы можете попробовать эту идею. И затем, эффективность для оператора + почти такая же, как оператор + =

    
ответ дан Lin Xuelei 06.05.2015 в 07:45
  • Это должен был комментарий к его ответу, а не новый ответ. –  Allan 29.11.2017 в 14:08