2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5  След.
 
 оптимизация сравнений в С++
Сообщение30.07.2018, 07:10 


07/10/15

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


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

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

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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 08:49 
Заслуженный участник


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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 09:44 
Заслуженный участник


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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 10:21 
Аватара пользователя


31/10/08
1244
Я бы так сделал. Сравнение 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 


07/10/15

2400
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 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Возможно, так прокатит:
Используется синтаксис 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 
Заслуженный участник


20/08/14
11064
Россия, Москва

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

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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 19:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 19:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение30.07.2018, 20:10 


07/10/15

2400
Попробовал так:
Используется синтаксис 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 
Заслуженный участник


20/08/14
11064
Россия, Москва
Да, у меня ошибка. :-(
Но Ваш код от исходного в общем-то ничем не отличается, так же первый условный переход плохо предсказываем и может выполняться без выхода из цикла, т.е. нарушает линейность выполнения.
Тогда как сделать без операции | вместо || (или & вместо &&) я не знаю. А это не есть 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 


07/10/15

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

Используется синтаксис 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 
Заслуженный участник


20/08/14
11064
Россия, Москва
Я бы вынес из внутреннего цикла вычисление 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 


07/10/15

2400
Используется синтаксис 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 
Заслуженный участник


20/08/14
11064
Россия, Москва
Здесь Вы гораздо больше полагаетесь на "умность" компилятора, что он сам вынесет константы (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  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group