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

[Andrey_Kireew]

FomaNeverov в сообщении #1331137 писал(а):

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

Это только на первый взгляд будет хорошо и правильно, можно конечно создать массив flag с нулями и единицами, а потом проверять, например так:

Используется синтаксис C

if ((*(fe+ii)==0) && (*(flag+ii)==0))
.........................
 

конечно можно, и скорость особо не изменится, но всё же, зачем это нужно?

Дополнительный массив будет так и так. Здесь его, конечно можно сделать bool, но на 64 битной машине от этого толку не особо. Массив этот всё равно нужно инициализировать, так что скорость его создания в том и другом случаях, не на много будет отличаться.
Зато появляется дополнительное сравнение (хоть и говорят, что сравнение с нулём "беспатно", но кто его знает) и дополнительное логическое "и".

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

[photon]

Andrey_Kireew в сообщении #1331138 писал(а):

Если не в вычислительном плане, то в семантическом уж точно (потом намного труднее будет разобраться что там к чему)

Так часто бывает: или красиво, или быстро.
Для повышения удобочитаемости я бы
1) писал не

Используется синтаксис C

*(flag+ii)

а

Используется синтаксис C

flag[ii]

2) Дал переменным более длинные, но понятные имена - через месяц вы забудете, что такое fe и о чем маякует флаг
3) Расставил фигурные скобки для циклов и условий даже если в их теле только одна операция
4) Использовал std::vector (или сделал свой аналог) вместо массивов - нет необходимости думать о delete и некоторые другие плюшки.

Andrey_Kireew в сообщении #1331138 писал(а):

и дополнительное логическое "и"

Вторая проверка сработает только если первая проверка даст true. Поэтому, кстати, будет работать быстрее, если в случае логического "и" первой проверкой ставить ту, что чаще false, чтобы не проверять вторую, а в случае логического "или" наоборот.

Andrey_Kireew в сообщении #1331138 писал(а):

Здесь его, конечно можно сделать bool, но на 64 битной машине от этого толку не особо.

Разница есть. Короткие типы, требуют меньше памяти и если массив большой, то его куски реже надо будет подгружать в кэш. Если же вы решите векторизовать проверки, то это станет еще более критичным. Я бы без векторизации делал char.



Представим, что вы завели отдельный массив, в котором отмечаете, какие элементы проверять надо, а какие нет.
1) В процессе работы могут проверяемые стать непроверяемыми? А наоборот?
2) Какое хотя бы примерное соотношение тех, что надо проверять и тех, что не надо?
3) О каких вообще размерах массивов хотя бы примерно идет речь?

[realeugene]

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

Я бы без векторизации делал char.

Спорный совет. Для большинства современных процессоров bool и так будет однобайтным. Если уж оптимизировать последовательный доступ к флагам, то можно завести битовые маски в максимальном укладывающемся в регистр целочисленном типе (не факт, что это будет unsigned int, ну а польза или вред от такого решения зависит от много чего не упомянутого тут).

-- 08.08.2018, 11:21 --

Andrey_Kireew в сообщении #1331138 писал(а):

хоть и говорят, что сравнение с нулём "беспатно", но кто его знает

Врут.

[photon]

realeugene в сообщении #1331154 писал(а):

Спорный совет. Для большинства современных процессоров bool и так будет однобайтным. Если уж оптимизировать последовательный доступ к флагам, то можно завести битовые маски в максимальном укладывающемся в регистр целочисленном типе (не факт, что это будет unsigned int, ну а польза или вред от такого решения зависит от много чего не упомянутого тут)

Тут есть свои если. Если нет большого перекоса по числу true и false, то собирание большого числа бит и оптовая проверка ничего вам не даст - заполнили, получили, что среди ваших, скажем, 128 бит есть ненулевые, а потом все равно разбираете, какие из них какие. char удобен тем, что у него при той же однобайтности больше гибкость, чем у bool - если надо будет, то мы сможем потом в него запихнуть не только 0 и 1, но и, например, -1 и 42, которые будут в том же байте о чем-то говорить.

[realeugene]

(Оффтоп)

Andrey_Kireew в сообщении #1331138 писал(а):

потом намного труднее будет разобраться что там к чему

Смешно. Раньше о стиле нужно было думать. Теперь только могила полный рефакторинг кода его исправят.

[photon]

realeugene в сообщении #1331154 писал(а):

не факт, что это будет unsigned int

У 64-разрядного процессора? - это к гадалке не ходи, что он не будет unsigned int.

[realeugene]

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

Тут есть свои если. Если нет большого перекоса по числу true и false, то собирание большого числа бит и оптовая проверка ничего вам не даст - заполнили, получили, что среди ваших, скажем, 128 бит есть ненулевые, а потом все равно разбираете, какие из них какие.

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

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

char удобен тем, что у него при той же однобайтности больше гибкость, чем у bool - если надо будет, то мы сможем потом в него запихнуть не только 0 и 1, но и, например, -1 и 42, которые будут в том же байте о чем-то говорить.

Вы, действительно, считаете, что это - преимущество?

-- 08.08.2018, 11:38 --

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

У 64-разрядного процессора? - это к гадалке не ходи, что он не будет unsigned int.

У x64 - да.

[photon]

realeugene в сообщении #1331159 писал(а):

Вы, действительно, считаете, что это - преимущество?

Не всегда, но я могу представить ситуации, где это будет преимуществом

[realeugene]

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

Не всегда, но я могу представить ситуации, где это будет преимуществом

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

[photon]

realeugene в сообщении #1331163 писал(а):

Добавление новых значений к ранее булевскому типу

Э-э... Какой булевской переменной? На данный момент у автора анализируется double и никаких булевских переменных нет.

