ferus 10 июн 2015 в 18:15

Веселые старты или C++ и STL: кто быстрее?

4 мин

20K

C++*

Из песочницы

-9

Комментарии 44

AMDmi3 10 июн 2015 в 18:26

Сравнивать быстродействие кода без оптимизаций? Ну ок.

VioletGiraffe 10 июн 2015 в 21:45

+1. Тема интересна, результаты бесполезны. Пожалуй, повторю эксперимент сам. Один раз столкнулся при оптимизации хотспота с тем, что обход вектора с помощью итератора заметно медленнее, чем по индексу (в релизе со вмеми оптимизациями).

lexdevel 11 июн 2015 в 10:56

обход вектора с помощью итератора заметно медленнее, чем по индексу

Скорее всего это связано с тем, что Вы использовали постинкремент, а надо — преинкремент. Пруф.

VioletGiraffe 11 июн 2015 в 11:48

Не-а, всегда пишу прединкремент. После проделанного вчера эксперимента (мой пост ниже) я понял, что дело всего-навсего было в том, что я не догадался предвычислить end() до начала цикла, а size() — догадался. Это единственный фактор, насколько я могу судить по результатам исследования.

А вот разницы между +it и it++ как раз и нет в этом конкретном тесте.

xiWera 11 июн 2015 в 00:47

Ага, автор узнает много нового когда скомпилит все варианты с -O2 и посмотрит на дизасм :)

mickey99 10 июн 2015 в 18:34

Повторите пожалуйста те же тесты с _SECURE_SCL=0 и _HAS_ITERATOR_DEBUGGING=0

AMDmi3 10 июн 2015 в 18:55

А какое отношение к gcc имеют VC'шные костыли?

mickey99 10 июн 2015 в 19:55

Вы правы, никакого. Просто автоматическая реакция на «STL тормозит».

Gorthauer87 10 июн 2015 в 18:38

Только вот во всех этих сравнениях есть одна большая проблема: gcc по умолчанию не включает оптимизации, а если собирать с -O2, то всё становится совсем иначе:

Берем уровень -O3 и сравниваем accumulate с самым хардкорным вариантом:

aleksey@aleksey ~/d/p/bench> ./test 
t=0.00024414 ms
aleksey@aleksey ~/d/p/bench> ./test2 
t=0.00024414 ms

А если не видно разницы, то зачем платить больше?

GRascm 10 июн 2015 в 18:39

Даже при использовании -O1 у меня первый вариант работает с той же скоростью что и последний.

Gorthauer87 10 июн 2015 в 18:41

Кстати, clang тоже дают точно такую же скорость, хотя на -O1 он уже сливает.

Moxa 10 июн 2015 в 20:48

что-то подозрительно, у меня такое же значение выдало с пустым кодом…

GRascm 10 июн 2015 в 21:00

Теоретически возможно, что, с такой агрессивной оптимизацией, оно просто заполнило массив и посчитало сумму ещё на этапе компиляции.

Moxa 10 июн 2015 в 21:05

а сумма где-нибудь используется? скорее она и не считалась, оптимизатор просто удалил ненужный цикл

QtRoS 10 июн 2015 в 19:27

Все равно хорошая статья, хоть и автор не включил оптимизации в компиляторе. Наглядность улучшений от элементарных изменений просто на шикарном уровне! Как будто «Жемчужины программирования» перечитал, где автор упорно «срезает жирок» с циклов.

AWE64 10 июн 2015 в 21:00

По-моему, все, что здесь описано, и так более-менее очевидно, без подробностей, конечно. На цифры взглянуть всегда интересно — за это плюс статье.

kashey 10 июн 2015 в 19:51

Можно еще префетча немного добавить и суммировать «рядком» в несколько переменных — быть может векторизация прилетит.
В свое время (ну лет 15 назад, когда DDR память появилась) AMD с Интелом выпускали километры документации о том как же быстро пройтись по массиву и получить весь заявленный в рекламе bandwidth. Ой не простое это было дело.
С тех пор подросло целое поколение…

Zordhauer 10 июн 2015 в 20:07

