Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сравнение разных методов инициализации массива 
V
    Опции темы
avn
Дата 5.1.2011, 13:06 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 25.10.2005

Репутация: нет
Всего: нет
Доброго времени суток и с Новым Годом!

Копаясь в своих старых программах, обнаружил subject. Может, кому-то будет полезно...

Я решил измерить время заполнения массива различными способами. Сравнение я решил выполнить командой RDTSC. Измерение делалось следующим образом:

1) взяли RDTSC

2) пропустили цикл из 1 000 000 заполнений массива дробных чисел размером в 256 элементов

3) замерили RDTSC и разделили на кол-во итераций цикла

Характеристики машины: Pentium Dual-Core E5500 (2.8GHz), 2GB, WinXP.Prof.SP2

Результаты получились следующие:

Код

------------------------
--
--  Filling array [256] 1000000 times:
--
--  FOR (offset): average 25.0
--  std::generate: average 39.8
--  FOR (pointer): average 56.8
--  templated function: average 77.6
--  templated class: average 98.9
--  std::generate + boost::lambda: average 425.6
--  FOR (vector, iterator): average 530.1
--  FOR (list, iterator): average 578.7
--
------------------------


Способ FOR (offset):
Код

    for (f = 0; f < MemSize; ++f)
        arr[f] = val;


Способ std::generate:
Код

    struct F 
    {
         double val;
         F() : val (InitVal) {}
         double operator() () { return val; }
    } f;

    std::generate (arr, arr + MemSize, f);


Способ templated function:
Код

template <dword cur>
void FillingFunct (void)
{
    arr[cur] = InitVal;
    FillingFunct<cur + 1> ();
}

template <>
void FillingFunct<MemSize> (void)
{
}

void FillFunct (void)
{
    FillingFunct <0> ();
}


Способ templated class:
Код

template <dword cur>
struct FillingClass: public FillingClass <cur + 1>
{
    FillingClass()        { arr[cur] = InitVal; }
};

template <>
struct FillingClass<MemSize>
{
    FillingClass()        { }
};

void FillClass (void)
{
    FillingClass<0> c;
}


Способ std::generate + boost::lambda:
Код

    double val = InitVal;
    std::generate (arr, arr+MemSize, boost::lambda::var(val) = InitVal );


Способ FOR (vector, iterator):
Код

    ArrElem val = InitVal;
    ArrVect::iterator itCur, itEnd;

    itEnd = arr_vect.end ();
    for (itCur = arr_vect.begin (); itCur != itEnd; ++itCur)
        *itCur = val;


Способ FOR (list, iterator):
Код

    ArrElem val = InitVal;
    ArrList::iterator itCur, itEnd;

    itEnd = arr_list.end ();
    for (itCur = arr_list.begin (); itCur != itEnd; ++itCur)
        *itCur = val;


А вот и полный текст программы. Ее можно легко реконфигурировать, манипулируя #define-ми

Добавлено @ 13:07
Код


#include <Windows.h>                    // для повышения приоритета задачи
#include <intrin.h>                        // для RDTSC
#include <conio.h>                        // для getch ()
#include <vector>
#include <list>
#include <algorithm>
#include <boost\lambda\lambda.hpp>

typedef unsigned long dword;            // тип данных "беззнаковое 32 битное целое"
typedef long long qword;                // тип данных "беззнаковое 64 битное целое"
typedef long double real;                // тип данных "дробное число"

#define    InitVal        1.36e-4                // нек-рая константа
#define    MemSize        256                    // размер массива
#define    Loop        (1000*1000)            // кол-во повторений (для статистики)
#define    Div            100                    // уменьшение среднего RDTSC на экране

#pragma intrinsic (__rdtsc)                // подключение RDTSC
#define rdtsc() ((qword)__rdtsc())        // макроподстановка "получение кол-ва тактов процессора"

typedef long double ArrElem;            // тип данных "элемент массива"
typedef std::vector <ArrElem> ArrVect;    // тип данных "vector-массив"
typedef std::list <ArrElem> ArrList;    // тип данных "vector-массив"

volatile ArrElem arr[MemSize];            // массив в стиле Си
ArrVect arr_vect (MemSize);                // массив в стиле Си++ (vector)
ArrList arr_list (MemSize);                // массив в стиле Си++ (list)

// **
// **  Метод инициализации циклом в стиле Си - смещение от начала
// **

void FillFor (void)
{
    dword f;
    ArrElem val = InitVal;

    for (f = 0; f < MemSize; ++f)
        arr[f] = val;
}