char без дополнительных затрат места - это потенциально готовый набор из восьми битовых флагов, проверка выполнения комплекса флагов - всего лишь битовая маска, а не, как будет в вашем случае, соответствующее число проверок, если вы под каждый флаг будете делать свой массив булек.

[realeugene]

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

Э-э... Какой булевской переменной? На данный момент у автора анализируется double и никаких булевских переменных нет.

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

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

char без дополнительных затрат места - это потенциально готовый набор из восьми битовых флагов, проверка выполнения комплекса флагов - всего лишь битовая маска, а не, как будет в вашем случае соответствующее число проверок, если вы под каждый флаг будете делать свой массив булек.

Вот и не нужно искать себе приключений раньше времени, когда не известно, нужны ли дополнительные флаги. А независимые бульки отлично упаковываются компилятором в структуры как битовые поля, когда такая упаковка осмысленна (а она осмысленна далеко не всегда, так как модификация битового поля сложнее модификации бульки в виде целого байта). Правда, компилятору помочь нужно, указав булевским полям размер один бит. И они прекрасно упакуются побитово. Впрочем, давно это не проверял, может быть, сейчас компиляторы уже и поумнели. Но читаемость кода с булями шириной в 1 бит сохраняется. Что сделает компилятор с одновременной проверкой нескольких флагов при этом - смотреть нужно, умеет ли он хорошо сам оптимизировать вычисление логических выражений с побитовыми операциями над одно переменной. Я не проверял и зарекаться не буду. Но сам принцип "не оптимизируй свой код раньше времени", в любом случае, никто не отменял.

[photon]

realeugene в сообщении #1331179 писал(а):

Вот и не нужно искать себе приключений раньше времени

А где тут приключения?
на данный момент разница будет сводиться к

Используется синтаксис C

flag[i]

vs

Используется синтаксис C

1 == flag[i]

[realeugene]

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

на данный момент разница будет сводиться к

Конечно, у булевских признаков должны быть осмысленные имена. Например, 'IsUsed' или 'IsZero'. То есть:

flags[i].IsUsed

или просто

IsUsed[i]

А писать

1 == flag[i]

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

1. Что, вообще, означает флаг с маской '1' в поле flag?
2. Что будет означать значение flag, равное 3?
3. Значения там 3 быть первоначально не могло? А что случится, если добавят второй флаг с маской 2, как вы предполагаете? Программа молча перестанет работать по непонятной причине?
4. И это значит, что в вашем таком простом коде уже затаилась ошибка: вы сами подразумевали, что в этом поле можно безболезненно добавить новые флаги, но в коде написали

1 == flag[i]

вместо

(flag[i] & 1)

. То есть написанный вами код не отражает принятых вами предположений об этой переменной.

[photon]

realeugene в сообщении #1331201 писал(а):

Конечно, у булевских признаков должны быть осмысленные имена. Например, 'IsUsed' или 'IsZero'.

Я бы не писал "flag" в своей программе, если планируется время жизни кода больше пары дней, но здесь я следовал нотации, принятой топикстартером, а вы уводите куда-то в сторону: то рассказываете про добавление к имеющемуся булевскому типу, которого у ТС не имелось, то порождаете переменные, имена которых, хотя и хорошие в сравнении с авторскими, но выпадают из того, что уже предложил ТС

realeugene в сообщении #1331201 писал(а):

1. Что, вообще, означает флаг с маской '1' в поле flag?
2. Что будет означать значение flag, равное 3?

Используется синтаксис C

unsigned char const IS_MALE =   0b00000001;
unsigned char const IS_ANIMAL = 0b00000010;
unsigned char const IS_FLYING = 0b00000100;

...

unsigned char const FLYING_ANIMAL_MASK = IS_ANIMAL | IS_FLYING;
...
if (FLYING_ANIMAL_MASK == (creature[i].properties & FLYING_ANIMAL_MASK))
{
// let fly
}
...
 

realeugene в сообщении #1331201 писал(а):

4. И это значит, что в вашем таком простом коде уже затаилась ошибка: вы сами подразумевали, что в этом поле можно безболезненно добавить новые флаги, но в коде написали

Идеологически, если я сразу точно уверен, что буду использовать сложные маски, то да, я поступил неправильно и даже вариант с "& 1" некрасивый - лучше использовать именованные константы, но, вероятно, в жизни до тех пор пока не появится необходимость запихнуть во флаг более одного признака, я все-таки буду использовать сравнение через равенство - тут уж сработает упомянутое вами "не оптимизируй раньше времени".


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

[Dmitriy40]

Помочь ТС оптимизировать его код нереально, он сначала просит оптимизировать кусок кода, а потом оказывается что что вся оптимизация насмарку т.к. ТС возвращается к изначальному коду, а оптимизации подвергается совсем другой кусок, предотвращающий вызов якобы оптимизируемого (причём замечу что отдельный массив флагов я давно предложил и уж точно не double).
А уж вопрос о разности множеств вообще феерия неясности.
Потому каждый в теме рассуждает об заинтересовавшем его ответвлении темы ... Я вот получил (асм+AVX2) на одном ядре скорость поиска почти впятеро больше скорости чтения памяти и застопорился, быстрее 0.25 такта на double число уже никак не получается.

По теме же байты vs биты (упакованные конечно) могу сказать следующее из личного опыта (решето Эратосфена): пока массив помещается в кэш любого уровня - байты лучше, особенно если надо и писать часто, код проще и оказывается быстрее. Когда в кэш не помещается - лучше биты, т.к. меньше трафик памяти, несмотря на увеличение исполняемого кода. Причём это вот "лучше" измеряется десятками процентов, а то и парой-тройкой раз.