2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4, 5  След.
 
 оптимизация сравнений в С++
Сообщение30.07.2018, 07:10 
Добрый вечер,
в процессе доработки одной из программ, пришлось добавить много разных условий, видимо в критичном, часто повторяющемся месте, и быстродействие кода заметно упало. Вот пример:
Используется синтаксис C
while (((*ind<=0) || (*b==0)) && (b<F))
    {ind++; b++;}
 


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

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

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

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 09:44 
На вид в нем нет ничего улучшаемого (ну разве что постинкременты на прединкременты для порядка заменить), но Вы уверены, что дело в нем? В реалистичных условиях заметное замедление тут можно получить только при многократном вызове этого участка, но тогда лучше бы понять, можно ли без этого обойтись.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 10:21 
Аватара пользователя
Я бы так сделал. Сравнение 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.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 10:43 
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 -это адрес, он никогда не будет нулевым, какой тогда смысл "гнать" их в обратную сторону?

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 12:56 
Аватара пользователя
Возможно, так прокатит:
Используется синтаксис C
while (1)
    while ((*ind<=0) && (b<F)) // урезанное условие, проверяющееся быстро
        {ind++; b++;}
    if ( (b>=F) || ((*ind>0) && (*b!=0)) ) // полное условие (инвертированное)
        break;
    ind++; b++;
}

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 19:28 

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

Не будет ли быстрее такой вариант?
Код:
while (b < F) {
    if (*ind > 0) break;
    if (*b != 0) break;
    ++ind; ++b;
}
Смысл в исключении условия ИЛИ внутри цикла и замены его на два отдельных условия завершения цикла. При этом тело цикла будет выполняться строго линейно до наступления условия выхода из цикла и не будет никаких плохо предсказанных переходов (кроме самого цикла, который предсказывается отлично). Экономится вычисление логического ИЛИ и ошибка предсказания условного перехода, но тратится обращение ко второму массиву, надо выбирать что быстрее.
Т.е. предположение что тормозом является плохо предсказываемый переход при вычислении операции ИЛИ в условии цикла. При этом операции И в условии цикла линейности выполнения не нарушают.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 19:45 
Аватара пользователя
А что, в C++ всегда вычисляются все логические операнды??

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 19:53 
Вроде бы нет, поэтому и условный переход, плохо предсказываемый. Если бы все - тело цикла стало бы линейным и проблем не было. Что собственно я и сделал. Да, код стал не эквивалентным.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 20:10 
Попробовал так:
Используется синтаксис 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;
, непонятно, то ли есть прирост, то ли нет, каждый раз по разному выходит. Явно различия, если и есть - то несущественные.

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

-- 30.07.2018, 20:36 --

Andrey_Kireew в сообщении #1329608 писал(а):
А зачем менять потинкремент на прединкремент? что так быстрее будет?
Для изменения простой переменной - нет, практически одинаково (при достаточно умном компиляторе). А вот в сложных выражениях, в принципе да, будет быстрее. Сравните требуемые операции:
Код:
b=*++p;
//Прочитать p
//Увеличить
//Сохранить обратно
//Использовать как адрес
Код:
b=*p++;
//Прочитать p
//Скопировать - вот и лишняя операция и лишний регистр, которых и так мало
//Увеличить копию
//Сохранить обратно
//Использовать как адрес
Возможен и ещё хуже вариант (зависит от компилятора):
Код:
b=*p++;
//Прочитать p
//Использовать как адрес
//Снова прочитать p - чтение памяти медленнее обращения к регистрам
//Увеличить
//Сохранить обратно

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 20:43 
А можно ли как то оптимизировать вот этот "злой" код

Используется синтаксис 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++;
и всё. В этом случае тоже влияет "пред" или "пост" ? Я вообще наивно полагал, что постинкремент позволяет продолжать программу не дожидаясь завершения этой операции, что может дать прирост производительности ...

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 21:03 
Я бы вынес из внутреннего цикла вычисление 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 писал(а):
но у меня то нет никакого чтения по адресу
Смеётесь что ли?! Переменные обычно в памяти лежат, а не в регистрах, процессор всё равно же прочитает внутрь, увеличит и запишет обратно.
Для простой переменной разницы практически нет.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 21:39 
Используется синтаксис 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;}
 


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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 22:39 
Здесь Вы гораздо больше полагаетесь на "умность" компилятора, что он сам вынесет константы (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++)

 
 
 [ Сообщений: 72 ]  На страницу 1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group