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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Не стоит увлекаться шаблонным программированием! Эксперимент с разными способами 
V
    Опции темы
avn
Дата 13.8.2009, 11:47 (ссылка) | (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Добрый день!

Решил сравнить чем быстрее заполнять массив - циклом, шаблонной функцией или шаблонным классом?

Если вкратце - циклом оказалось таки быстрее  smile . Хотя, просмотрев код на ассемблере, сомнений больше нет... Так что вывод - шаблоны стоит использовать только там, где оно этого стОит  smile .

Ну а теперь - эксперимент.

Машина AMD Athlon 64 3000 1.81 GHz, 1.0 G RAM. Стоит Windows XP Profesional SP2. IDE - VC++2008.
Определен массив из long double arr[256]. Вначале думал выбрать 512 MB, но VC стал ругаться - не хватает памяти для разворота рекурсии  smile ... Реализованы 3 метода:

Циклический метод:
Код

void FillFor (void)
{
    unsigned long f;
    long double val = 0;

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


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

template <unsigned long cur>
void FillingFunct (void)
{
    arr[cur] = cur / Div;
    FillingFunct<cur + 1> ();
}

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

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


Метод заполнения шаблонным рекурсивным классом:
Код

template <unsigned long cur>
struct FillingClass: public FillingClass <cur + 1>
{
    FillingClass()        { arr[cur] = cur / 10.0; }
};

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


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


Измерение производится следующим образом:

- повышаем приоритет потока и процесса до максимума;
- в цикле из 10240 раз замеряем время до входа в функцию, потом функция, потом время выхода. Измерение производится с помощью QueryPerformanceCounter;
- даем системе 1мс обработать другие потоки  smile
- берем среднее арифметическое из всех этих функций.

Итог у меня получился такой:

Цитата

------------------------
--
--  Заполнение массива [256] 10240 раз:
--
--  циклом: в среднем 51 nsec,
--  функцией: в среднем 74 nsec,
--  классом: в среднем 83 nsec.
--
------------------------


Для меня он оказался немного неожиданным, но, изучил дизассемблированный код, все стало на свои места.
PM MAIL   Вверх
Lazin
Дата 13.8.2009, 12:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
ну еще-бы, в первом случае - простая итерация - заполнение массива
во втором и третьем случае, помимо заполнения массива будет расти стек


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
andrew_121
Дата 13.8.2009, 12:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодофей
****


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

Репутация: 6
Всего: 33
Что-то вы напутали.
Первый пример выполняется на стадии работы программы.
Второй и третий - во время компиляции.


--------------------
Удалил аккаунт. Прощайте!
PM MAIL   Вверх
Cheloveck
Дата 13.8.2009, 12:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 3
Всего: 32
Ежели стрелять из пушки по воробьям, то попасть очень сложно. При том расходы колоссальные.


--------------------
user posted image
PM Jabber   Вверх
Lazin
Дата 13.8.2009, 12:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(andrew_121 @  13.8.2009,  12:07 Найти цитируемый пост)
Первый пример выполняется на стадии работы программы.
Второй и третий - во время компиляции.

садись - два smile

кстати, "Метод шаблонной рекурсивной функции" может быть сведен компилятором вообще, к N присваиваний, если ф-я будет встроена, что, если подсказать ему директивой __forceinline? smile

Добавлено через 2 минуты и 54 секунды
Цитата(avn @  13.8.2009,  11:47 Найти цитируемый пост)
Вначале думал выбрать 512 MB, но VC стал ругаться - не хватает памяти для разворота рекурсии

ты хоть понимаешь, что твой код будет делать, и какого размера будет exe-шник, при достаточно большом размере массива? smile

Добавлено через 4 минуты и 19 секунд
Цитата(Lazin @  13.8.2009,  12:34 Найти цитируемый пост)
ты хоть понимаешь, что твой код будет делать, и какого размера будет exe-шник, при достаточно большом размере массива?

это я сказал специально для сто двадцать первого, что-бы он не обижался, что я только на него наезжаю smile


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
andrew_121
Дата 13.8.2009, 12:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодофей
****


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

Репутация: 6
Всего: 33
Цитата(Lazin @  13.8.2009,  12:34 Найти цитируемый пост)
садись - два smile

Почему? Разве это выполняется не во время компиляции?
Т.е. код генерируется.

Добавлено @ 12:45
Цитата(Lazin @  13.8.2009,  12:34 Найти цитируемый пост)
что-бы он не обижался, что я только на него наезжаю

в основном так и есть.

Это сообщение отредактировал(а) andrew_121 - 13.8.2009, 12:53


--------------------
Удалил аккаунт. Прощайте!
PM MAIL   Вверх
Lazin
Дата 13.8.2009, 12:55 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154
Цитата(andrew_121 @  13.8.2009,  12:44 Найти цитируемый пост)
Почему? Разве это выполняется не во время компиляции?
Т.е. код генерируется.
код не может выполняться во время компиляции, просто шаблон генерирует код, который во время выполнения, заполняет массив smile 


--------------------
C++ is the steampunk of programming languages: modern ideas realized with victorian technology.
PM MAIL Skype GTalk   Вверх
andrew_121
Дата 13.8.2009, 12:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодофей
****


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

Репутация: 6
Всего: 33
Цитата(Lazin @  13.8.2009,  12:55 Найти цитируемый пост)
код не может выполняться во время компиляции, просто шаблон генерирует код, который во время выполнения, заполняет массив smile  

Я это и имел ввиду. Просто по другому выразился.


--------------------
Удалил аккаунт. Прощайте!
PM MAIL   Вверх
GoldFinch
Дата 13.8.2009, 13:05 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


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

Репутация: 15
Всего: 26
тема - бред. ТС не понимает что делает его код.

Добавлено через 2 минуты и 24 секунды
Цитата(avn @  13.8.2009,  12:47 Найти цитируемый пост)
Для меня он оказался немного неожиданным, но, изучил дизассемблированный код, все стало на свои места. 

а что дизасм не выложил?
PM MAIL ICQ   Вверх
GoldFinch
Дата 13.8.2009, 13:21 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


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

Репутация: 15
Всего: 26
avn, 
сравни заодно с этим
Код

void FillFor_2()
{
    double val = 0;
    for (double* it = arr, E=arr+MemSize; it!=E; ++it)
    {
        *it = val;
        val += 0.1;
    }
}

и с этим
Код

void FillStd()
{
    struct F 
    {
         double val;
         F() : val(-0.1) {}
         double operator() () { return val+=0.1;  }
    } f;
    std::generate(arr,arr+MemSize,f);
}


Добавлено @ 13:26
еще можно
Код

#include <boost/lambda.hpp>
void FillLambda()
{
    double val=0 - 0.1;
    std::generate(arr,arr+MemSize, boost::lambda::var(val)+=0.1 );
}


Это сообщение отредактировал(а) GoldFinch - 13.8.2009, 13:29
PM MAIL ICQ   Вверх
avn
Дата 14.8.2009, 12:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
GoldFinch, ну чего сразу же бред??? Вот тут человек пытается заполнить таблицу CRC методом шаблонных классов - именно эта статья меня и натолкнула на идею сравнить производительность разных методов.

А дизасм я не выложил, т. к. я смотрел в своем IDE. Да и длинноват он будет... Кто хочет, сам может все увидеть.

Cheloveck, стрелять по воробьям из пушки - это мастер-класс стрельбы, если попал  smile  ! В нерабочее время можно и поразвлечься  smile !

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

И вообще - я считаю, что полезно в в разделе "С++ для новичков" проводить такие небольшие исследования, чтобы люди лучше понимали, как и что работает.

GoldFinch, по поводу твоего кода - ща попробую  smile  ...

Это сообщение отредактировал(а) avn - 14.8.2009, 12:25
PM MAIL   Вверх
zim22
Дата 14.8.2009, 12:31 (ссылка) | (голосов:2) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


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

Репутация: 24
Всего: 69
Цитата(avn @  14.8.2009,  12:22 Найти цитируемый пост)
И вообще - я считаю, что полезно в в разделе "С++ для новичков" проводить такие небольшие исследования.

template metaprograming явно не для новичков



--------------------
C++ FAQ Lite
PM MAIL   Вверх
avn
Дата 14.8.2009, 12:39 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
GoldFinch, попробовал. Получилось следующее:

Цитата

------------------------
--
--  Filling array [256] 1024 times:
--
--  simple FOR: average 50.3 nsec,
--  templated function: average 63.1 nsec,
--  templated class: average 69.4 nsec,
--  iterated FOR: average 52.0 nsec,
--  std::generate: average 80.0 nsec,
--  std::generate + boost::lambda: average 239.2 nsec
--
------------------------


ИТОГ: алгоритм FOR с итератором работает слегка быстрее, чем просто FOR. По ходу разных запусков получалось, что иногда быстрее, иногда медленнее. Но, в общем, очень близко.

Ну а использование std::generate - кхм, не очень smile ...

Добавлено через 4 минуты и 28 секунд
Цитата(zim22 @ 14.8.2009,  12:31)
template metaprograming явно не для новичков

Ну-у, в этой области я пока что новичок - разбираюсь, изучаю - посему и в разделе для новичков smile ...
PM MAIL   Вверх
GoldFinch
Дата 14.8.2009, 13:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


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

Репутация: 15
Всего: 26
avn, полный код тестовой программы выложи, и опции компилятора
чтото результаты сомнительные

Добавлено @ 13:45
Цитата(avn @  14.8.2009,  13:22 Найти цитируемый пост)
А дизасм я не выложил, т. к. я смотрел в своем IDE. Да и длинноват он будет... Кто хочет, сам может все увидеть.

у нас нет твоего тестового кода, и настроек компиляции, так что сами ничего не увидим

Это сообщение отредактировал(а) GoldFinch - 14.8.2009, 13:45
PM MAIL ICQ   Вверх
GoldFinch
Дата 14.8.2009, 14:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


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

Репутация: 15
Всего: 26
ну да, все как я и думал.

avn, у тебя наверное были включены проверки времени выполнения STL (надо /GS-), 
поэтому код с STL получился медленным

мой тестовый код
Код

#include <iostream>
#include <iomanip>
#include <windows.h>

#include <algorithm>
#include <boost/lambda/lambda.hpp>

double* arr;
int MemSize;


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

void FillFor_2()
{
    double val = 0;
    for (double *it = arr, *E=arr+MemSize; it!=E; ++it)
    {
        *it = val;
        val += 0.1;
    }
}

int main()
{
    std::cout<<"MemSize=";
    std::cin>>MemSize;
    arr=new double[MemSize];

    int countOfTests;
    std::cout<<"countOfTests=";
    std::cin>>countOfTests;

    std::cout<<std::setprecision(4);

    SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS);
    SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_TIME_CRITICAL);

    Sleep(1);
    __int64 t0=__rdtsc();
    __int64 t1=__rdtsc();
    __int64 deltaTime=t1-t0;

    {
        __int64 time=0;
        Sleep(1);
        for(int testsCount=countOfTests;testsCount;--testsCount)
        {
            Sleep(1);
            __int64 t0=__rdtsc();
            FillFor_2();
            __int64 t1=__rdtsc();
            time+=t1-t0-deltaTime;
        }
        std::cout<<"FillFor_2 rate="<<(double)time/(countOfTests*MemSize)<<std::endl;
    }

    {
        __int64 time=0;
        Sleep(1);
        for(int testsCount=countOfTests;testsCount;--testsCount)
        {
            Sleep(1);
            __int64 t0=__rdtsc();
            FillLambda();
            __int64 t1=__rdtsc();
            time+=t1-t0-deltaTime;
        }
        std::cout<<"FillLambda rate="<<(double)time/(countOfTests*MemSize)<<std::endl;
    }

    return 0;
}

