2014 dxdy logo

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

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




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


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


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


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

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

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

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


23/12/05
10807
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 


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

-- 08.08.2018, 11:21 --

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

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


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

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

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


27/08/16
4885

(Оффтоп)

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

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


23/12/05
10807
realeugene в сообщении #1331154 писал(а):
не факт, что это будет unsigned int

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

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


27/08/16
4885
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 
Экс-модератор
Аватара пользователя


23/12/05
10807
realeugene в сообщении #1331159 писал(а):
Вы, действительно, считаете, что это - преимущество?

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

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


27/08/16
4885
photon в сообщении #1331161 писал(а):
Не всегда, но я могу представить ситуации, где это будет преимуществом
Я же могу представить, сколько в таких случаях потребуется внести изменений во всевозможные места в коде, где используется такая переменная, чтобы не заморачиваться тем, какой изначально был написан тип при её определении. Добавление новых значений к ранее булевскому типу - это неслабое изменение именно семантики такой переменной.

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


23/12/05
10807
realeugene в сообщении #1331163 писал(а):
Добавление новых значений к ранее булевскому типу
Э-э... Какой булевской переменной? На данный момент у автора анализируется double и никаких булевских переменных нет.

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

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


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

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

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


23/12/05
10807
realeugene в сообщении #1331179 писал(а):
Вот и не нужно искать себе приключений раньше времени

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

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


27/08/16
4885
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 
Экс-модератор
Аватара пользователя


23/12/05
10807
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 
Заслуженный участник


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

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

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

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



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

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


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

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