Теоретически, сравнение между 0 и 255 быстрее, чем 0 и 1?

Question

С точки зрения программирования с очень низким уровнем, как выполняется сравнение между двумя числами?

Используя один байт, без знака числа 0, 1 и 255 записываются:

0 -----> 00000000 
1 -----> 00000001 
255 ---> 11111111 

Теперь, что происходит во время сравнения между этими числами?

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

b = 0 
while b < 8: 
    if first_number[b] != second_number[b]: 
     return False 
    b += 1 
return True 

В основном это походит на сравнение каждого бита, шаг за шагом, и остановить до конца, если два бит разные.

Таким образом, мы отмечаем, что сравнение останавливается на первой итерации по сравнению с 0 и 255, в то время как оно останавливается на последнем, если сравнивать 0 и 1.

Первое сравнение было бы в 8 раз быстрее второго.

На практике я сомневаюсь, что это так. Но теоретически это верно? Если нет, то как работает компьютер?

Answer 1

Аппаратное обеспечение принципиально отличается от доминирующих парадигм программирования тем, что все логические ворота (или схемы вообще) всегда выполняют свою работу независимо, параллельно, во все времена. Нет такой вещи, как «сделайте это, тогда сделайте это», только «сделайте это здесь, подайте результат в схему». Если на чипе есть схема с входами A и выходом B, то цепь всегда, непрерывно, обновляет B в соответствии с текущими значениями A —, независимо от того, нужен ли результат прямо сейчас «на большом снимке».

Ваш алгоритм псевдокода даже не начинает хорошо отображаться на логические ворота. Вместо этого, компаратор выглядит в Verilog (не обращая внимания, что есть встроенный == оператора):

assign not_equal = (a[0]^b[0]) | (a[1]^b[1]) | ...; 

Где каждый XOR представляет собой отдельный логический элемент и, следовательно, работает независимо от других. Результаты «уменьшаются» логическим или, то есть выходом 1, если любой из XOR создает 1 (это также делает некоторые работы параллельно, но критический путь длиннее одного затвора).Кроме того, все эти ворота существуют в кремнии независимо от конкретных значений бит, и сигнал должен распространяться через около (1 + log w) затворы для w-разрядного целого числа. Эта задержка распространения снова не зависит от промежуточных и конечных результатов.

В некоторых семействах процессоров сравнение равенства реализуется путем вычитания двух чисел и сравнения результата с нулем (с использованием схемы, как описано выше), но применяется тот же принцип. Сумматор/вычитатель не становится медленнее или быстрее в зависимости от значений.

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

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

Цепи государственных машин представляют собой схемы с памятью: они сохраняют свое текущее состояние и всегда вычисляют выходы (в зависимости от текущего состояния) и следующее состояние (в зависимости от текущего состояния и входов) каждого тактового цикла. На некоторых входах они могут проходить через N состояний до тех пор, пока они не выдадут выходной сигнал, и N + x на других входах. Однако операции ALU вообще не делают этого. Трубопроводные ларьки, неверные предсказания филиалов и пропуски кеша являются общими причинами, по которым в некоторых случаях одна инструкция занимает больше времени, чем обычно. Правильно рассуждать об этом так, чтобы помочь программистам быстрее писать код сложно: вы должны учесть все хитрости и причуды реального оборудования, и их очень много. Жизненно важны эмпирические данные, то есть сравнительный анализ реального процессора черного ящика.

Answer 2

Когда он переходит к сборке, команда cmp используется независимо от содержимого переменных.

Таким образом, нет разницы в производительности.

Answer 3

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

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

Итак, ответ: нет, каждое сравнение занимает почти одно и то же время для каждого возможного ввода.