// **
// **  Метод инициализации циклом в стиле Си - указатель
// **

void FillFor_2 (void)
{
    ArrElem val = InitVal;
    volatile ArrElem *E = arr + MemSize;
    volatile ArrElem *pCur;

    for (pCur = arr; pCur != E; ++pCur)
        *pCur = val;
}

// **
// **  Метод инициализации циклом в стиле STL - vector, итератор
// **

void FillForVectorIt (void)
{
    ArrElem val = InitVal;
    ArrVect::iterator itCur, itEnd;

    itEnd = arr_vect.end ();
    for (itCur = arr_vect.begin (); itCur != itEnd; ++itCur)
        *itCur = val;
}

// **
// **  Метод инициализации циклом в стиле STL - list, итератор
// **

void FillForListIt (void)
{
    ArrElem val = InitVal;
    ArrList::iterator itCur, itEnd;

    itEnd = arr_list.end ();
    for (itCur = arr_list.begin (); itCur != itEnd; ++itCur)
        *itCur = val;
}

// **
// **  Метод алгоритма generate
// **

void FillStd()
{
    struct F 
    {
         double val;
         F() : val (InitVal) {}
         double operator() () { return val; }
    } f;

    std::generate (arr, arr + MemSize, f);
}

// **
// **  Метод алгоритма generate на основе Boost
// **

void FillLambda()
{
    double val = InitVal;
    std::generate (arr, arr+MemSize, boost::lambda::var(val) = InitVal );
}

// **
// **  Метод шаблонной рекурсивной функцией
// **

template <dword cur>
void FillingFunct (void)
{
    arr[cur] = InitVal;
    FillingFunct<cur + 1> ();
}

template <>
void FillingFunct<MemSize> (void)
{
}

void FillFunct (void)
{
    FillingFunct <0> ();
}

// **
// **  Метод шаблонным рекурсивным классом
// **

template <dword cur>
struct FillingClass: public FillingClass <cur + 1>
{
    FillingClass()        { arr[cur] = InitVal; }
};

template <>
struct FillingClass<MemSize>
{
    FillingClass()        { }
};

void FillClass (void)
{
    FillingClass<0> c;
}

// **
// **  Точка входа
// **