Мне кажется, для хорошего программиста должно быть очевидно, что за любой «сахар» (улучшение читабельности, возможность повторого использования, универсальность, дополнительную абстракцию и т.п.) требуется заплатить как раз-таки скоростью выполнения.
Хочешь скорости работы программы — пиши в машинных кодах, а если хочешь скорости своей работы (и тех, кто будет потом править твой код), то пиши на максимально высокоуровневом языке =)

И это все, как и в случае со статьей, не учитывает оптимизацию компилятора.

MichaelBorisov 10 июн 2015 в 20:14

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

Некоторый «сахар» C++ достается именно что бесплатно. При условии, что компилятор разберется, как перевести этот сахар в эффективный машинный код. Таких случаев немало, и особенно их немало с STL. В крайнем случае «платой за сахар» будет некоторое замедление компиляции.

И написание программы на ассемблере ничуть не уступает (по скорости ее работы) написанию ее в машинных кодах. Поэтому в машинных кодах никто не пишет еще с 50х-60х гг прошлого века.

Zordhauer 10 июн 2015 в 20:34

польза статьи, скорее всего, в том, чтобы показать необходимость знать детали «работы» языка. Ведь не всегда есть возможность использовать оптимизацию компилятора (иначе эта опция был бы включена по умолчанию), да и не всегда стоит доверять компилятору (любое доверие потом может стать боком).

kmu1990 10 июн 2015 в 20:46

польза статьи, скорее всего, в том, чтобы показать необходимость знать детали «работы» языка.

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

иначе эта опция был бы включена по умолчанию

Я думал, что оптимизации не включены по-умолчанию, чтобы сделать отладку проще и компиляцию быстрее (gcc docs), или другими словами сделать процесс разработки более удобным, разве нет?

MichaelBorisov 10 июн 2015 в 20:10

Без включенной оптимизации компилятора все эти результаты несут информацию о скорости работы экзотически скомпилированных (без оптимизации) программ, то есть для практического применения пользы ноль.

Поначалу я удивился, почему помогает ключевое слово «register», ведь даже в VC5.0 компилятор разобрался бы, как оптимизировать такой простой цикл, и без «register». Сам бы на регистрах что надо разместил. Тем более регистров процессора более чем достаточно для такого простого цикла.

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

VioletGiraffe 10 июн 2015 в 22:14

Тот же тест, винда, MSVC 2013 (toolset v120) x86, vector(200 * 1000 * 1000). Релиз + /O2 (дефолтные релизные настройки):

accumulate: 46 ms
for_each: 118 ms
for(int i: vec): 118 ms // Обидно, да?
for (auto i = vec.begin(); i != vec.end(); i++): 47 ms
for (auto i = vec.begin(); i != end; ++i): 46 ms
for (size_t i = 0; i < vec.size(); ++i) sum += vec[i];: 118 ms
for (size_t i = 0; i < size; ++i) sum += vec[i];: 47 ms // Ага, понятно, почему range-based for медленный: компилятор, как и в этом случае, не кэширует" vec.size() и вычисляет его каждый раз.
int *array = &vec[0]; for(size_t i = 0; i < size; ++i) sum += array[i];: 47 ms
auto end = &vec[vec.size() — 1]; for (int *i = &vec[0]; i != end; ++i) sum += *i;: 47 ms
register: 47 ms // Ч. т. д.
sum += array[i] + array[++i]: 65 ms // Интересно…

VioletGiraffe 10 июн 2015 в 22:20

P. S. Я расстроен, что компилятор не умеет оптимизировать вызов const-метода std::vector::size (ну или end). Неужели это так сложно — определить, что на векторе после generate не вызываются никакие не-const методы? И почему бы в векторе не сделать размер переменной, чтоб его просто вернуть, а не вычислять каждый раз?

MichaelBorisov 12 июн 2015 в 13:28

Я думаю, тут в первую очередь косяк разработчиков STL (P.J. Plauger). Реализация vector::size вычисляет разность между двумя переменными (this->_Mylast — this->Myfirst). Вероятно, время тратится на доступ к этим указателям в памяти.

ассемблерный код получается следующим (VS2013, Release, x86)

mov eax,dword ptr[esp+0Ch]
mov esi,dword ptr[esp+8]
sub eax,esi
sar eax,2

Во как. 4 команды, 2 доступа к памяти, и кроме вычитания еще имеем сдвиг. Сейчас попробую сделать свой «вектор» и посмотреть, что накомпилирует компилятор при простом возврате члена данных класса.

