производительность без знака против целых чисел со знаком

Question

Есть ли какой-либо выигрыш или потеря производительности при использовании целых чисел без знака по сравнению со целыми числами со знаком?

Если да, то это тоже относится к коротким и длинным?

Answer 1

Деление на степени 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

Answer 2

В C ++ (и C) переполнение целых чисел со знаком не определено, тогда как переполнение целых чисел без знака определено для переноса. Обратите внимание, что, например, в gcc вы можете использовать флаг -fwrapv, чтобы определить переполнение со знаком (чтобы обернуть его).

Неопределенное целочисленное переполнение со знаком позволяет компилятору предполагать, что переполнения не происходит, что может привести к возможностям оптимизации. Смотрите, например это сообщение в блоге для обсуждения.

Answer 3

Это будет зависеть от точной реализации.Однако в большинстве случаев не будет никакой разницы.Если вам действительно все равно, вы должны попробовать все варианты, которые вы рассматриваете, и измерить производительность.

Answer 4

unsigned приводит к такой же или лучшей производительности, чем signed.Некоторые примеры:

• Деление на константу, которая является степенью 2 (см. Также ответ от FredOverflow )
• Деление на константу (например,мой компилятор реализует деление на 13 с использованием 2 asm-инструкций для unsigned и 6 инструкций для unsigned)
• Проверка четности числа (я понятия не имею, почему мой компилятор 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 раза)и несколько непредсказуемо - это зависит от размера кэша и взаимосвязи между вычислениями и передачей памяти в вашем приложении.

Answer 5

Это в значительной степени зависит от конкретного процессора.

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

Если какой-либо из этих двух вариантов быстрее, он полностью зависит от процессора, и, скорее всего, разница будет незначительной, если она вообще существует.

Answer 6

Разница в производительности между целыми числами со знаком и без знака на самом деле более общая, чем предполагает ответ о принятии.Деление целого без знака на любую константу может быть выполнено быстрее, чем деление целого числа без знака на константу, независимо от того, является ли константа степенью двойки.См. http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html

. В конце своего поста он включает следующий раздел:

Естественный вопрос: может ли та же оптимизация улучшить подписанное деление;к сожалению, похоже, что это не так по двум причинам:

Приращение дивиденда должно стать увеличением величины, то есть приращением, если n> 0, уменьшением, если n <0. Это создает дополнительные расходы.</p>

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

Таким образом, похоже, что алгоритм округления может работатьделение со знаком, но будет ниже стандартного алгоритма округления.

Answer 7

Не только деление на степени 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           ║
╚═════════════╧══════════╧══════════════╝

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

Answer 8

Короче, не беспокойся перед фактом. Но потрудитесь после.

Если вы хотите иметь производительность, вам приходится использовать оптимизацию производительности компилятора , которая может работать против здравого смысла. Следует помнить, что разные компиляторы могут компилировать код по-разному, и они сами имеют разные виды оптимизации. Если мы говорим о компиляторе g++ и говорим о повышении его уровня оптимизации с помощью -Ofast или хотя бы флага -O3, по моему опыту он может скомпилировать тип long в код с еще большей производительностью чем любой unsigned тип, или даже просто int.

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

Оптимизированная многопоточная программа вычисления линейной алгебры может легко иметь> 10-кратную разницу в производительности точно оптимизирована по сравнению с неоптимизированной. Так что это имеет значение.

Вывод оптимизатора противоречит логике во многих случаях. Например, у меня был случай, когда разница между a[x]+=b и a[x]=b изменила время выполнения программы почти в 2 раза. И нет, a[x]=b не был быстрее.

Вот, например, NVidia с указанием , что для программирования их графических процессоров:

Примечание: как уже было рекомендовано, подписанная арифметика следует отдавать предпочтение арифметике без знака, где это возможно для лучшая пропускная способность на SMM. Стандарт языка C помещает больше ограничения на поведение переполнения для математики без знака, ограничение компилятора возможности оптимизации.

Answer 9

Целые числа со знаком и без знака всегда будут работать как инструкции с одним тактом и иметь одинаковую производительность чтения-записи, но согласно Д-р Андрей Александреску без знака предпочтительнее, чем подписано. Причина этого в том, что вы можете вписать вдвое большее количество чисел в одно и то же количество битов, поскольку вы не тратите впустую знаковый бит и будете использовать меньше инструкций для проверки отрицательных чисел, что приведет к увеличению производительности из-за уменьшения ПЗУ. По моему опыту с Kabuki VM , которая имеет сверхвысокопроизводительную реализацию Script , редко когда вам действительно требуется номер со знаком при работе с памятью. Я проводил майские годы, занимаясь арифметикой указателей со знаковыми и беззнаковыми числами, и я не нашел никакой пользы для подписанных, когда не требуется знаковый бит.

Где подпись может быть предпочтительнее, когда используется сдвиг битов для выполнения умножения и деления степеней 2, потому что вы можете выполнять отрицательные степени деления 2 с целыми числами дополнения со знаком 2. Пожалуйста, посмотрите больше видео на YouTube от Andrei , чтобы узнать больше о методах оптимизации. В моей статье вы также можете найти полезную информацию о самом быстром в мире алгоритме преобразования целых чисел в строку .

Answer 10

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