Производительность без знака против целых чисел со знаком
Есть ли какой-либо выигрыш / потеря производительности при использовании целых чисел без знака по сравнению со знаковыми
Если это так, то будет ли это продолжаться коротко и долго?
12 ответов
Деление на степени 2 быстрее с unsigned intпотому что это может быть оптимизировано в одну инструкцию смены. С signed intобычно требуется больше машинных инструкций, потому что деление округляет до нуля, но смещение вправо округляет вниз. Пример:
int foo(int x, unsigned y)
{
x /= 8;
y /= 8;
return x + y;
}
Вот соответствующий x часть (подписанное деление):
movl 8(%ebp), %eax
leal 7(%eax), %edx
testl %eax, %eax
cmovs %edx, %eax
sarl $3, %eax
А вот соответствующий y часть (без знака деления):
movl 12(%ebp), %edx
shrl $3, %edx
В C++ (и C) целочисленное переполнение со знаком не определено, а целочисленное переполнение без знака определено для обхода. Обратите внимание, что, например, в gcc, вы можете использовать флаг -fwrapv, чтобы определить переполнение со знаком (чтобы обернуть его).
Неопределенное целочисленное переполнение со знаком позволяет компилятору предполагать, что переполнения не происходит, что может привести к возможностям оптимизации. Смотрите, например, этот блог для обсуждения.
unsigned приводит к такой же или лучшей производительности, чем signed, Некоторые примеры:
- Деление на константу, которая является степенью 2 (см. Также ответ от FredOverflow)
- Деление на постоянное число (например, мой компилятор реализует деление на 13, используя 2 инструкции asm для unsigned и 6 инструкций для sign)
- Проверка, является ли число четным (я понятия не имею, почему мой компилятор MS Visual Studio реализует его с 4 инструкциями для
signedчисла; GCC делает это с 1 инструкцией, как вunsignedдело)
short обычно приводит к такой же или худшей производительности, чем int (при условии, sizeof(short) < sizeof(int)). Понижение производительности происходит, когда вы назначаете результат арифметической операции (которая обычно int, никогда short) к переменной типа short, который хранится в регистре процессора (который также имеет тип int). Все преобразования из short в int занимают время и раздражают.
Примечание: некоторые DSP имеют быстрые инструкции умножения для signed short тип; в этом конкретном случае short быстрее чем int,
Что касается разницы между int а также longЯ могу только догадываться (я не знаком с 64-битными архитектурами). Конечно, если int а также long имеют одинаковый размер (на 32-битных платформах), их производительность также одинакова.
Очень важное дополнение, на которое указывают несколько человек:
Что действительно важно для большинства приложений, так это объем памяти и используемая пропускная способность. Вы должны использовать наименьшие необходимые целые числа (short, может быть даже signed/unsigned char) для больших массивов.
Это даст лучшую производительность, но выигрыш будет нелинейным (т.е. не в 2 или 4 раза) и несколько непредсказуемым - это зависит от размера кэша и взаимосвязи между вычислениями и передачей памяти в вашем приложении.
Это будет зависеть от точной реализации. Однако в большинстве случаев не будет никакой разницы. Если вам действительно все равно, вы должны попробовать все варианты, которые вы рассматриваете, и измерить производительность.
Это в значительной степени зависит от конкретного процессора.
На большинстве процессоров есть инструкции для арифметики со знаком и без знака, поэтому разница между использованием целых чисел со знаком и без знака сводится к тому, какой компилятор использует.
Если какой-либо из них быстрее, он полностью зависит от процессора, и, скорее всего, разница будет незначительной, если она вообще существует.
Разница в производительности между целыми числами со знаком и без знака на самом деле более общая, чем предполагает ответ о принятии. Деление целого без знака на любую константу может быть выполнено быстрее, чем деление целого числа без знака на константу, независимо от того, является ли константа степенью двойки. См. http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html
В конце своего поста он включает следующий раздел:
Естественный вопрос заключается в том, может ли та же оптимизация улучшить подписанное деление; к сожалению, похоже, что это не так по двум причинам:
Прирост дивиденда должен стать увеличением величины, то есть приращением, если n > 0, уменьшением, если n < 0. Это влечет за собой дополнительные расходы.
Штраф за неработающий делитель в подписанном делении составляет лишь половину от этого, оставляя меньшее окно для улучшений.
Таким образом, представляется, что алгоритм округления может быть выполнен для работы в знаковом делении, но будет хуже, чем стандартный алгоритм округления.
Не только деление на степени 2 быстрее с типом без знака, деление на любые другие значения также быстрее с типом без знака. Если вы посмотрите таблицы инструкций Agner Fog, то увидите, что неподписанные подразделения имеют такую же или лучшую производительность, чем подписанные версии.
Например с AMD K7
╔═════════════╤══════════╤═════╤═════════╤═══════════════════════╗
║ Instruction │ Operands │ Ops │ Latency │ Reciprocal throughput ║
╠═════════════╪══════════╪═════╪═════════╪═══════════════════════╣
║ DIV │ r8/m8 │ 32 │ 24 │ 23 ║
║ DIV │ r16/m16 │ 47 │ 24 │ 23 ║
║ DIV │ r32/m32 │ 79 │ 40 │ 40 ║
║ IDIV │ r8 │ 41 │ 17 │ 17 ║
║ IDIV │ r16 │ 56 │ 25 │ 25 ║
║ IDIV │ r32 │ 88 │ 41 │ 41 ║
║ IDIV │ m8 │ 42 │ 17 │ 17 ║
║ IDIV │ m16 │ 57 │ 25 │ 25 ║
║ IDIV │ m32 │ 89 │ 41 │ 41 ║
╚═════════════╧══════════╧═════╧═════════╧═══════════════════════╝
То же самое относится к Intel Pentium
╔═════════════╤══════════╤══════════════╗
║ Instruction │ Operands │ Clock cycles ║
╠═════════════╪══════════╪══════════════╣
║ DIV │ r8/m8 │ 17 ║
║ DIV │ r16/m16 │ 25 ║
║ DIV │ r32/m32 │ 41 ║
║ IDIV │ r8/m8 │ 22 ║
║ IDIV │ r16/m16 │ 30 ║
║ IDIV │ r32/m32 │ 46 ║
╚═════════════╧══════════╧══════════════╝
Конечно, они довольно древние. Более новые архитектуры с большим количеством транзисторов могут сократить разрыв, но применимы основные вещи: как правило, вам нужно больше макроопераций, больше логики, больше задержек для деления со знаком.
Короче, не беспокойтесь перед фактом. Но потрудитесь после.
Если вы хотите иметь производительность, вы должны использовать оптимизацию производительности компилятора, которая может работать против здравого смысла. Следует помнить, что разные компиляторы могут компилировать код по-разному, и они сами имеют разные виды оптимизации. Если мы говорим о g++ компилятор и говорить о повышении его уровня оптимизации с помощью -Ofast или хотя бы -O3 флаг, по моему опыту, он может скомпилировать long введите в код с еще лучшей производительностью, чем любой unsigned типа, или даже просто int,
Это из моего собственного опыта, и я рекомендую вам сначала написать свою полную программу и заботиться о таких вещах только после этого, когда у вас есть действительный код в ваших руках, и вы можете скомпилировать его с оптимизацией, чтобы попытаться выбрать типы, которые на самом деле выполняют Лучший. Это также хорошее общее предложение по оптимизации кода для повышения производительности, сначала быстро напишите, попробуйте скомпилировать с оптимизацией, настройте параметры, чтобы увидеть, что работает лучше всего. И вам также следует попробовать использовать разные компиляторы для компиляции вашей программы и выбрать тот, который выводит наиболее производительный машинный код.
Оптимизированная многопоточная программа вычисления линейной алгебры может легко иметь>10- кратную разницу в производительности, точно оптимизированную и неоптимизированную. Так что это имеет значение.
Вывод оптимизатора противоречит логике во многих случаях. Например, у меня был случай, когда разница между a[x]+=b а также a[x]=b изменил время выполнения программы почти в 2 раза. И нет, a[x]=b не был быстрее.
Вот, например, NVidia, заявляющая, что для программирования своих графических процессоров:
Примечание. Как уже было рекомендовано, рекомендуется использовать арифметику со знаком по сравнению с арифметикой без знака везде, где это возможно, для обеспечения максимальной пропускной способности SMM. Стандарт языка C накладывает больше ограничений на поведение переполнения для математики без знака, ограничивая возможности оптимизации компилятора.
IIRC, на x86 подписанный / неподписанный не должен иметь никакого значения. Короткая / длинная, с другой стороны, - это другая история, так как объем данных, которые необходимо переместить в / из ОЗУ, больше для длинных (другие причины могут включать в себя операции приведения типа, такие как расширение короткой на длинную).
По традиции int является собственным целочисленным форматом целевой аппаратной платформы. Любой другой целочисленный тип может повлечь за собой снижение производительности.
РЕДАКТИРОВАТЬ:
Вещи немного отличаются в современных системах:
intна самом деле может быть 32-битным в 64-битных системах из соображений совместимости. Я считаю, что это происходит в системах Windows.Современные компиляторы могут неявно использовать
intпри выполнении вычислений для более коротких типов в некоторых случаях.
Целые числа со знаком и без знака всегда будут работать как одночасовые инструкции и иметь одинаковую производительность чтения-записи, но, по словам доктора Андрея Александреску, без знака предпочтительнее, чем со знаком. Причина этого в том, что вы можете вписать вдвое большее количество чисел в одно и то же количество бит, потому что вы не тратите впустую знаковый бит и будете использовать меньше инструкций для проверки отрицательных чисел, что приведет к увеличению производительности из-за уменьшения ПЗУ. По моему опыту работы с виртуальной машиной Kabuki, в которой реализована сверхскоростная реализация сценариев, редко когда вам действительно требуется подписанный номер при работе с памятью. Я проводил майские годы, занимаясь арифметикой указателей со знаковыми и беззнаковыми числами, и я не нашел никакой пользы для подписанных, когда не требуется знаковый бит.
Где подпись может быть предпочтительнее, когда используется сдвиг битов для выполнения умножения и деления степеней 2, потому что вы можете выполнять отрицательные степени деления 2 с целыми числами дополнения со знаком 2. Пожалуйста, посмотрите еще несколько видео на YouTube от Андрея, чтобы узнать больше о методах оптимизации. В моей статье вы также можете найти полезную информацию о самом быстром в мире алгоритме преобразования целых чисел в строку.
Целое число без знака выгодно тем, что вы храните и обрабатываете оба потока как битовый поток, я имею в виду просто данные без знака, поэтому умножение, деление становится проще (быстрее) с операциями сдвига битов