MichaelBorisov 12 июн 2015 в 13:48

Впрочем, к кэшированию все это не относится. Только что посмотрел, как компилятор компилирует цикл for(size_t i=0; i<v.size(); i++) a+=v[i]. Там что-то невообразимое получилось! Очень сложные конструкции, использование SSE и регистров xmm, явные попытки частично размотать цикл. Еще надо поразбираться.

MichaelBorisov 12 июн 2015 в 13:39

Только что попробовал сделать свой «вектор», у которого размер хранился бы в переменной-члене класса. Компилятор прекрасно кэширует значение этой переменной на регистре. Вот пример кода:

#include <iostream>
#include <vector>

class kektor
{
public:
    kektor(size_t nsize) : m_size(nsize) {}

    size_t size(void) const throw() { return m_size; }
private:
    size_t m_size;
};

void print_kek(const kektor& v)
{
    for (size_t i = 0; i < v.size(); i++)
    {
        std::cout << i<<'\n';
    }
}


void main(void)
{
    std::cout << "Hello World!\n";
    size_t sz;
    std::cin >> sz;
    kektor v(sz);
    print_kek(v);
}

Ассемблерный код для функции print_kek:

xor         edi,edi
test        esi,esi
je          endloop
loop:
push        edi 
call        std::basic_ostream<char,std::char_traits<char> >::operator<<
mov         ecx,eax
call        std::operator<<<std::char_traits<char> >
inc         edi
cmp         edi,esi
jb          loop
endloop: ...

Так что да. Неприятно. Недосмотр авторов STL. Оптимизации компилятора доверяй, но проверяй.

kmu1990 12 июн 2015 в 13:40

А почему вы уверены, что в строке sum += vec[i] вызывается const метод? Кажется, если сам vec не const, то из const и не const метода будет выбран как раз последний.

DaylightIsBurning 12 июн 2015 в 23:08

Это не так просто: нужно знать, что значение size() не меняется по ходу выполнения цикла, что далеко не факт, независимо от const, может size() текущее время возвращает — откуда компилятору знать. Короче значение size() может косвенно зависеть от операций в цикле и компилятору не так то просто убедиться в обратном.

VioletGiraffe 12 июн 2015 в 23:24

Да, вы правы, const тут не помогает.

НЛО прилетело и опубликовало эту надпись здесь

Lol4t0 10 июн 2015 в 22:33

Поиграем в игру «найдите 5 отличий»

Возьмем код

#include <vector>
#include <algorithm>
using namespace std;

int foo (vector<int> vec) {
       return accumulate(vec.begin(), vec.end(), 0, [](int sum, int i) {
               return sum + i;
       });
}

int bar (vector<int> vec) {
       const int COUNT = vec.size();
       register int *array = &vec[0];
       register int sum = 0;
       for(register int i = 0; i != COUNT; ++i) {
           sum += array[i];
       };
       return sum;
}

Скомпилируем

Сравним результат

foo(std::vector<int, std::allocator<int> >):
	mov	rcx, QWORD PTR [rdi+8]
	mov	rdx, QWORD PTR [rdi]
	xor	eax, eax
	cmp	rdx, rcx
	je	.L4
.L3:
	add	eax, DWORD PTR [rdx]
	add	rdx, 4
	cmp	rcx, rdx
	jne	.L3
	rep ret
.L4:
	rep ret
bar(std::vector<int, std::allocator<int> >):
	mov	rcx, QWORD PTR [rdi]
	mov	rax, QWORD PTR [rdi+8]
	sub	rax, rcx
	sar	rax, 2
	test	eax, eax
	mov	esi, eax
	je	.L10
	xor	edx, edx
	xor	eax, eax
.L9:
	add	eax, DWORD PTR [rcx+rdx*4]
	add	rdx, 1
	cmp	esi, edx
	jne	.L9
	rep ret
.L10:
	xor	eax, eax
	ret

ZyXI 10 июн 2015 в 22:39

Странно, что вас ругали за отсутствие оптимизаций, но пропустили CLOCK_REALTIME. Эти часы нельзя использовать для любых измерений производительности: документация явно говорит, что они могут изменяться. Специально для измерения производительности есть CLOCK_MONOTONIC_RAW (CLOCK_MONOTONIC для не‐linux) и CLOCK_PROCESS_CPUTIME_ID. На простоту кода изменение константы на правильную не влияет никак.

