Сравнение 1 <10 дешевле, чем 1 <1000000?

65

Я просто использовал ~ 1 миллиард в качестве счетчика для a z-indexв CSS, и думал о сравнениях, которые должны продолжаться. Есть ли разница в производительности на уровне ALU при сравнении очень больших чисел с очень маленькими?

Например, будет ли один из этих двух фрагментов более дорогим, чем другой?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}
Viziionary
источник
9
знаете ли вы о том, как работает предсказание ветвлений ?
комнат
12
ОП не спрашивает, сколько времени займет ветвление. Ясно, что этот пример предназначен для того, чтобы гарантировать, что он занимает одинаковое время в обоих фрагментах. Вопрос в том, будет ли отдельная CMPмашинная инструкция медленнее, если iона больше.
Килиан Фот
18
Поскольку это делается в CSS, преобразование строки в целое число, вероятно, будет доминировать в самой операции сравнения с точки зрения времени, затрачиваемого на выполнение.
58
Если вам нужно было использовать 1000000000 в качестве z-индекса в файле CSS, вы сделали что-то не так.
Берги
6
Для CSS накладные расходы на преобразование текста в целое число будут зависеть от количества преобразуемых цифр (где 6-значное число, например, 1000000, может быть примерно в 6 раз дороже, чем 1-значное число, например, 1); и эти издержки могут быть на порядки больше, чем издержки целочисленных сравнений.
Брендан

Ответы:

82

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

Лучший способ наверняка ответить на вопрос - это скомпилировать ваш код в сборку и ознакомиться с документацией целевого процессора для получения сгенерированных инструкций. Для текущих процессоров Intel это будет Руководство разработчика программного обеспечения для архитектуры Intel 64 и IA-32 .

Описание инструкции CMP(«сравнить») приведено в томе 2А на стр. 3-126 или на стр. 618 документа PDF и описывает ее работу следующим образом:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

Это означает, что второй операнд при необходимости расширяется до знака, вычитается из первого операнда и результат помещается во временную область в процессоре. Затем флаги состояния устанавливаются так же, как и для SUBинструкции («вычитать») (стр. 1492 в PDF).

В документации CMPили SUBдокументации нет упоминания о том, что значения операндов имеют какое-либо отношение к задержке, поэтому любое значение, которое вы используете, является безопасным.

Blrfl
источник
5
Что если число становится слишком большим для 32-битной арифметики? Разве это не будет разделено на более медленные вычисления?
Falco
3
@Falco Не на процессоре с 64-битным ALU (который в настоящее время является почти всем из них, за исключением встроенного пространства)
reirab
8
@Falco: Да, но поскольку вопрос касается производительности ALU, это означает, что значения соответствуют размеру слова ЦП или возможностям любых SIMD-инструкций, которые он может иметь. Работа с большими числами, чем это, должна быть реализована с помощью нескольких инструкций вне процессора. Это было очень распространено 30 лет назад, когда у вас были только 8- или 16-битные регистры для работы.
Blrfl
6
@Falco Как это потребует отладки? Это не ошибка; просто немного медленнее делать 64-битные операции на процессоре, который изначально не поддерживает 64-битные операции. Утверждение, что никогда не следует использовать число выше 2 ^ 31-1, кажется немного нелепым.
Рейраб
2
@Falco Сказав это, механизмы рендеринга в браузерах даже используют целые числа для представления z-индексов? Большинство механизмов рендеринга, с которыми я знаком, используют плавающие с одинарной точностью для всего (до финальной стадии растеризации), но я на самом деле не изучал движки рендеринга в браузерах.
Рейраб
25

Есть ли разница в производительности на уровне ALU при сравнении очень больших чисел с очень маленькими?

Это очень маловероятно, если переход от маленького числа к большому не изменит ваш числовой тип, скажем, с a intна a long. Даже в этом случае разница может быть незначительной. Вы, скорее всего, увидите разницу, если ваш язык программирования тихо переключается на арифметику произвольной точности под прикрытием.

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

