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

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

Если это так, то будет ли это продолжаться коротко и долго?

 JeremyP17 янв. 2011 г., 12:34
Недостаточно того, что вам нужно заботиться об этом.
 Brett11 нояб. 2012 г., 22:31
@ JeremyP, могу ли я предположить, что вы говорили правду только для большинства разработчиков и приложений ...
 JeremyP12 нояб. 2012 г., 09:03
@Brett: Разница между арифметикой со знаком и без знака на большинстве процессоров равна нулю. Разница для разных размеров незначительна, если вы не занимаетесь арифметикой.

Ответы на вопрос(12)

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

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

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

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

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

 Philipp17 янв. 2011 г., 12:04
int всегда имеет ширину 32 бита во всех известных мне системах (Windows, Linux, Mac OS X, независимо от того, является ли процессор 64-разрядным или нет). Этоlong другой тип: 32 бита в Windows, но одно слово в Linux и OS X.
 Philipp17 янв. 2011 г., 11:59
да, традиционно ;-) на современных 64-битных системах,int по-прежнему 32-битная ширина, но 64-битные типы (long или жеlong longв зависимости от ОС) должно быть как минимум так же быстро.

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

Например с 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           ║
╚═════════════╧══════════╧══════════════╝

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

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

 phuclv09 июн. 2017 г., 02:51
это не имеет значения на уровне инструкций, но с уровня C ++ это имеет значение
 CAFxX17 янв. 2011 г., 11:57
Также имейте в виду, что некоторые компиляторы могут иметь оптимизации, которые не применяются ко всем целочисленным типам. Например. по крайней мере, старые компиляторы Intel не могли применять автовекторизацию, если счетчик цикла for был чем-то другим, чем подписанное int.
 phuclv11 июн. 2017 г., 03:08
Нет, есть другие случаи, когда значение имеет значение. Вы читали другие ответы?
 CAFxX13 июн. 2017 г., 07:34
Я сделал. А вы? Большинство из них говорят, что нет больших различий, за исключением делений с постоянной времени компиляции и переменных индукции цикла (о которых я упоминал в своем комментарии). Даже в твоем тывроде обратите внимание, что в более новых процессорах разница не очень большая (см., например, таблицы Sandy Bridge)
 CAFxX11 июн. 2017 г., 00:25
@ LưuVĩnhPhúc Вы говорите о переполнении подписки, являющемся UB? если так, то единственный известный мне случай, в котором имеет значение, - это случай, в котором сложнее оптимизировать компиляторы, чтобы рассуждать о беззнаковых интергерах, используемых в качестве счетчиков циклов / индукционных переменных (и это было отражено в моем комментарии непосредственно над вашим)

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

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

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

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

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

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

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 раза) и несколько непредсказуемым - это зависит от размера кэша и взаимосвязи между вычислениями и передачей памяти в вашем приложении.

 anatolyg10 мая 2017 г., 10:51
@JoshParnell Я думаю, ты имеешь в видуshort быстрее чемint когдасвязанный с памятью, По моему опыту, они имеют одинаковую производительность на x86, иshort медленнее на ARM.
 anatolyg19 янв. 2011 г., 17:59
@ Grizzly Я согласен (мое приложение на самом деле требует больших вычислительных ресурсов, поэтому мой опыт работы сshort отличается от твоего / чужого)
 anatolyg30 июн. 2014 г., 20:55
@martinkunev Абсолютно! Это может быть единственной причиной использованияshort сегодня (с не кеш-памятью практически бесконечно) и очень веская причина.
 Grizzly18 янв. 2011 г., 22:26
Я был бы осторожен с утверждением о производительности short по сравнению с int. Хотя арифметика «может» быстрее с использованием int, следует помнить, что целочисленная арифметика редко является узким местом (по крайней мере, на современных процессорах для настольных компьютеров), с другой стороны, пропускная способность памяти часто бывает такой, поэтому для больших наборов данных короткие значения могут фактически дать значительно лучшую производительность, чем внутр. Кроме того, для кода с автоматическим вектором использование меньших типов данных часто означает, что в один элемент может быть добавлено больше элементов данных, поэтому даже арифметическая производительность может увеличиться (хотя вряд ли, учитывая текущее состояние автовекторизаторов).
 bcrist07 сент. 2014 г., 01:25
Оперативная память @anatolyg может быть практически бесконечной, но не забывайте, что 32-разрядные программы по-прежнему превосходят по численности 64-разрядные с большим отрывом, что означает, что независимо от того, сколько ОЗУ доступно, вы все равно часто ограничены 2 ГБ используемого адреса -пространство.

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

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

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

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

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

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

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

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

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

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

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

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

Решение Вопроса

Деление на степени 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
 ulidtko13 июн. 2016 г., 09:22
В этом масштабебольше инструкций не всегда значитмедленнее во время выполнения для современных конвейерных архитектур процессоров. То есть Я бы все-таки сделал замер, прежде чем делать далеко идущие выводы.
 fredoverflow04 окт. 2014 г., 18:08
@ Manu343726 Что если делитель не является степенью 2? (И даже если бы это было так, вы должны сначала вычислить двоичный логарифм числа перед сдвигом.)
 Manu34372630 дек. 2013 г., 12:57
Почему фокус не может быть сделан для непостоянных делителей? Первый операнд x86shrl должен быть буквальным?
 sharptooth17 янв. 2011 г., 12:31
Это будет работать только в том случае, если делителем является известная постоянная времени компиляции, являющаяся степенью двойки, не так ли?
 AProgrammer17 янв. 2011 г., 13:06
@sharptooth, для деления, да. Возможно, есть другие приемы манипулирования битами, которые действительны только для неподписанных. Или подписано. Я не думаю, что положительный эффект только в одном направлении.

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

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

 sbi17 янв. 2011 г., 11:55
+1 для «если вы хотите знать, вам нужно измерить». Это очень раздражает, что на это нужно отвечать почти еженедельно.

Ваш ответ на вопрос