Я хотел бы узнать о преимуществах этого.
Ответ 3
Вкратце:
- Оператор
>> в Java известен как оператор Extended Extended Shift.
-
X >> 1 математически эквивалентен X / 2, для всех строго положительных значений X.
-
X >> 1 всегда быстрее, чем X / 2, в соотношении примерно 1:16, хотя разница может оказаться гораздо менее значимой в реальных тестах из-за современной архитектуры процессора.
- Все основные JVM-устройства могут корректно выполнять такие оптимизации, но неоптимизированный байт-код будет выполняться в интерпретированном режиме тысячи раз до того, как эта оптимизация действительно произойдет.
- Исходный код JRE использует множество идиом оптимизации, поскольку они имеют важное значение для кода, выполняемого в интерпретируемом режиме (и, самое главное, при запуске JVM).
- Систематическое использование проверенных и эффективных кодовых оптимизационных идиом, которые принимаются всей командой разработчиков, не является преждевременной оптимизацией.
Длинный ответ
В следующем обсуждении попытайтесь правильно решить все вопросы и сомнения, которые были опубликованы в других комментариях на этой странице. Это так долго, потому что я чувствовал, что необходимо сделать акцент на том, почему какой-то подход лучше, вместо того, чтобы демонстрировать личные результаты тестов, убеждения и практику, когда размер может значительно варьироваться от одного человека к другому.
Так что давайте задавать вопросы по одному.
1. Что означает X >> 1 (или X << 1, или X >>> 1) в Java?
>>, << и >>> совместно называются операторами бит-сдвига. >> широко известен как смена знака расширенного правого бита или сдвиг арифметического правого бита. >>> - это расширенный сдвиг вправо без знака (также известный как логический сдвиг вправо), а << - это просто сдвиг влево (расширение знака не применяется в этом направлении, поэтому нет необходимости в логическом и арифметические варианты).
Операторы бит-сдвига доступны (хотя и с различной нотацией) на многих языках программирования (фактически, из краткого опроса, который я бы сказал, почти на всех языках, которые являются более или менее потомками языка C, плюс несколько других). Бит-сдвиги являются фундаментальными бинарными операциями, и, по сути, почти каждый процессор, когда-либо созданный, предлагает инструкции по сборке для них. Бит-сдвиги также являются классическим строительным блоком в электронном дизайне, который, учитывая разумное количество транзисторов, обеспечивает его конечный результат за один шаг с постоянным и предикативным периодом стабилизации.
Конкретно оператор смены битов преобразует число, перемещая все его биты на n позиций, как слева, так и справа. Биты, которые выпадают, забыты; биты, которые "входят", принудительно равны 0, за исключением случая сдвига вправо с правом знака, в котором самый левый бит сохраняет свое значение (и, следовательно, его знак). См. Wikipedia для иллюстрации этого.
2. Имеет ли X >> 1 значение X / 2?
Да, если дивиденд гарантированно будет положительным.
В более общем плане:
- сдвиг слева на
N эквивалентен умножению на 2N;
- логический сдвиг вправо на
N эквивалентен беззнаковому целочисленному делению на 2N;
- арифметический сдвиг вправо на
N эквивалентен нецелочисленному делению на 2N, округленному до целого к отрицательной бесконечности (что также эквивалентно значению целочисленного деления на 2N для любого строго положительного целого).
3. Является ли бит более быстрым, чем эквивалентная артехическая операция, на уровне CPU?
Да, это так.
Прежде всего, мы можем легко утверждать, что на уровне ЦП бит сдвиг требует меньше работы, чем эквивалентная арифметическая операция. Это справедливо как для умножений, так и для делений, и причина этого проста: как целые умножения, так и целые схемы деления содержат несколько бит-сдвигов. Положим иначе: блок сдвига бит представляет собой лишь часть уровня сложности единицы умножения или деления. Поэтому гарантируется, что требуется меньше энергии для выполнения простого битового сдвига, а не полной арифметической операции. Тем не менее, в конечном счете, если вы не контролируете потребление электрическим током или рассеивание тепла, я сомневаюсь, что вы могли заметить, что ваш процессор использует больше энергии.
Теперь давайте поговорим о скорости. На процессорах с разумно простой архитектурой (примерно, любой процессор, разработанный до Pentium или PowerPC, а также самые последние процессоры, не имеющие какой-либо формы конвейеров выполнения), в целом реализовано целочисленное деление (и умножение, в меньшей степени) путем итерации по битам (фактически группа бит, известная как radix) на одном из операндов. Каждая итерация требует одного цикла ЦП, а это означает, что целочисленное деление на 32-битном процессоре потребует (не более) 16 циклов (при условии, что блок разделения Radix 2 SRT на гипотетическом процессоре). Единицы умножения обычно обрабатывают больше бит одновременно, поэтому 32-разрядный процессор может завершить целочисленное умножение в 4-8 циклах. Эти единицы могут использовать переменную бит-сдвиг переменной формы для быстрого перехода по последовательности последовательных нулей и, следовательно, могут быстро прекратиться при умножении или делении на простые операнды (например, положительная мощность двух); в этом случае арифметическая операция будет завершена за меньшее количество циклов, но по-прежнему потребует больше, чем просто операция смены битов.
Очевидно, что синхронизация команд различается между проектами процессоров, но преходящее соотношение (бит сдвига = 1, умножение = 4, деление = 16) является разумным приближением фактической производительности этих инструкций. Для справки, на Intel 486, инструкции SHR, IMUL и IDIV (для 32 бит, считая регистр константой) требуются соответственно 2, 13-42 и 43 цикла (см. здесь для списка из 486 инструкций с указанием времени).
Как насчет процессоров, найденных на современных компьютерах? Эти процессоры разработаны вокруг архитектур трубопроводов, которые позволяют одновременно выполнять несколько инструкций; результат состоит в том, что большинство инструкций в настоящее время требуют только одного цикла выделенного времени. Но это вводит в заблуждение, поскольку инструкции фактически остаются в конвейере в течение нескольких циклов перед выпуском, в течение которых они могут препятствовать выполнению других инструкций. Целочисленное умножение или единица деления остается "зарезервированным" за это время, и поэтому любое дальнейшее деление будет сдерживаться. Это, в частности, проблема в коротких циклах, где одиночное различие или разделение в конечном итоге затормозится предыдущим вызовом самого себя, которое еще не завершено. Бит-сдвиговые инструкции не страдают от такого риска: большинство "сложных" процессоров имеют доступ к нескольким единицам сдвига бит, и им не нужно резервировать их очень долго (хотя обычно по меньшей мере 2 цикла по причинам, присущим архитектуре конвейера). Фактически, чтобы поместить это в число, быстрый взгляд на Справочное руководство по оптимизации Intel для Atom, похоже, указывает на то, что SHR, IMUL и IDIV (одинаковые как указано выше) соответственно имеют 2, 5 и 57 латентных циклов; для 64-битных операндов это 8, 14 и 197 циклов. Подобная латентность применяется к большинству современных процессоров Intel.
Итак, да, смещение битов происходит быстрее, чем эквивалентные арифметические операции, хотя в некоторых ситуациях на современных процессорах это может фактически не иметь никакого значения. Но в большинстве случаев это очень важно.
4. Будет ли виртуальная машина Java выполнять такую оптимизацию для меня?
Конечно, будет. Ну... конечно, и... в конце концов.
В отличие от большинства компиляторов языка, обычные компиляторы Java не выполняют никакой оптимизации. Считается, что виртуальная машина Java находится в лучшем положении, чтобы решить, как оптимизировать программу для конкретного контекста выполнения. И это действительно дает хорошие результаты на практике. Компилятор JIT очень глубоко понимает динамику кода и использует эти знания для выбора и применения тонны небольших преобразований кода, чтобы создать очень эффективный собственный код.
Но компиляция байтового кода в оптимизированные собственные методы требует много времени и памяти. Именно поэтому JVM даже не рассмотрит оптимизацию блока кода до того, как он будет выполнен тысячи раз. Затем, несмотря на то, что блок кода был запланирован для оптимизации, может потребоваться много времени, прежде чем поток процесса компилятора будет обрабатывать этот метод. И позже, различные условия могут привести к тому, что оптимизированный блок кода будет отброшен, возвращаясь к интерпретации байтового кода.
Хотя JSE API разработан с целью реализации различными поставщиками, неверно утверждать, что это также JRE. Oracle JRE предоставляется другим всем в качестве эталонной реализации, но его использование с другой JVM не рекомендуется (актуально, это было запрещено ранее, до того, как Oracle открыл исходный код JRE).
Оптимизации в исходном коде JRE являются результатом принятых конвенций и усилий по оптимизации среди разработчиков JRE для обеспечения разумных результатов даже в ситуациях, когда оптимизация JIT еще не помогает или просто не может помочь. Например, сотни классов загружаются до вызова основного метода. В начале, JIT-компилятор еще не приобрел достаточную информацию для правильной оптимизации кода. В это время ручная оптимизация имеет важное значение.
5. Разве это не преждевременная оптимизация?
Это, если нет причин, почему это не так.
Это факт современной жизни, когда всякий раз, когда программист демонстрирует оптимизацию кода где-то, другой программист будет противопоставлять цитату Дональда Кнута о оптимизации (ну, это было его? кто знает...) Это даже воспринимается многими как ясное утверждение Кнута о том, что мы никогда не должны пытаться оптимизировать код. К сожалению, это серьезное непонимание важного вклада Кнута в информатику за последние десятилетия: Кнут как фактически создал тысячи страниц грамотности на практической оптимизации кода.
Как сказал Кнут:
Программисты тратят огромное количество времени на размышления о скорости некритических частей своих программ или беспокоятся о скорости их некритических частей, и эти попытки эффективности действительно оказывают сильное негативное влияние при отладке и обслуживании. Мы должны забыть о небольшой эффективности, скажем, около 97% времени: преждевременная оптимизация - корень всего зла. Однако мы не должны упускать наши возможности в этих критических 3%. - Дональд Э. Кнут, "Структурированное программирование с заявлениями Goto"
То, что Knuth квалифицируется как преждевременная оптимизация, - это оптимизации, которые требуют много размышлений и применяются только к некритической части программы и оказывают сильное негативное влияние на отладку и обслуживание. Теперь все это можно обсуждать в течение долгого времени, но пусть нет.
Следует, однако, понимать, что небольшие локальные оптимизации, которые оказались эффективными (то есть, по крайней мере, в среднем, в целом), которые не оказывают отрицательного влияния на общую конструкцию программы, не уменьшают совместимость кода и не требуют постороннего мышления, это совсем не плохо. Такая оптимизация актуальна, поскольку они ничего не стоят, и мы не должны упускать такие возможности.
Тем не менее, и это самое важное, что нужно помнить, оптимизация, которая была бы тривиальной для программистов в одном контексте, может оказаться некомпетентной для программистов в другом контексте. По этой причине особенно проблематичны битовые сдвиговые и маскирующие идиомы. Программисты, которые знают идиому, могут ее прочитать и использовать, не задумываясь, и эффективность этих оптимизаций доказана, хотя и невелика, если только код не содержит сотни случаев. Эти идиомы редко являются реальным источником ошибок. Тем не менее, программисты, не владеющие определенной идиомой, теряют время, понимая, что, почему и как делает этот фрагмент кода.
В конце концов, чтобы поддержать такую оптимизацию или нет, и именно то, какие идиомы должны использоваться, действительно зависит от группового решения и контекста кода. Я лично считаю, что определенное количество идиом является лучшей практикой во всех ситуациях, и любой новый программист, присоединяющийся к моей команде, быстро приобретает их. Многие идиомы зарезервированы для критического кода. Весь код, помещенный во внутреннюю общую библиотеку кодов, рассматривается как критический путь кода, поскольку они могут оказаться вызванными из такого критического кода. Во всяком случае, это моя личная практика, и ваша медаль может меняться.