результат:
Код

MemSize=1024
countOfTests=1024
FillFor_2 rate=7.517
FillLambda rate=7.19
Для продолжения нажмите любую клавишу . . .

код с лямбдой всегда быстрее, т.к. там там тест-код оптимальнее, 1 операция против 2х

Добавлено @ 14:30
а вот так выглядят дизасмы, 
код c for
Код

.text:00401104                 call    esi ; Sleep(x)
.text:00401106                 fldz
.text:00401108                 mov     ecx, MemSize
.text:0040110E                 rdtsc
.text:00401110                 mov     edi, eax
.text:00401112                 mov     eax, arr
.text:00401117                 lea     ecx, [eax+ecx*8]
.text:0040111A                 mov     ebx, edx
.text:0040111C                 cmp     eax, ecx
.text:0040111E                 jz      short loc_40113A
.text:00401120                 fld     ds:__real@3fb999999999999a
.text:00401126                 jmp     short loc_40112A
.text:00401128 ; ---------------------------------------------------------------------------
.text:00401128
.text:00401128 loc_401128:                             ; CODE XREF: _main+136j
.text:00401128                 fxch    st(1)
.text:0040112A
.text:0040112A loc_40112A:                             ; CODE XREF: _main+126j
.text:0040112A                 fxch    st(1)
.text:0040112C                 add     eax, 8
.text:0040112F                 fst     qword ptr [eax-8]
.text:00401132                 fadd    st, st(1)
.text:00401134                 cmp     eax, ecx
.text:00401136                 jnz     short loc_401128
.text:00401138                 fstp    st
.text:0040113A
.text:0040113A loc_40113A:                             ; CODE XREF: _main+11Ej
.text:0040113A                 rdtsc
.text:0040113C                 fstp    st
...

