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

[Andrey_Kireew]

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

[Dmitriy40]

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

[Andrey_Kireew]

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

[photon]

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

[Andrey_Kireew]

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

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

[realeugene]

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

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

Это если оптимизация в компиляторе включена.

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

[Dmitriy40]

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

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

Кстати, раз уж всё равно стал отвечать, добавлю:

photon в сообщении #1330924 писал(а):

2) Если массивы используются вместе имеет смысл объединить их в один вектор структур или пар, чтобы обрабатываемые данные не валялись в разных местах памяти.

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

[aa_dav]

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

[realeugene]

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

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

У хорошего оптимизирующего компилятора обязательно есть настройки, которые нужно включить, чтобы он хорошо оптимизировал. Или забыть включить. Боюсь, не все про это знают. Судя по уровню знаний ТС, он легко может всё компилировать в режиме Debug с отключённой оптимизацией.

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

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

Неинтересно - вот и нефиг фигнёй тогда страдать.

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

есть чисто алгоритмические приёмы оптимизаций (и вынос инваринта цикла за тело цикла к ним относится).

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

[Andrey_Kireew]

aa_dav в сообщении #1331024 писал(а):

А какого типа элементы массивов?

double

[photon]

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

[upgrade]

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

[photon]

upgrade в сообщении #1331038 писал(а):

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

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

[realeugene]

upgrade в сообщении #1331048 писал(а):

1. проверка на четность
если да
2. проверка на минус
если первую проверку выдержал, переходим ко второй, если вторую не выдержал - значит это ноль

Или 2.

(Оффтоп)

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

[upgrade]

photon в сообщении #1331039 писал(а):

Многократный проход по массиву с выбором сначала одного, потом другог

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