2014 dxdy logo

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

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




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


07/10/15
1522
В общем всем спасибо!
хотя особого прироста я так и не добился, зато теперь уж знаю, что возможности для оптимизации тут весьма не велики

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


20/08/14
5502
Россия, Москва
Сами эти два цикла да, оптимизировать тяжело. Но можно попробовать вообще их исключить и проверять положительность элементов массива в точке их ввода или вычисления. Этим снимется чтение матрицы из памяти, а большие матрицы в кэши не помещаются и скорость чтения ограничена скоростью памяти (10..30 ГБ/с). Проверка же числа на положительность быстра относительно процесса ввода или вычисления, т.е. там нагрузка изменится не сильно, зато обрамляющий код циклов там и так уже есть, да и данные ещё лежат в регистрах. Например конкретно такую проверку я бы сделал как дополнительный массив в одну колонку с флагом есть ли в строке основного массива положительные числа и в цикле вычислений (или ввода) устанавливал бы бит в этом массиве. При желании можно даже аккуратно счётчик nAlt там же изменить (если до установки бит в массиве был сброшен, то увеличить).
Общее количество операций примерно такое же или даже немного больше, зато отсутствует медленное чтение всей матрицы и накладные расходы на циклы.

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


07/10/15
1522
Спасибо Dmitriy40, хорошая идея, надо будет попробовать

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


23/12/05
10807
1) В процессе формирования массивов можно сделать мапу на элементы, удовлетворяющие вашим требованиям (если их не очень много)
2) Если массивы используются вместе имеет смысл объединить их в один вектор структур или пар, чтобы обрабатываемые данные не валялись в разных местах памяти.

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


07/10/15
1522
photon здесь плохо то, что массивы многократно пересчитываются, собственно - это и есть основная часть алгоритма, основное время тратится на неё. Поэтому, новый массив с индексами "true" и "false" тоже придётся пересчитывать каждый раз. Я внимательно изучил алгоритм, на предмет того, не вылетают ли эти значения где то в явном виде, с тем, чтобы их можно было просто записать по ходу дела (у меня подобным образом индексируются нуль-столбцы и от этого есть очень большой выигрыш), но нет, чтобы их определить, нужно проводить проверку почти полностью.

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

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


27/08/16
4886
Dmitriy40 в сообщении #1329641 писал(а):
С хорошим компилятором разницы быть не должно.
Это если оптимизация в компиляторе включена.

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

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


20/08/14
5502
Россия, Москва
realeugene
Хорошо, специально для Вас уточню: слова выше "хорошим компилятором" читать как "хорошо оптимизирующим компилятором". Плохо (или совсем не) оптимизирующий компилятор сюда не подпадает.

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

Кстати, раз уж всё равно стал отвечать, добавлю:
photon в сообщении #1330924 писал(а):
2) Если массивы используются вместе имеет смысл объединить их в один вектор структур или пар, чтобы обрабатываемые данные не валялись в разных местах памяти.
это не всегда хорошо работает, иногда сложность вычисления адресов съедает выигрыш от data prefetch (пример: проход по массиву 100 байтных записей я бы сделал на указателе на начало записи и смещении внутри записи, как это реализует компилятор я не знаю и не знаю как это ему порегулировать, надеюсь хоть не будет для каждого поля вычислять заново и начальный адрес всей записи - а я видел и такое вживую) или некоторые поля записи не всегда нужны и их чтение зря расходует объём кэша и трафик памяти. Но это уже довольно тонкие вопросы, которые многим проще оценить на практике, чем вникать в ассемблерный код и архитектуру процессора.
Для пар же простых (и лучше одинаковых) типов, да и во многих других простых случаях, совет работает хорошо.

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


11/12/14
877
А какого типа элементы массивов?
Совсем недавно сталкиваться с синтетическими тестами, где перевод обработки массивов байт (алгоритм блиттинга с нулевой маской прозрачности) на SSE давал прирост производительности до нескольких десятков раз. Даже поразительно было видеть такое ускорение.
Более того - хорошо помогала даже работа с байтами через long long в духе эзотерической перетусовки битовых масок, сам факт того, что не по байту гоняется в кеш и обратно давал практически линейное ускорение от ширины передаваемых данных.

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