Роберт Харви
источник
Следует отметить, что предлагаемые числа в вопросе имеют разные числовые типы в типичном 32-битном целочисленном типе ...
Falco
19

Многие процессоры имеют «маленькие» инструкции, которые могут выполнять арифметические операции, в том числе сравнения, с некоторыми непосредственно указанными операндами. Операнды, отличные от этих специальных значений, должны либо использовать больший формат инструкции, либо, в некоторых случаях, должны использовать инструкцию «загрузить значение из памяти». Например, в наборе команд ARM Cortex-M3 есть как минимум пять способов сравнить значение с константой:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

Первая форма самая маленькая; вторая и третья формы могут выполняться или не выполняться так быстро, в зависимости от скорости памяти, из которой извлекается код. Четвертая форма формы почти наверняка будет медленнее, чем первые три, а пятая форма еще медленнее, но последняя может использоваться с любым 32-разрядным значением.

На старых процессорах x86 короткие инструкции сравнения будут выполняться быстрее, чем длинные, но многие новые процессоры преобразуют длинные и короткие формы в одно и то же представление при первом извлечении и сохраняют это унифицированное представление в кеше. Таким образом, хотя встроенные контроллеры (подобные тем, что установлены на многих мобильных платформах) будут иметь разницу в скорости, многие компьютеры на базе x86 не будут.

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

Supercat
источник
В MIPS вы можете иметь только 16-битные непосредственные значения, поэтому, безусловно, сравнение с 1 будет короче и (возможно) быстрее, чем 1000000. Возможно, то же самое для Sparc и PowerPC. И я думаю, что я читал из некоторых источников, что Intel также оптимизирует операции с небольшими мгновенными сообщениями в нескольких случаях, но я не уверен для сравнения или нет
phuclv
@ LưuVĩnhPhúc: регистр может быть загружен до цикла. В этот момент фактическое сравнение будет одинаковым количеством инструкций в любом случае.
Чао
Поскольку цикл был просто примером для операции, и вопрос был, например, z-index, если у вас есть 1000 объектов, каждый со своим собственным z-index, и вы устанавливаете их на 100000000 ... 1000000999 или на 10000 ... 10999 и вы перебираете их для сортировки перед рендерингом, есть много сравнений и много инструкций загрузки. Там это может иметь значение!
Falco
@ Фалько: В этом случае, немедленные не будут даже учитывать; загрузка и сравнение с регистром кажется почти неизбежным.
Чао
@cHao: Если сравнивать Z индексы друг с другом, они будут в регистрах. Если кто-то обрабатывает определенные диапазоны индексов по-разному, это может повлечь за собой немедленное сравнение. Обычно константы загружаются до начала цикла, но если, например, у одного есть цикл, который должен считывать пары значений из памяти и сравнивать первое значение каждой пары с пятью разными (неравномерно разнесенными) константами в диапазоне 100000 до 100499, и другое значение с пятью другими такими константами, может быть намного быстрее вычесть 100250 (хранится в регистре), а затем сравнить со значениями от -250 до 250 ...
суперкат
5

Короткий ответ на этот вопрос: нет , нет никакой разницы во времени для сравнения двух чисел на основе величины этих чисел, если предположить, что они хранятся в одном и том же типе данных (например, оба 32-разрядных целых или оба 64-разрядных длинных).

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

Единственные случаи, о которых я могу вспомнить, с которыми я столкнулся, когда сравнение двух чисел не было операцией с одним циклом, следующие:

  • Инструкции, где на самом деле существует задержка памяти при извлечении операндов, но это не имеет никакого отношения к тому, как работает само сравнение (и, как правило, невозможно в архитектурах RISC, хотя обычно это возможно в конструкциях CISC, таких как x86 / x64.)
  • Сравнения с плавающей точкой могут быть многоцикловыми, в зависимости от архитектуры.
  • Указанные числа не соответствуют размеру слова в АЛУ, и, следовательно, сравнение должно быть разбито на несколько инструкций.
