2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение13.11.2023, 18:41 
Аватара пользователя


05/06/08
477
Собственно, сабж.
Код:
a[j] =  k & pw[i];   или a[j] = k & (1<<i);

Код:
pw[i]
- статический массив степени двойки.
Думаю, второе. Хотя не факт, с учетом новых возможностей использования кеша процессора и оптимизации компилятора.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение13.11.2023, 19:46 
Заслуженный участник
Аватара пользователя


01/08/06
3131
Уфа
Смутно припоминаю, что лет 20 назад процессоры Pentinum обращались к индексированной памяти без потери времени (разумеется, если искомое лежит в L1 кэше), в то время как инструкции сдвига с переменным аргументом требовала нескольких тактов.
Ну то есть тогда я бы был за первый вариант, однозначно. Как сейчас — не знаю. Запросто может случиться, что зависит от архитектуры процессора.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение13.11.2023, 19:57 
Заслуженный участник
Аватара пользователя


16/07/14
9149
Цюрих
Сильно зависит от окружающего кода. Например если i меняется в цикле, то, в зависимости от деталей, первый вариант может быть развернут вообще в одну инструкцию. С другой стороны, если удастся вычислить заранее величину сдвига, то во втором варианте его вообще можно сделать в compile time.
В целом т.к. второй вариант компилятор легко может свести к первому, я сильно удивлюсь, если первый при включенной оптимизации окажется быстрее.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение13.11.2023, 20:54 
Заслуженный участник


18/09/21
1756
Это определяется не C++, а железом на котором исполняться будет.
Операция сдвига - дешевая операция которая встроена в ALU (arithmetic logic unit) в обычном процессоре вроде Intel.
На каком-нибудь контроллере (вроде как в Arduino) может ALU и без этого будет.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение13.11.2023, 21:32 
Заслуженный участник


20/08/14
11776
Россия, Москва
А ещё если a[] потом ни зачем не нужно кроме проверки в if, то может оптимизироваться до одной команды bt r,i (если i<64 и k в регистре) (выполняется 1 такт) с последующим условным переходом (если будет предсказан то вообще 0 тактов).

Вообще я за второй вариант, со сдвигом: вычисляемые обращения к массивам плохо предсказываются и скорость падает даже если весь массив в L1 (у него латентность 4 такта, а сдвиг выполнится за 1 такт).

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение14.11.2023, 17:38 
Аватара пользователя


05/06/08
477
Спасибо за ответы.
Если есть желание вопрос немного в сторону.
В американских форумах часто встречаю цикл в форме:
Код:
for (long j=0; j<L; ++j)

То есть плюсы слева. Может что-то экономится? Или просто такой стиль? Тот же вопарос по поводу long вместо int . Что-то архитектурное или просто стиль?

-- Вт ноя 14, 2023 19:02:27 --

На всякий случай, я понимаю разницу между while(++a) и while(a++).

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение14.11.2023, 18:08 
Заслуженный участник


18/09/21
1756
MGM в сообщении #1617897 писал(а):
То есть плюсы слева.
Здесь (внутри "for") - вообще без разницы.
(Разница, слева или справа, какое значение всё это даёт. Тут в "for" это значение вообще не используется.)

-- 14.11.2023, 18:11 --

MGM в сообщении #1617897 писал(а):
Тот же вопарос по поводу long вместо int

"long" - это допустимое сокращение "long int".
Что вам надо, "int" или "long int" - сами решайте.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение14.11.2023, 19:40 
Заслуженный участник