void main (void)
{
    dword f;
    qword before, after;
    real dif_mode;

    // . Windows - максимальный приоритет
    SetPriorityClass (GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
    SetThreadPriority (GetCurrentThread (), THREAD_PRIORITY_TIME_CRITICAL);    

    printf ("\
------------------------\n\
--\n\
--  Filling array [%d] %d times:\n\
--\n", MemSize, Loop);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillFor ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  FOR (offset): average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillStd ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  std::generate: average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillFor_2 ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  FOR (pointer): average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillFunct ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  templated function: average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillClass ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  templated class: average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillLambda ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  std::generate + boost::lambda: average %.1f (val %e)\n", dif_mode, arr[MemSize / 2]);

    // .
    arr_vect[MemSize / 2] = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillForVectorIt ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  FOR (vector, iterator): average %.1f (val %e)\n", dif_mode, arr_vect[MemSize / 2]);

    // .
    *arr_list.rbegin()++ = 0;
    before = rdtsc ();
    for (f = 0; f < Loop; ++f)
        FillForListIt ();
    after = rdtsc ();
    dif_mode = (after - before) * 1.0 / Loop / Div;

    printf ("--  FOR (list, iterator): average %.1f (val %e)\n", dif_mode, *arr_list.rbegin()++);

    printf ("\
--\n\
------------------------\n");

    _getch ();
}


Это сообщение отредактировал(а) avn - 5.1.2011, 13:09
PM MAIL   Вверх
Alca
Дата 5.1.2011, 14:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 2
Всего: 50
Это типа в релизе? Чем компилил?


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
Estranged
Дата 5.1.2011, 15:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 158
Регистрация: 30.8.2010

Репутация: нет
Всего: 3
Программа будет грешить слегка, процессор выполняет еще тысячи прерываний в секунду, отчего счетчик тактов слегка раздувает реальные показатели выполнения.
PM MAIL   Вверх
avn
Дата 5.1.2011, 16:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 25.10.2005

Репутация: нет
Всего: нет
Цитата(Alca @ 5.1.2011,  14:38)
Это типа в релизе? Чем компилил?

Компилил в Microsoft Visual Studio 2008

Добавлено через 1 минуту и 36 секунд
Цитата(Estranged @ 5.1.2011,  15:14)
Программа будет грешить слегка, процессор выполняет еще тысячи прерываний в секунду, отчего счетчик тактов слегка раздувает реальные показатели выполнения.

Это понятно smile
Но, насколько я знаю, для ОТНОСИТЕЛЬНОГО сравнения RDTSC - самая доступная точная вещь.
А проблему прерываний я решаю статистически - думаю, за 1e6 итераций * 256 элементов массива роль единичных прерываний уже несущественна.
PM MAIL   Вверх
Alca
Дата 5.1.2011, 17:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 2
Всего: 50
Цитата

Это типа в релизе?

я по два раз, два раза не повторяю, не повторяю  smile 


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
Estranged
Дата 5.1.2011, 21:30 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 158
Регистрация: 30.8.2010

Репутация: нет
Всего: 3
            ------------------------
            --
            --  Filling array [256] 1000000 times:
            --
--  FOR (offset): average 5.3 (val 1.360000e-004)
--  std::generate: average 5.3 (val 1.360000e-004)
--  FOR (pointer): average 5.3 (val 1.360000e-004)
--  templated function: average 2.6 (val 1.360000e-004)
--  templated class: average 2.6 (val 1.360000e-004)
--  FOR (vector, iterator): average 5.3 (val 1.360000e-004)
--  FOR (list, iterator): average 7.9 (val 1.360000e-004)
            --
            ------------------------

Релиз в MS VS 2010. Процессор AMD Phenom II 3000 Ггц.
PM MAIL   Вверх
Alca
Дата 5.1.2011, 22:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3993
Регистрация: 14.6.2006

Репутация: 2
Всего: 50
 smile 


--------------------
C++ cross-platform library
PM WWW ICQ Skype Jabber   Вверх
sQu1rr
Дата 7.1.2011, 01:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Код

------------------------
--
--  Filling array [256] 10 000 000 times:
--
--  FOR (offset): average 2.9 (val 1.360000e-004)
--  std::generate: average 3.0 (val 1.360000e-004)
--  FOR (pointer): average 2.9 (val 1.360000e-004)
--  templated function: average 2.7 (val 1.360000e-004)
--  templated class: average 2.7 (val 1.360000e-004)
--  std::generate + boost::lambda: average 3.0 (val 1.360000e-004)
--  FOR (vector, iterator): average 2.9 (val 1.360000e-004)
--  FOR (list, iterator): average 8.0 (val 1.360000e-004)
--
------------------------
PM MAIL Skype GTalk   Вверх
avn
Дата 11.1.2011, 17:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 25.10.2005

Репутация: нет
Всего: нет
Цитата(Estranged @ 5.1.2011,  21:30)
------------------------
            --
            --  Filling array [256] 1000000 times:
            --
--  FOR (offset): average 5.3 (val 1.360000e-004)
--  std::generate: average 5.3 (val 1.360000e-004)
--  FOR (pointer): average 5.3 (val 1.360000e-004)
--  templated function: average 2.6 (val 1.360000e-004)
--  templated class: average 2.6 (val 1.360000e-004)
--  FOR (vector, iterator): average 5.3 (val 1.360000e-004)
--  FOR (list, iterator): average 7.9 (val 1.360000e-004)
            --
            ------------------------

Релиз в MS VS 2010. Процессор AMD Phenom II 3000 Ггц.

Интересно, что тут соотношение не такое, как у меня. Почему варианты templated обрабатываются в 2 раза быстрее, чем FOR??? Или все дело в компиляторе? У меня VS 2008.

Alca - да, релиз smile
PM MAIL   Вверх
Estranged
Дата 11.1.2011, 19:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 158
Регистрация: 30.8.2010

Репутация: нет
Всего: 3
avn, потому что FOR - цикл, предсказание ветвлений может ошибаться. А templated развернулись в линейный код типа
загрузить в arr [0] значение X
загрузить в arr [1] значение X
загрузить в arr [2] значение X
загрузить в arr [3] значение X
...

Это сообщение отредактировал(а) Estranged - 11.1.2011, 19:24
PM MAIL   Вверх
bsa
Дата 12.1.2011, 22:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196
Цитата(avn @  11.1.2011,  18:12 Найти цитируемый пост)
Интересно, что тут соотношение не такое, как у меня. Почему варианты templated обрабатываются в 2 раза быстрее, чем FOR??? Или все дело в компиляторе? У меня VS 2008.

От компилятора тоже многое зависит. Еще больше зависит от уровня оптимизации при компиляции.
Если интересно, что получается при компиляции шаблонов - включи генерацию ассемблерного кода и смотри.


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1322 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.