ferus 12 июн 2015 в 22:27

Отличное замечание, вы безусловно правы

alexac 11 июн 2015 в 00:36

Мне одному кажется, что последний пример

sum += array[i] + array[++i];

Это явное UB? Я не удивляюсь, что там прирост скорости вдвое, там компилятор имел право вообще пол системы снести во время трансляции.

Упрощенный пример и предупреждение: codepad.org/U2jK5eIo

НЛО прилетело и опубликовало эту надпись здесь

kmu1990 11 июн 2015 в 09:37

Нет, имеется ввиду, что i изменяется и читается в одном выражении. Например, порядок вычисления array[i] и array[++i] не определен, например, он может сначала посчитать array[++i] и тогда программа дважды обратится к одному и тому же элементу массива, что не правильно.

А вообще вот, что пишет стандарт:

If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined.

В данном случае, как я понимаю, сайд эффект от ++i «unsequenced» с использованием i в array[i].

Singerofthefall 11 июн 2015 в 10:25

Да, вы совершенно правы, так как (§1.9/15)

Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced

ferus 12 июн 2015 в 22:28

Да, вы правы, позор на мои седины,
добавил в статью UPDATE, спасибо!

andy_p 11 июн 2015 в 12:14

auto end = &vec[vec.size () — 1];
for(int *i = &vec[0]; i != end; ++i) {
sum += *i;
};

А последний элемент не суммируем?

ferus 12 июн 2015 в 22:29

да ну его

DaylightIsBurning 11 июн 2015 в 17:11

Решил проверить сам и заодно узнать, насколько хорошо работают оптимизации. Во-первых не сошлись времена даже близко — у меня «регистровая» версия выдаёт 660 ms (а не 10 как у автора). Во-вторых оптимизации всё уравнивают, что бы оптимизации цикл совсем не выкинули — добавил вывод суммы в консоль.

g++ --version
cat /proc/cpuinfo | grep "model name" | head -n1

g++ -std=c++11 test_for.cpp -o test_for
g++ -std=c++11 -O3 test_for.cpp -o test_forO3

g++ -std=c++11 test_acc.cpp -o test_acc
g++ -std=c++11 -O3 test_acc.cpp -o test_accO3

g++ -std=c++11 test_reg.cpp -o test_reg
g++ -std=c++11 -O3 test_reg.cpp -o test_regO3

echo "No O; for,acc,reg:"
./test_for
./test_acc
./test_reg

echo "-O3; for,acc,reg:"
./test_forO3
./test_accO3
./test_regO3

Результат:

g++ (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

model name      : Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz
No O; for,acc,reg:
t=11341 ms, sum=-2039607552
t=8141.1 ms, sum=-2039607552
t=660.89 ms, sum=-2039607552
-O3; for,acc,reg:
t=231.37 ms, sum=-2039607552
t=231.31 ms, sum=-2039607552
t=232.29 ms, sum=-2039607552

test_reg.cpp

#include <iostream>
#include <sys/time.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int COUNT = 1000 * 1000 * 1000;
int RandomNumber () {
    static int s = 0;
    return (s++ % 100);
}

int main () {
    vector<int> vec(COUNT);
    generate(vec.begin(), vec.end(), RandomNumber);
    
    struct timespec tm1, tm2;
    clock_gettime(CLOCK_REALTIME, &tm1);
    
    register int *array = &vec[0];
    register int sum = 0;
    for(register int i = 0; i != COUNT; ++i) {
	sum += array[i];
    };
    
    clock_gettime(CLOCK_REALTIME, &tm2);
    
    double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000);
    double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000);
    cout << "t=" << setprecision(5) << t2 -t1 << " ms, sum=" <<sum<< endl;
    return 0;
};

test_acc.cpp

#include <iostream>
#include <sys/time.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int COUNT = 1000 * 1000 * 1000;
int RandomNumber () {
    static int s = 0;
    return (s++ % 100);
}