20/08/14
11776
Россия, Москва
MGM в сообщении #1617897 писал(а):
Может что-то экономится? Или просто такой стиль?
Скорее стиль. Это могло бы экономиться в компиляторах без оптимизатора (префиксная операция чуть проще в реализации), но вряд ли Вы с такими столкнётесь. Но ради большей совместимости могут и возвести в ранг стиля, мол "а вдруг".
Ну и да, в таких простых случаях это роли вообще не играет.
Можно было бы сэкономить одну-две команд процессора в теле цикла записав цикл в виде
for(i=L; --i!=0; )
но тут и порядок обхода получается другой, и менее привычно человеку, и на хоть сколько-то сложных внутренностях цикла пара команд роли не играет, а совсем простые циклы (всего из нескольких команд процессора) лучше вообще разворачивать (хотя бы частично), но обычно это умеет и оптимизатор. Так что смысла извращаться всё равно нет.
Написание высокоскоростного кода, или под хитрые архитектуры (с плохими оптимизаторами) - вопрос отдельный, часто контринтуитивный и гораздо шире столь примитивных вариантов. И нередко решается лишь опытным прогоном и замером времени в реальных условиях.

MGM в сообщении #1617897 писал(а):
Тот же вопарос по поводу long вместо int . Что-то архитектурное или просто стиль?
На некоторых архитектурах int может быть меньшей длины чем long и его диапазона может не хватить для задачи (например 16-битные всего лишь -32768..32767, может быть мало, а бывает и 2млрд мало). Так что это типа намёк что число нужно побольше. С другой стороны вроде бы не гарантируется что long длиннее int (только что не короче), так это не требование, а лишь намёк, и скорее не компилятору, а человеку. Если нужна уверенность, то есть другие типы, или с объявленным размером (типа uint32_t) или с объявленным смыслом (например чтобы влезал указатель, intptr_t). Подробнее о типах данных в C++ лучше смотреть сразу в стандарте. Вопрос различий обсуждался например здесь.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение16.11.2023, 18:06 
Экс-модератор
Аватара пользователя


23/12/05
12064
Dmitriy40 в сообщении #1617912 писал(а):
Скорее стиль. Это могло бы экономиться в компиляторах без оптимизатора (префиксная операция чуть проще в реализации), но вряд ли Вы с такими столкнётесь. Но ради большей совместимости могут и возвести в ранг стиля, мол "а вдруг".

Я, например, именно так и делаю: знаю, что с точки зрения производительности разницы не будет, но пишу ++j. Еще из негласных правил для себя, например: 1) Всегда ставлю {}, даже если всего одна команда (чтобы случайно при каком-нибудь переносе или добавлении других команд) не попортить; 2) в условиях сравнения на равенство с константой пишу if (1 == t) (потому что при случайной потере одного знака равенства и обратном порядке скомпилируется и будет работать, но неправильно); 3) const пишу после типа: int const a = 0; (в данном случае разницы нет, но при объявлении указателей тогда сохраняется единообразие чтения справа налево int const * - указатель на константные данные, int const * const - константный указатель на константные данные)

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение16.11.2023, 19:08 
Заслуженный участник


20/08/14
11776
Россия, Москва

(Бла-бла-бла, не для ТС)

MGM, Вам это пока не нужно, photon всё правильно сказал про хороший стиль написания кода, именно такой и рекомендуют.

photon в сообщении #1618218 писал(а):
Dmitriy40 в сообщении #1617912 писал(а):
Скорее стиль. Это могло бы экономиться в компиляторах без оптимизатора (префиксная операция чуть проще в реализации), но вряд ли Вы с такими столкнётесь. Но ради большей совместимости могут и возвести в ранг стиля, мол "а вдруг".

Я, например, именно так и делаю: знаю, что с точки зрения производительности разницы не будет, но пишу ++j.

