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

Ответ 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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

• Разделение на константу, которая равна 2 (см. также ответ от FredOverflow)
• Деление на постоянное число (например, мой компилятор реализует деление на 13, используя 2 asm-команды для unsigned и 6 инструкций для подписания)
• Проверка четности числа (я понятия не имею, почему мой компилятор MS Visual Studio реализует его с 4 инструкциями для чисел signed, gcc делает это с 1 инструкцией, как в случае с unsigned)

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

Примечание: некоторые DSP имеют команды быстрого умножения для типа signed short; в этом конкретном случае short быстрее, чем int.

Что касается разницы между int и long, я могу только догадываться (я не знаком с 64-разрядными архитектурами). Конечно, если int и long имеют одинаковый размер (на 32-разрядных платформах), то их производительность также одинакова.

Очень важное дополнение, на которое указывают несколько человек:

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

Это даст лучшую производительность, но коэффициент усиления нелинейный (т.е. не в 2 или 4 раза) и несколько непредсказуемый - это зависит от размера кэша и соотношения между вычислениями и передачами памяти в вашем приложении.

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

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

Ответ 8

Традиционно int - это собственный целочисленный формат целевой аппаратной платформы. Любой другой целочисленный тип может нести штрафные санкции.

EDIT:

В современных системах ситуация немного отличается:

• int может по сути быть 32-разрядной в 64-разрядных системах по соображениям совместимости. Я считаю, что это происходит в системах Windows.

• Современные компиляторы могут неявно использовать int при выполнении вычислений для более коротких типов в некоторых случаях.

Ответ 9

IIRC, на x86 подписанный /unsigned не должен иметь никакого значения. С другой стороны, короткая/длинная, это другая история, поскольку объем данных, которые нужно перенести в/из ОЗУ, больше для длинных (другие причины могут включать операции литья, такие как удлинение от короткого до длинного).

Ответ 10

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

Ответ 11

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

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