2014 dxdy logo

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

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




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


27/08/16
5107
Pavia в сообщении #1329497 писал(а):
Сравнение 0 это бесплатная операция в отличие от F.

В современных процессорах нет разницы: всё равно нужно сначала сравнить число с другим числом в регистре, чтобы сформировать флаги (с нулём можно сформировать флаги какой-нибудь другой операцией, но тоже отдельной), а потом выполнить команду условного перехода.

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение07.08.2018, 17:34 
Экс-модератор
Аватара пользователя


23/12/05
10983
upgrade в сообщении #1331050 писал(а):
Почему многократный. Для сравнения массив разделяется на два - четные значения и нечетные.

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

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


07/08/14
2937
photon в сообщении #1331058 писал(а):
На это разделение требуется дополнительный проход по массиву, да еще и переписывание куда-то отдельно четных, отдельно нечетных.

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

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


20/08/14
5591
Россия, Москва
Обход проверки (срабатывание условного перехода) стоит дороже выполнения лишней проверки (не срабатывания условного перехода). Из-за ошибок предсказания и предвыборки и исполнительного конвейера.

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


07/08/14
2937
Dmitriy40 в сообщении #1331062 писал(а):
Обход проверки (срабатывание условного перехода) стоит дороже выполнения лишней проверки

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

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


27/08/16
5107
upgrade,
вы с системой команд какого процессора знакомы?

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


07/08/14
2937
8086 был знаком, теперь никакого...а для c++ толк то есть знакомиться с командами процессора?

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


27/08/16
5107
upgrade в сообщении #1331066 писал(а):
8086 был знаком

Каким образом у 8086 протестировать бит можно было быстрее, чем сравнить с нулём или любой другой константой? Константа уже в регистре.

Какой командой проверить на чётность числа типа double? Это, правда, относится к 8087.

upgrade в сообщении #1331066 писал(а):
а для c++ толк то есть знакомиться с командами процессора?
Хотя бы для того, чтобы не советовать настойчиво чепуху.

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


20/08/14
5591
Россия, Москва
upgrade в сообщении #1331063 писал(а):
Не факт, проверка на четность может стоить дешевле проверки на ноль, это тестировать надо. Ведь проверка на четность битовая (младший бит ноль - выбираем только значения с нулевым младшим битом), а битовые операции очень быстрые.
upgrade в сообщении #1331066 писал(а):
8086 был знаком, теперь никакого...
Вы не правы даже насчёт него, специально открыл бумажную книжку:
Код:
;8086
cmp ax,i  - 4 такта
cmp r,i   - 4 такта
test ax,i - 4 такта
test r,i  - 5 тактов

Ну и за 40 лет развития техника ушла вперёд и сейчас они занимают по 1 (или по 0.25 в потоке) такту обе одинаково.

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


07/10/15
1522
photon да нет, как раз double менять ни на что не нужно, точность как раз такая и нужна, иначе "выплывут" намного более серьёзные проблемы

 Профиль  
                  
 
 Re: оптимизация сравнений в С++
Сообщение07.08.2018, 19:09 
Экс-модератор
Аватара пользователя


23/12/05
10983
Andrey_Kireew в сообщении #1331074 писал(а):
как раз double менять ни на что не нужно

Хорошо, но более существенная часть вопроса:
photon в сообщении #1331035 писал(а):
1) Чисто для проверки: вы билдите в релизе с уровнем оптимизации O2, O3 или Ох?

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


07/10/15
1522
photon в сообщении #1331076 писал(а):
Хорошо, но более существенная часть вопроса:
photon в сообщении #1331035 писал(а):
1) Чисто для проверки: вы билдите в релизе с уровнем оптимизации O2, O3 или Ох?


O2 /Oy- /DNDEBUG

-- 07.08.2018, 21:40 --

У меня получилось быстро найти некоторые индексы, массивы для которых проверять не нужно. Для проверки, временно, я "забаниваю" эти позиции единицами. Быстродействие проверяю просто через clock(). До изменений было 62 тика, после - всего 2 тика. Выигрыш очень хороший. Видимо, после изменений, остаётся проверить очень немного массивов.

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

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


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

