оптимизация сравнений в С++

[Andrey_Kireew]

Добрый вечер,
в процессе доработки одной из программ, пришлось добавить много разных условий, видимо в критичном, часто повторяющемся месте, и быстродействие кода заметно упало. Вот пример:

Используется синтаксис C

while (((*ind<=0) || (*b==0)) && (b<F)) 
    {ind++; b++;}
 

это поиск пары положительных элементов 2-х массивов. Ну есть и другие фрагменты в этом духе ...

Можно ли как то ускорить их работу? У меня есть идея - сначала выбрать индексы элементов 1-го массива, а по ним уже выбирать элементы 2-го массива. Но будет ли от этого толк? Ведь тогда придётся записывать индексы во вспомогательный массив, а это займет времени может даже и больше, чем второе сравнение ...

Вообще, можно ли как то это всё оптимизировать?

[iifat]

Вообще, насколько я помню, рекомендуют начать с профилирования — выделить ресурсопожирающие куски. И оптимизировать их не по мелочи, а алгоритмически.
В вашем случае, имхо, (принципиалоьно) ускорить этот кусок невозможно. Может, он у вас вызывается миллионы раз, но тогда и менять надо объемлющий кусок, дабы этот вызывался не так часто.

[Pphantom]

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

[Pavia]

Я бы так сделал. Сравнение 0 это бесплатная операция в отличие от F. Логическую операцию заменил бы на битовую - тут надо знать статистику данных, какие условия выполняются реже или чаще и их комбинации.

b=F;
while ( (b>=0)&&((*ind<=0) | (*b==0)))
    {ind--; b--;}

Да и вообще данный цикл можно развернуть, и использовать SSE.

Andrey_Kireew в сообщении #1329479 писал(а):

У меня есть идея - сначала выбрать индексы элементов 1-го массива, а по ним уже выбирать элементы 2-го массива.

Это медленно на накладных расходах больше потеряете. Если данные умещаются в кэш L1 то чтение 4 такта запись 4 такта, а потом второй проход и с ново чтение 4. 12 против условного перехода которое занимает 12 тактов(считай что сравнение 14 тактов). Если данные провалятся в кэш L2 то скорость упадёт примерно раз в 10.

[Andrey_Kireew]

Pphantom в сообщении #1329494 писал(а):

но Вы уверены, что дело в нем?

раньше было так:

Используется синтаксис C

while ((*ind<=0) && (b<F)) 
    {ind++; b++;}
 

когда я добавил сравнение - стало работать заметно медленнее.

Но там, потом, есть вычисления float, и примерно в таком же количестве. Не знаю как они соотносятся со сравнениями по трудоёмкости на современных процессорах. Может быть разницы и нет. Если так, то дело в этом. Если нет, то и не знаю. Число итераций после изменений даже уменьшилось, по идее - быстрее должно работать.

-- 30.07.2018, 11:53 --

Pavia в сообщении #1329497 писал(а):

b=F;
while ( (b>=0)&&((*ind<=0) | (*b==0)))
    {ind--; b--;}

b -это адрес, он никогда не будет нулевым, какой тогда смысл "гнать" их в обратную сторону?

[worm2]

Возможно, так прокатит:

Используется синтаксис C

while (1)
    while ((*ind<=0) && (b<F)) // урезанное условие, проверяющееся быстро
        {ind++; b++;}
    if ( (b>=F) || ((*ind>0) && (*b!=0)) ) // полное условие (инвертированное)
        break;
    ind++; b++;
}

Если не прокатит, можно попробовать урезанное условие поменять на ((*b==0) && (b<F)). Смысл попыток в том, чтобы самый внутренний (исполняющийся наибольшее число раз) цикл упростить и тем самым ускорить, а в более внешнем цикле проводить полную проверку, которая (если повезёт с данными) будет выполняться гораздо реже.

[Dmitriy40]

(Поторопился и ошибся, код неверный, зато идея линеаризации потока выполнения правильная)

Не будет ли быстрее такой вариант?

while (b < F) {
    if (*ind > 0) break;
    if (*b != 0) break;
    ++ind; ++b;
}

Смысл в исключении условия ИЛИ внутри цикла и замены его на два отдельных условия завершения цикла. При этом тело цикла будет выполняться строго линейно до наступления условия выхода из цикла и не будет никаких плохо предсказанных переходов (кроме самого цикла, который предсказывается отлично). Экономится вычисление логического ИЛИ и ошибка предсказания условного перехода, но тратится обращение ко второму массиву, надо выбирать что быстрее.
Т.е. предположение что тормозом является плохо предсказываемый переход при вычислении операции ИЛИ в условии цикла. При этом операции И в условии цикла линейности выполнения не нарушают.

[Geen]

А что, в C++ всегда вычисляются все логические операнды??

[Dmitriy40]

Вроде бы нет, поэтому и условный переход, плохо предсказываемый. Если бы все - тело цикла стало бы линейным и проблем не было. Что собственно я и сделал. Да, код стал не эквивалентным.