27/08/16
4886
Dmitriy40 в сообщении #1330965 писал(а):
Хорошо, специально для Вас уточню: слова выше "хорошим компилятором" читать как "хорошо оптимизирующим компилятором". Плохо (или совсем не) оптимизирующий компилятор сюда не подпадает.
У хорошего оптимизирующего компилятора обязательно есть настройки, которые нужно включить, чтобы он хорошо оптимизировал. Или забыть включить. Боюсь, не все про это знают. Судя по уровню знаний ТС, он легко может всё компилировать в режиме Debug с отключённой оптимизацией.

Dmitriy40 в сообщении #1330965 писал(а):
Чтобы подглядывать в генерируемый код (с чем я абсолютно согласен) надо хоть немного разбираться в целевой архитектуре. Не все это знают и не всем это интересно,
Неинтересно - вот и нефиг фигнёй тогда страдать.

Dmitriy40 в сообщении #1330965 писал(а):
есть чисто алгоритмические приёмы оптимизаций (и вынос инваринта цикла за тело цикла к ним относится).
В этой теме обсуждается именно микрооптимизация. С выносом инвариантов из цикла в большинстве подобных случаев компилятор справится и сам.

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


07/10/15
1522
aa_dav в сообщении #1331024 писал(а):
А какого типа элементы массивов?


double

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


23/12/05
10807
1) Чисто для проверки: вы билдите в релизе с уровнем оптимизации O2, O3 или Ох?
2) Если нет острой необходимости в типе double, лучше его не использовать. Бывают случаи, когда не обойтись, но обычно float хватает с головой. Если вопрос быстродействия критичен, то можно и вовсе перейти на целочисленную арифметику - сейчас, как правило, выигрыш уже не очень большой, но обычно все-таки есть.

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


07/08/14
2880
Не знаю, как устроено представление чисел в c++, но идея такова:
если 0 имеет признак чётности, то сперва выбираются в модуль сравнения с нулем только чётные значения из всего массива имеющихся.
В этом случае количество операций сравнения нулем упадет примерно в два раза (правда возможно за счет роста количества операцией проверки чётности), а так как считывать значения для сравнения все равно надо при любом алгоритме, в целом производительность должна вырасти в том случае, если тактов на проверку четности требуется меньше, чем тактов на проверку на нуль.
Насколько я в курсе, иногда такие алгоритмы используются для получения элементов из коллекций - сперва проверяется четный адрес или нет, а затем если четный пробегаются только четные адреса, и выборка нужного элемента ускоряется в два раза.

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


23/12/05
10807
upgrade в сообщении #1331038 писал(а):
если 0 имеет признак чётности, то сперва выбираются в модуль сравнения с нулем только чётные значения из всего массива имеющихся.

Это плохая идея. Многократный проход по массиву с выбором сначала одного, потом другого обойдется дороже операций сравнения.

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


27/08/16
4886
upgrade в сообщении #1331048 писал(а):
1. проверка на четность
если да
2. проверка на минус
если первую проверку выдержал, переходим ко второй, если вторую не выдержал - значит это ноль
Или 2.

(Оффтоп)

Вы издеваетесь?

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


07/08/14
2880
photon в сообщении #1331039 писал(а):
Многократный проход по массиву с выбором сначала одного, потом другог

Почему многократный. Для сравнения массив разделяется на два - четные значения и нечетные.
Затем для нечетных проверяется только минус, а для четных - минус и ноль.
Если $100$ элементов, то всех сверок $150$.
А если проверять каждый на ноль и на минус, то $200$ (и те и другие проверяются на минус и на ноль).
А если проверяем только на ноль (переменную $*b$), то выбираем только четные из $100$ и всего проверок будет примерно $50$.
Вот если проверка четности требует больше ресурсов, чем проверка на ноль, то смысла нет, а если меньше, то есть.

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

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



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

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


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

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