(Как я бы сделал исходную задачу поиска первого положительного double значения в массиве/строке)

Я бы векторизовал внутренний цикл поиска на AVX, примерно так (для архитектуры Haswell):
Код:
int FindByFirst0(double * p, int len) {//Цикл поиска первого положительного значения в одной строке массива
   double * s = p + len;
   while ((p < s) && (p & 0x1F != 0))//Цикл до обнуления младших 5 битов адреса
      if (*p++ > 0) return 1;
   int n = (s & -32) / 8 / 4;//Проверяем по 4 элемента
//   while (n != 0) {
//      if (test32(p)) break;//Проверка сразу 4-х элементов
//      p += 4;//Проверяем по 4 элемента
//      --n;
//   }
   asm {
   mov   ESI,p
   mov   ECX,n
   jecxz   .find
   vpxor   ymm0,ymm0,ymm0
.scan:
   vcmppd   ymm1,ymm0,[ESI],1
   vptest   ymm1,ymm1
   jnz   .find
   add   ESI,32
   dec   ECX
   jnz   .scan
.find:
   mov   p,ESI
   }
   //Сюда попадает если в 4-х элементах начиная с p найдено условие останова или дошли [почти] до конца массива
   while (p < s)
      if (*p++ > 0) return 1;
   return 0;
}
//Использование:
for (ii = 0; ii < nCol; ii++)
   if (*(fe + ii) == 0)
      nAlt += FindByFirst0(aPos[ii], NStr);
Весь цикл scan выполняется 1.5 такта на 4 элемента до момента нахождения условия останова. При этом все 4 вычислительных конвейера (0,1,5,6) заняты на 100% (и потому Hyper-threading полностью в пролёте). А конвейеры чтения памяти заняты на 33%.
Итоговая скорость примерно 10млрд чисел в секунду на ядро, при том что DDR3-1600 память в двухканальном режиме выдаёт лишь 3млрд чисел в секунду (DDR4-2400 выдаёт меньше 5млрд) и будет тормозом.
С single числами скорость была бы ровно вдвое выше.

При развороте цикла вчетверо с объединением результатов тремя командами vpor и одной vptest и одним условным переходом получим предельно возможную скорость 0.25 такта на число, меньше не может быть из-за 100% загрузки 1-го конвейера командой vcmppd (потому и HT данной программе не поможет). Зато остальные конвейеры загружены на 62% (0 и 5) и 75% (6) и 50% (чтение памяти).
Но память даже двухканальная DDR4-2400 столько чисел выдать не успеет и будет тормозом.

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


07/10/15
1522
Andrey_Kireew в сообщении #1329614 писал(а):
А можно ли как то оптимизировать вот этот "злой" код

Используется синтаксис C
for (ii=0; ii<NCol; ii++)
     if (*(fe+ii)==0)
        for (k=0; k<NStr; k++)
            if (*(aPos[ii]+k)>0)
               {nAlt++; break;}
 




в итоге пришел к такому решению, копирую строку fe, чтобы её не "попортить":
Используется синтаксис C
double *scopy=new double [Len*sizeof(double)];
memcpy(scopy, fe, Len*sizeof(double));

........... // в элементы scopy соответствующие массивам, которые не нужно проверять записывается "1"

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

delete [] scopy;
 


этот кусок помещается в удобном месте кода, так что легко пометить массивы, которые проверять не нужно,
потом scopy за не надобностью удаляется.

Получилось стройно и мнемонично. Работает быстро, в том плане, что скорость выполнения этого фрагмента роли уже не играет.

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

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


28/07/17
236
Andrey_Kireew в сообщении #1331089 писал(а):
У меня получилось быстро найти некоторые индексы, массивы для которых проверять не нужно. Плохо то, что "забанивать" единицами неправильно, на этих местах наряду с нулями могут быть информативные параметры, которые "затирать" нельзя никак.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

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



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

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


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

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