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

Деление на степени 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. Некоторые примеры:

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

То же самое и с Intel Pentium.

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

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

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

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

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ:

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

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

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

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