reirab
источник
4

@ RobertHarvey ответ хороший; Считайте этот ответ дополнением к своему.


Вы должны также рассмотреть предсказание ветвления :

В компьютерной архитектуре предиктор ветвления - это цифровая схема, которая пытается угадать, каким образом пойдет ветвь (например, структура if-then-else), прежде чем это станет известно наверняка. Целью предиктора ветвления является улучшение потока в конвейере команд. Предсказатели ветвлений играют решающую роль в достижении высокой эффективной производительности во многих современных конвейерных микропроцессорных архитектурах, таких как x86.

По сути, в вашем примере, если ifоператор внутри цикла всегда возвращает один и тот же ответ, тогда система может оптимизировать его, правильно угадав, в какую сторону он будет переходить. В вашем примере, поскольку ifоператор в первом случае всегда возвращает один и тот же результат, он будет выполняться немного быстрее, чем во втором случае.

Отличный вопрос переполнения стека

durron597
источник
Прогнозирование ветвления влияет на время ветвления, но не на само время сравнения.
Рейраб
3

Это зависит от реализации, но это будет очень, очень маловероятно .

Я признаю, что я не читал подробности реализации различных движков браузера, и CSS не определяет какой-либо конкретный тип хранения для чисел. Но я считаю, что можно с уверенностью предположить, что все основные браузеры используют 64-битные числа с плавающей запятой двойной точности («doubles», чтобы позаимствовать термин из C / C ++) для удовлетворения большинства своих числовых потребностей в CSS потому что это то, что JavaScript использует для чисел, и поэтому использование одного и того же типа облегчает интеграцию.

С точки зрения компьютера, все двойники несут одинаковое количество данных: 64 бита, независимо от того, равно ли это значение 1 или -3,14 или 1000000 или 1e100 . Время, необходимое для выполнения операции над этими числами, не зависит от фактического значения этих чисел, потому что оно всегда работает с одним и тем же объемом данных. Таким способом можно найти компромисс: двойные числа не могут точно представлять все числа (или даже все числа в пределах их диапазона), но они могут быть достаточно близки для большинства вопросов, а виды вещей, которые CSS делает не численно достаточно требовательна, чтобы нуждаться в большей точности. Объедините это с преимуществами прямой совместимости с JavaScript, и вы получите достаточно веские аргументы в пользу двойных чисел.

Не исключено, что кто-то может реализовать CSS с использованием кодирования переменной длины для чисел. Если бы кто-то использовал кодирование переменной длины, то сравнение с небольшими числами было бы дешевле, чем сравнение с большими числами, потому что большие числа имеют больше данных для обработки . Эти виды кодирования могут быть более точными, чем двоичные, но они также намного медленнее, и, в частности, для CSS, прироста точности, вероятно, недостаточно, чтобы стоить потери производительности. Я был бы очень удивлен, узнав, что любой браузер так поступает.

Теперь, теоретически, есть одно возможное исключение из всего, что я сказал выше: сравнение с нулем часто происходит быстрее, чем сравнение с другими числами . Это не потому, что ноль является коротким (если это было причиной, то 1 должен быть таким же быстрым, но это не так). Это потому, что ноль позволяет вам обманывать. Это единственное число, где все биты выключены, поэтому, если вы знаете, что одно из значений равно нулю, вам даже не нужно рассматривать другое значение как число: если какой-либо из битов включен, то он не равен ноль, и тогда вам нужно только взглянуть на один бит, чтобы увидеть, больше или меньше нуля.

Ложка
источник
0

Если бы этот код интерпретировался каждый раз, когда он выполнялся, было бы различие, поскольку для токенизации и интерпретации требуется больше времени по 10000000000000сравнению с 1000. Тем не менее, это очевидная первая оптимизация интерпретаторов в этом случае: токенизировать один раз и интерпретировать токены.

Марк Херд
источник