Сравнение букв медленнее, чем сравнение цифр?

Question

Оставайтесь здесь со мной.

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

// 32 bit integers.
Input:  9 4

4: 00000000 00000000 00000000 00000110
9: 00000000 00000000 00000000 00001001
// Etc.

и начинаем сравнение справа налево.

// First step.
4: 0
9: 1

Output: 9 4

// Second step
4: 1
9: 0

Output: 4 9 // Technically a stable algorithm, but we cannot observe that here.

// Third step

4: 1
9: 0

Output: 4 9

// Fourth step

4: 0
9: 1

Output: 9 4

И это все;остальные 28 итераций - все нули, поэтому вывод больше не изменится.Теперь, сравнение всей цепочки строк, как это будет идти

// strings
Input: "Christian" "Denis"

Christian: C h r i s t i a n
Denis:     D e n i s

// First step.
Christian: n
Denis:     s

Output: Christian, Denis

// Second step
Christian: a
Denis:     i

Output: Denis, Christian

// ... 

и т. Д.

Мой вопрос заключается в том, является ли сравнение знакового символа, байтового числа, быстрее, чем сравнение целых чисел?

Если предположить, 1-байтовый символ сравнивается быстрее, чем 4-байтовое целое.Это правильно?Могу ли я сделать то же предположение с форматами wchar_t или UTF-16/32?

Answer 1

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

Как правило, int - это наиболее "удобный" размер для процессора, поэтому сравнение обычнобудь быстрымВсе, что больше, может быть медленнее, поскольку может потребоваться разбить его на несколько int с.Все, что меньше , может быть таким же быстрым, как int, но в зависимости от архитектуры памяти неправильное выравнивание может занять больше времени.

Помимо всего этого, есть памятькоэффициент пропускной способности.Чем больше тип, тем выше требуемая пропускная способность.И еще есть кеширующие эффекты.Если узким местом является скорость процессора, то это не имеет значения.В противном случае это так.

Answer 2

В C или C ++ char - это просто однобайтовое целое число (хотя «один байт» может быть или не быть 8 битами). Это означает, что в типичном случае единственное различие, с которым вам приходится иметь дело, заключается в том, является ли однобайтовое сравнение более быстрым, чем многобайтовое сравнение.

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

Даже на чем-то вроде x86, который напрямую поддерживает однобайтовые операции, они все еще часто работают медленнее (на современном процессоре). Есть несколько вещей, которые способствуют этому. Прежде всего, инструкции, использующие регистры размера «естественного» для текущего режима, имеют более простое кодирование, чем инструкции, использующие другие размеры. Во-вторых, у значительного числа процессоров x86 есть так называемая «частичная остановка регистра» - хотя это все неявно, внутренне они делают что-то вроде RISC, выполняя операцию над полноразмерным регистром, а затем объединяют ее с другие байты исходного значения. Например, если вы выводите результат в AL, а затем ссылаетесь на EAX, выполнение последовательности займет больше времени, чем если бы вы произвели результат в EAX для начала.

OTOH, если вы посмотрите на достаточно старые процессоры, обратное может быть (и часто) верно. В качестве экстремального примера рассмотрим Intel 8080 или Zilog Z80. Оба имели некоторые 16-битные инструкции, но пути через ALU имели ширину всего 8 бит - например, 16-битное сложение фактически выполнялось как два последовательных 8-битных сложения. Если бы вы могли обойтись только с 8-битной операцией, это было бы примерно в два раза быстрее. Хотя 8-разрядные процессоры являются (удаленной) памятью на настольных компьютерах, они все еще используются в некоторых встроенных приложениях, поэтому это также не является устаревшим.

Answer 3

Однобайтовые символы сравниваются как числа в C ++. Точная скорость зависит от платформы процессора хоста и обычно равна скорости сравнения 4-байтовых целых чисел.

Answer 4

У меня такой вопрос, сравнивать ли цифру со знаком и число байтов быстрее, чем сравнивать целые числа?

Нет.В C ++ эти операции, безусловно, будут идентичны по скорости.Современные процессоры в любом случае выполняют большинство операций с байтами в количестве 4 ¹ , поэтому 1 байт против 4 байтов не будет сокращать время вычислений.

Пожалуйста, примите, что преобразование в двоичныйс целочисленным примером не имеет значения

Не происходит никакого преобразования.Числа в любом случае представлены в ПК как двоичные.

---

¹ Грубое упрощение.Но ради аргумента мы можем утверждать, что int в C ++ всегда будет «родной» единицей измерения для данного CPU.

Answer 5

Ответ - «выравнивание». Сравнение символов, которые не выровнены по естественной границе слова, всегда будет медленнее, чем сравнение выровненных данных. Помимо этого, процессор выполняет несколько операций за цикл в конвейере, и многие другие условия влияют на производительность.

Answer 6

Как сказал Аль Кепп, это зависит от вашей платформы.Однако в большинстве процессоров есть встроенная инструкция для сравнения Words , которая, поскольку она является инструкцией CPU, всегда занимает одно и то же время, если сравниваемые данные помещаются в одно слово.*

CMP x86 Assembly

Answer 7

Если предположить, 1-байтовый символ сравнивается быстрее, чем 4-байтовое целое. Это правильно?

Я очень сильно сомневаюсь в этом. Если бы я, где угадать, моя ставка была бы наоборот, если один из них медленнее, чем другой. Причина? Большинство современных процессоров предназначены для работы непосредственно с 4-байтовыми типами.

Могу ли я сделать то же предположение с форматами wchar_t или UTF-16/32?

Нет. Форматы UTF намного сложнее и не могут сравниваться напрямую, байтов за байтом, если вы строго не проверяете на равенство.

Вы действительно не должны беспокоиться о такой проблеме скорости. Если ваш инструктор учит вас беспокоиться о скорости сравнения 1-байтового типа с 4-байтовым типом, то вам действительно нужно принимать все, что они говорят, с МНОГО соли. Пишите эффективные алгоритмы, не пытайтесь оптимизировать на этом уровне детализации.