Ну, вообще говоря зависит от. От архитектуры, компилятора, окружения этой команды.
Вот например попробуйте для AVR написать прединкремент и постинкремент числа итераций в uint32 (такие в регистрах не хранятся) и сравнение с константой, да ещё с неоптимизирующим компилятором ... Знаете что будет? Прединкремент загрузит число в регистры (4 команды по 3 такта), увеличит его на 1 (4 команды по 1 такту), выгрузит число обратно в память (4 команды по 3 такта), вычтет константу из числа в регистрах (4 команды по такту). Постинремент же загрузит число в регистры (4 команды по 3 такта), выгрузит во временную память (4 команды по 3 такта), увеличит число в регистрах на 1 (4 команды по 1 такту), выгрузит число обратно в память (4 команды по 3 такта), загрузит число из временной памяти (4 команды по 3 такта), вычтет константу из числа в регистрах (4 команды по 1 такту). Разница в двух операциях выгрузки числа во временную память и загрузки его обратно. Но каждая операция занимает 12 тактов! Т.е. 24 лишних такта. Или 32 такта против 56 тактов. Более чем в полтора раза. Проблема разумеется в страшно медленных командах обращения в памяти, аж по 3 такта. Но уж что есть. А сохранить значение до инкремента в других регистрах (или обратно уменьшить на 1 вместо сохранения во временной памяти) плохо оптимизирующий компилятор просто не умеет.
Разумеется это с одной стороны искусственный пример, мало кто сталкивается с этим при написании кода (т.е. мало кто пишет код держа в уме возможность его применения на AVR), с другой вполне жизненный потому что (некоторые) известные компиляторы именно так себя и ведут и можно поиметь тормоза на пустом месте.
А ещё бывают безрегистровые архитектуры (один-два аккумулятора не считаем), типа PIC или STM8, в них вообще вся работа только с памятью, часто даже для однобайтовых переменных. И не везде память быстрая (за такт). И не везде результат команды сразу попадает в память (как в PIC), бывает надо его туда отправлять отдельной командой и получится почти как в AVR.
Так что в общем случае далеко не всегда производительность одинакова.
А то привыкли все к компам с хорошо оптимизирующими компиляторами и огромными кэшами и суперскалярностью с отдельными портами загрузки/выгрузки, понапишут библиотек абы как, а потом пытаешься их использовать не на компе - и получаешь страх и ужас, особенно если посмотришь в бинарный код после компилятора ... Я вообще зарёкся туда смотреть пока программы не слишком тормозят - моментально возникает желание переписать вообще весь этот кошмар на асме (что разумеется глупость, но иногда таки приходится, хотя бы частично, особенно обработчики прерываний).

Другое дело что все эти тонкости всплывают обычно уже в около-профессиональной деятельности, когда приходится максимально ужиматься по ресурсам контроллера (цене, току потребления, размеру кода и используемого ОЗУ, ...), при работе же только с компами (ну и мобильниками теперь уж) и с обычными приложениями (где не надо выжимать каждый десяток процентов скорости) на любую разницу такого порядка можно смело плевать.

Но вообще Вы делаете всё правильно, совершенно Вам не возражаю, именно такой стиль и рекомендуют уже относительно давно. Не из-за производительности, а ради уменьшения ошибок человека.

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение16.11.2023, 19:21 
Заслуженный участник
Аватара пользователя


01/09/13
4656
MGM в сообщении #1617897 писал(а):
То есть плюсы слева. Может что-то экономится? Или просто такой стиль?

В общем случае, переменная цикла может быть "большим" объектом с перегруженными операциями.... Даже если они "согласовано перегружены", постфиксный оператор, скорее всего, потребует выделения памяти под текущее состояние объекта (а это накладно).

 Профиль  
                  
 
 Re: Что быстреее при реализации С++ кода k&pw[i] или k&(1<<i)
Сообщение16.11.2023, 19:39 
Экс-модератор
Аватара пользователя


23/12/05
12064

(Оффтоп)

Dmitriy40 в сообщении #1618252 писал(а):
Вот например попробуйте для AVR написать прединкремент и постинкремент числа итераций в uint32 (такие в регистрах не хранятся) и сравнение с константой, да ещё с неоптимизирующим компилятором
Я о себе - это не мой случай.

Dmitriy40 в сообщении #1618252 писал(а):
Другое дело что все эти тонкости всплывают обычно уже в около-профессиональной деятельности, когда приходится максимально ужиматься по ресурсам контроллера (цене, току потребления, размеру кода и используемого ОЗУ, ...), при работе же только с компами (ну и мобильниками теперь уж) и с обычными приложениями (где не надо выжимать каждый десяток процентов скорости) на любую разницу такого порядка можно смело плевать.
Если вы думаете, что десяток процентов скорости или энергопотребления для мобильников никого не интересует, то сильно ошибаетесь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

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



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

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


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

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