2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 08:00 
FomaNeverov в сообщении #1331137 писал(а):
Ну так создайте ещё один массив (список, что угодно), в котором вашим многим массивам будут соответствовать единицы и нули - нужно проверять или нет. И исходные массивы трогать будет не нада.


Это только на первый взгляд будет хорошо и правильно, можно конечно создать массив flag с нулями и единицами, а потом проверять, например так:
Используется синтаксис C
if ((*(fe+ii)==0) && (*(flag+ii)==0))
.........................
 


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

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

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 09:48 
Аватара пользователя
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) О каких вообще размерах массивов хотя бы примерно идет речь?

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:18 
photon в сообщении #1331148 писал(а):
Я бы без векторизации делал char.
Спорный совет. Для большинства современных процессоров bool и так будет однобайтным. Если уж оптимизировать последовательный доступ к флагам, то можно завести битовые маски в максимальном укладывающемся в регистр целочисленном типе (не факт, что это будет unsigned int, ну а польза или вред от такого решения зависит от много чего не упомянутого тут).

-- 08.08.2018, 11:21 --

Andrey_Kireew в сообщении #1331138 писал(а):
хоть и говорят, что сравнение с нулём "беспатно", но кто его знает
Врут.

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

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:30 

(Оффтоп)

Andrey_Kireew в сообщении #1331138 писал(а):
потом намного труднее будет разобраться что там к чему
Смешно. Раньше о стиле нужно было думать. Теперь только могила полный рефакторинг кода его исправят.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:32 
Аватара пользователя
realeugene в сообщении #1331154 писал(а):
не факт, что это будет unsigned int

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:37 
photon в сообщении #1331155 писал(а):
Тут есть свои если. Если нет большого перекоса по числу true и false, то собирание большого числа бит и оптовая проверка ничего вам не даст - заполнили, получили, что среди ваших, скажем, 128 бит есть ненулевые, а потом все равно разбираете, какие из них какие.
Просто внутренний цикл с проверкой сдвигаемой битовой маской значения в регистре нередко эффективнее, чем последовательная загрузка по одному байту из памяти. Каким бы быстрым ни был кэш.

photon в сообщении #1331155 писал(а):
char удобен тем, что у него при той же однобайтности больше гибкость, чем у bool - если надо будет, то мы сможем потом в него запихнуть не только 0 и 1, но и, например, -1 и 42, которые будут в том же байте о чем-то говорить.
Вы, действительно, считаете, что это - преимущество?

-- 08.08.2018, 11:38 --

photon в сообщении #1331157 писал(а):
У 64-разрядного процессора? - это к гадалке не ходи, что он не будет unsigned int.
У x64 - да.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:41 
Аватара пользователя
realeugene в сообщении #1331159 писал(а):
Вы, действительно, считаете, что это - преимущество?

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 11:45 
photon в сообщении #1331161 писал(а):
Не всегда, но я могу представить ситуации, где это будет преимуществом
Я же могу представить, сколько в таких случаях потребуется внести изменений во всевозможные места в коде, где используется такая переменная, чтобы не заморачиваться тем, какой изначально был написан тип при её определении. Добавление новых значений к ранее булевскому типу - это неслабое изменение именно семантики такой переменной.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 14:56 
Аватара пользователя
realeugene в сообщении #1331163 писал(а):
Добавление новых значений к ранее булевскому типу
Э-э... Какой булевской переменной? На данный момент у автора анализируется double и никаких булевских переменных нет.

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 15:35 
photon в сообщении #1331174 писал(а):
Э-э... Какой булевской переменной? На данный момент у автора анализируется double и никаких булевских переменных нет.
В данном случае это уже вопрос не про ТС, а про ваш совет не делать булевские переменные. Который, на мой взгляд, сомнительный.

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

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 16:38 
Аватара пользователя
realeugene в сообщении #1331179 писал(а):
Вот и не нужно искать себе приключений раньше времени

А где тут приключения?
на данный момент разница будет сводиться к
Используется синтаксис C
flag[i]
vs
Используется синтаксис C
1 == flag[i]

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 17:15 
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)
. То есть написанный вами код не отражает принятых вами предположений об этой переменной.

 
 
 
 Re: оптимизация сравнений в С++
Сообщение08.08.2018, 18:47 
Аватара пользователя
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" некрасивый - лучше использовать именованные константы, но, вероятно, в жизни до тех пор пока не появится необходимость запихнуть во флаг более одного признака, я все-таки буду использовать сравнение через равенство - тут уж сработает упомянутое вами "не оптимизируй раньше времени".


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

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

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

 
 
 [ Сообщений: 72 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group