[Andrey_Kireew]

Попробовал так:

Используется синтаксис C

while (b<F) 
    {if (*ind>0) 
          if (*b!=0) break; 
                 ind++; b++;}
 

(в коде Dmitriy40 есть ошибка - первый break; не нужно)

... ну побыстрее стало, примерно на 10%, причём запускал несколько раз - во всех случаях заметен этот небольшой прирост.

А зачем менять потинкремент на прединкремент? что так быстрее будет?

-- 30.07.2018, 21:24 --

Поменял я

ind++; b++;

на

++ind; ++b;

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

[Dmitriy40]

Да, у меня ошибка.
Но Ваш код от исходного в общем-то ничем не отличается, так же первый условный переход плохо предсказываем и может выполняться без выхода из цикла, т.е. нарушает линейность выполнения.
Тогда как сделать без операции | вместо || (или & вместо &&) я не знаю. А это не есть good practice.
Тогда считаю лучшим решение worm2.

-- 30.07.2018, 20:36 --

Andrey_Kireew в сообщении #1329608 писал(а):

А зачем менять потинкремент на прединкремент? что так быстрее будет?

Для изменения простой переменной - нет, практически одинаково (при достаточно умном компиляторе). А вот в сложных выражениях, в принципе да, будет быстрее. Сравните требуемые операции:

b=*++p;
//Прочитать p
//Увеличить
//Сохранить обратно
//Использовать как адрес

b=*p++;
//Прочитать p
//Скопировать - вот и лишняя операция и лишний регистр, которых и так мало
//Увеличить копию
//Сохранить обратно
//Использовать как адрес

Возможен и ещё хуже вариант (зависит от компилятора):

b=*p++;
//Прочитать p
//Использовать как адрес
//Снова прочитать p - чтение памяти медленнее обращения к регистрам
//Увеличить
//Сохранить обратно

На самом деле всё это сильно зависит и от компилятора, и от процессора, и от окружающего кода. Например копирование регистра часто бесплатно, времени не занимает. Или чтение переменной из кэша тоже может времени не требовать (если будет предсказано правильно и data path свободен).
Так что на такие мелочи обращать внимание себе дороже, если только профилировщик прямо показывает что тормоза именно в них.

[Andrey_Kireew]

А можно ли как то оптимизировать вот этот "злой" код

Используется синтаксис C

for (ii=0; ii<NCol; ii++)
     if (*(fe+ii)==0)
        for (k=0; k<NStr; k++)
            if (*(aPos[ii]+k)>0)
               {nAlt++; break;}
 

а то, он несоразмерно своей пользе "пожирает" ресурсы, но и без него тоже не желательно

-- 30.07.2018, 21:50 --

Dmitriy40 в сообщении #1329611 писал(а):

Сравните требуемые операции:...

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

b++;

и всё. В этом случае тоже влияет "пред" или "пост" ? Я вообще наивно полагал, что постинкремент позволяет продолжать программу не дожидаясь завершения этой операции, что может дать прирост производительности ...

[Dmitriy40]

Я бы вынес из внутреннего цикла вычисление aPos[ii]. А потом и вообще убрал бы суммирование с k переходом на указатель, примерно так:

Используется синтаксис C

for (ii=0; ii<nCol; ii++)
    if (*(fe+ii)==0) {
        int * p = aPos[ii];//Указать правильный тип
        int * s = p + NStr;//Указать правильный тип
        for (; p<s; p++)
            if (*p==0) {nAlt++; break;}
    }

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

Andrey_Kireew в сообщении #1329614 писал(а):

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

Смеётесь что ли?! Переменные обычно в памяти лежат, а не в регистрах, процессор всё равно же прочитает внутрь, увеличит и запишет обратно.
Для простой переменной разницы практически нет.

[Andrey_Kireew]

Используется синтаксис C

for (ii=0; ii<NCol; ii++)
     if (*(fe+ii)==0)
     for (ind=aPos[ii]; ind<aPos[ii+1]; ind++)
            if (*ind>0)
               {nAlt++; break;}
 

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

[Dmitriy40]

Здесь Вы гораздо больше полагаетесь на "умность" компилятора, что он сам вынесет константы (aPos[ii+1]) за тело цикла, я бы сделал это руками:

for (ind=aPos[ii], stop=aPos[ii+1]; ind<stop; ind++)

С хорошим компилятором разницы быть не должно.

Ну и не стоит сравнивать указатели на разные строки массивов (конкретно на [ii] и [ii+1]), мало ли как хранятся массивы, вдруг там есть зазоры между строками (например от выравнивания структур данных), хоть C/C++ и обещают всё линейно держать (а другие языки с похожим синтаксисом не обещают, вот будет радость искать глюки).
И выражение [ii+1] может выйти за границу массива aPos!
Всё же такой код лучше:

for (ind=aPos[ii], stop=ind+NStr; ind<stop; ind++)