int main () {
    vector<int> vec(COUNT);
    generate(vec.begin(), vec.end(), RandomNumber);
    
    struct timespec tm1, tm2;
    clock_gettime(CLOCK_REALTIME, &tm1);

    int sum;    
    sum=accumulate(vec.begin(), vec.end(), 0, [](int sum, int i) {
	return sum + i;
    });
    
    clock_gettime(CLOCK_REALTIME, &tm2);
    
    double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000);
    double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000);
    cout << "t=" << setprecision(5) << t2 -t1 << " ms, sum=" <<sum<< endl;
    return 0;
};

test_for.cpp

#include <iostream>
#include <sys/time.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int COUNT = 1000 * 1000 * 1000;
int RandomNumber () {
    static int s = 0;
    return (s++ % 100);
}

int main () {
    vector<int> vec(COUNT);
    generate(vec.begin(), vec.end(), RandomNumber);

    struct timespec tm1, tm2;
    clock_gettime(CLOCK_REALTIME, &tm1);

    int sum = 0;
    for(auto i = vec.begin(); i != vec.end(); ++i) {
	sum += *i;
    };

    clock_gettime(CLOCK_REALTIME, &tm2);

    double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000);
    double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000);
    cout << "t=" << setprecision(5) << t2 -t1 << " ms, sum=" <<sum<< endl;
    return 0;
};

ferus 12 июн 2015 в 22:30

habrahabr.ru/post/260193

Viilture 31 авг в 01:06

    for(int i = 0; i <  siZEA; i++)
    {
        vec[i] = 25624;
    }

0x401766 <+ 260> c7 45 f4 00 00 00 00 movl $0x0,-0xc(%ebp)
0x40176d <+ 267> 8b 45 f4 mov -0xc(%ebp),%eax
0x401770 <+ 270> 3b 45 e4 cmp -0x1c(%ebp),%eax
0x401773 <+ 273> 7d 1f jge 0x401794 MainWindow::MainWindow(QWidget*)+306
27 [1] vec[i] = 25624;
0x401775 <+ 275> 8b 45 f4 mov -0xc(%ebp),%eax
0x401778 <+ 278> 89 04 24 mov %eax,(%esp)
0x40177b <+ 281> b9 38 e0 40 00 mov $0x40e038,%ecx
0x401780 <+ 286> e8 6f 3e 00 00 call 0x4055f4 <QVector::operator>
0x401785 <+ 291> 83 ec 04 sub $0x4,%esp
0x401788 <+ 294> c7 00 18 64 00 00 movl $0x6418,(%eax)
25 [1] for(int i = 0; i < siZEA; ++i)
0x40178e <+ 300> 83 45 f4 01 addl $0x1,-0xc(%ebp)
0x401792 <+ 304> eb d9 jmp 0x40176d MainWindow::MainWindow(QWidget*)+267

    25 [1]	    for(int i = 0; i <  siZEA; i++)
    {
        vec[i] = 25624;
    }

0x401766 <+ 260> c7 45 f4 00 00 00 00 movl $0x0,-0xc(%ebp)
0x40176d <+ 267> 8b 45 f4 mov -0xc(%ebp),%eax
0x401770 <+ 270> 3b 45 e4 cmp -0x1c(%ebp),%eax
0x401773 <+ 273> 7d 1f jge 0x401794 MainWindow::MainWindow(QWidget*)+306
27 [1] vec[i] = 25624;
0x401775 <+ 275> 8b 45 f4 mov -0xc(%ebp),%eax
0x401778 <+ 278> 89 04 24 mov %eax,(%esp)
0x40177b <+ 281> b9 38 e0 40 00 mov $0x40e038,%ecx
0x401780 <+ 286> e8 6f 3e 00 00 call 0x4055f4 <QVector::operator>
0x401785 <+ 291> 83 ec 04 sub $0x4,%esp
0x401788 <+ 294> c7 00 18 64 00 00 movl $0x6418,(%eax)
25 [1] for(int i = 0; i < siZEA; i++)
0x40178e <+ 300> 83 45 f4 01 addl $0x1,-0xc(%ebp)
0x401792 <+ 304> eb d9 jmp 0x40176d MainWindow::MainWindow(QWidget*)+267

++i i++ Разве есть сейчас в этом разница? Выше пример кода с ++i и i++ с одинаковым ассемблером. А ну еще сейчас for(auto it:vec) в 4-10 раз быстрее обычного цикла

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Веселые старты или C++ и STL: кто быстрее?

Комментарии 44

Публикации

Истории