код с лямбдой:
Код

.text:004011C3                 call    esi ; Sleep(x)
.text:004011C5                 fld     ds:__real@bfb999999999999a
.text:004011CB                 mov     ecx, MemSize
.text:004011D1                 rdtsc
.text:004011D3                 mov     edi, eax
.text:004011D5                 mov     eax, arr
.text:004011DA                 lea     ecx, [eax+ecx*8]
.text:004011DD                 mov     ebx, edx
.text:004011DF                 cmp     eax, ecx
.text:004011E1                 jz      short loc_4011FD
.text:004011E3                 fld     ds:__real@3fb999999999999a
.text:004011E9                 jmp     short loc_4011ED
.text:004011EB ; ---------------------------------------------------------------------------
.text:004011EB
.text:004011EB loc_4011EB:                             ; CODE XREF: _main+1F9j
.text:004011EB                 fxch    st(1)
.text:004011ED
.text:004011ED loc_4011ED:                             ; CODE XREF: _main+1E9j
.text:004011ED                 fadd    st(1), st
.text:004011EF                 add     eax, 8
.text:004011F2                 fxch    st(1)
.text:004011F4                 fst     qword ptr [eax-8]
.text:004011F7                 cmp     eax, ecx
.text:004011F9                 jnz     short loc_4011EB
.text:004011FB                 fstp    st
.text:004011FD
.text:004011FD loc_4011FD:                             ; CODE XREF: _main+1E1j
.text:004011FD                 rdtsc
.text:004011FF                 fstp    st
...


Это сообщение отредактировал(а) GoldFinch - 14.8.2009, 14:34
PM MAIL ICQ   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

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

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


 




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


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

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