Написал несколько бенчмарков для вектора (использовал библиотеку гугла https://github.com/google/benchmark) и получил странный результат: обход с циклом от size
до нуля работает в два-три раза быстрее, чем от нуля до size
.
Подумал, это может быть связано с кешированием и прочими оптимизациями процессора, потому написал такие тесты
#define ARGS Arg(10000)
static void BM_Minus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; i = i - 1) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_Minus)->ARGS;
static void BM_PlusMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i + (-1)) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PlusMinus)->ARGS;
static void BM_PreMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; --i) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PreMinus)->ARGS;
static void BM_PostMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; i--) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PostMinus)->ARGS;
// -------------------------------------------------
static void BM_Plus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i + 1) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_Plus)->ARGS;
static void BM_MinusMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i - (-1)) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_MinusMinus)->ARGS;
static void BM_PrePlus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); ++i) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PrePlus)->ARGS;
static void BM_PostPlus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i++) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PostPlus)->ARGS;
И получил следующие результаты:
Benchmark Time CPU Iterations
----------------------------------------------------------------
BM_Minus/10000 16202 ns 16186 ns 43230
BM_PlusMinus/10000 9 ns 9 ns 76223137
BM_PreMinus/10000 16200 ns 16187 ns 43200
BM_PostMinus/10000 16207 ns 16193 ns 43089
BM_Plus/10000 42778 ns 42739 ns 16415
BM_MinusMinus/10000 42734 ns 42696 ns 16392
BM_PrePlus/10000 42783 ns 42745 ns 16361
BM_PostPlus/10000 42965 ns 42926 ns 16378
Посмотрел на ассемблер (предварительно выпилив код гугловской библиотеки), в сложении используется инструкция ja
, в вычитании je
, что, очевидно, не может давать такой разницы. В остальном отличие только в том, с каким числом сравнивается, что, опять же, повлиять не может, и сложение меняется на вычитание. Даже адрес переменной i
тот же.
Разница остается вне зависимости от того, включены ли оптимизации (проверял от O0
до O4
) и сколько элементов создается (проверял на малых, средних и больших значениях).
Вопрос:
1) Верны ли эти результаты для всех/большинства процессоров?
2) Почему такое происходит?
3) Возможно, кому-то известны случаи использования этой особенности?
4) Еще интересно, почему компилятор так оптимизировал BM_PlusMinus()
. Вернее, почему только ее. Но тема не об этом, это просто замечание.
Компилятор: g++ 7.3.1
Процессор: Intel Core i7
P.S. В комментариях заметили, что возможно, проблема в том, что state.range(0) вызывается несколько раз. Я не акцентировал на этом внимания, но написал, что ассемблерный код одинаковый. Более того, изначально я проверял с константами на месте state.range(0), также менял цикл на while, инициализацию полностью выносил за цикл бенчмарка. Потому проблема не в тестах, они корректны.
Сейчас я склоняюсь к версии, что процессору проще сравнивать с нулм, чем с большими числами, но тогда возникает вопрос, почему не уменьшаетя разница на малых числах.
Есть один тонкий момент - при использовании в качестве ограничителя вызова функции.
Тут
for(int = func(); i >= 0; --i)
func()
вызывается один раз, а тут -
for(int = 0; i < func(); ++i)
много раз (если оптимизатор не выпилит этот вызов, чего он может и не делать, если для него не очевидно, что этот вызов всегда дает одинаковый результат и не выполняет никаких побочных действий).
Update после возражения автора вопроса
Еще - вот такой код
int main()
{
const int N = 1000000000;
{
muTimer mt;
for(int i = 0; i < N; ++i);
cout << mt.stop().duration() << endl;
}
{
muTimer mt;
for(int i = N; i > 0; --i);
cout << mt.stop().duration() << endl;
}
}
(полностью - см. https://ideone.com/9WYPGW (на нулевое время не смотрите - понятно, что на Ideone оптимизатор циклы вообще выбросил))
дает при компиляции VC++ 2017 с отключенной оптимизацией на моей машине
1591801
1537876
т.е. одинаковое время в пределах погрешности.
Так что... а был ли мальчик? :)
Потому, что проверка данных из точек памяти вытягивает время. Это по-сути БАГ программиста, что он вызывает функцию постоянно. Представьте, что у вас отключены оптимизации. for.cpp: // > g++ -O0 -mtune=native -S -masm=intel -fverbose-asm for.cpp
int const n(10);
int f(){return n;}
/*
_Z1fv:
.LFB0:
.cfi_startproc
push rbp #
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp #,
.cfi_def_cfa_register 6
mov eax, 10 # D.2224,
pop rbp #
.cfi_def_cfa 7, 8
ret
*/
int main(){
for(int i=0;i<f();++i);
/*
jmp .L4 #
.L5:
inc DWORD PTR [rbp-4] # i
.L4:
call _Z1fv #
cmp eax, DWORD PTR [rbp-4] # D.2225, i
setg al #, retval.0
test al, al # retval.0
jne .L5 #,
*/
for(int i=f();i>0;)--i;
/*
call _Z1fv #
mov DWORD PTR [rbp-8], eax # i, tmp63
jmp .L6 #
.L7:
dec DWORD PTR [rbp-8] # i
.L6:
cmp DWORD PTR [rbp-8], 0 # i,
jg .L7 #,
*/
}
В первом цикле постоянно вызывается функция f(); А она постоянно дёргает стек и регистры, возвращая 10.
Здравствуйте, столкнулся с такой проблемой, что compareTo закидывает самую первую строчку из файла в конец после сортировкиТак выглядит код
Класс - реализация интерфейса, описывающего работникаУ каждого работника может быть менеджер, у каждого менеджера может быть менеджер итд
Существует кусками реализованная структура проектаБез многопоточности
Можно ли использовать gridview в linearlayout/ Ставлю, вроде отображает,а содержимого нету!