Требует ли беззнаковая математика больше инструкций процессора? - PullRequest
6 голосов
/ 10 июля 2011

Возьмем интегральную переменную C ++ i и предположим, что вы умножаете ее значение на 2.

Если i имеет подпись, я считаю, что операция в некоторой степени эквивалентна, прихотя бы математически , до:

i = i << 1;

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

i = (i << 1) & (decltype(i))-1;

Теперь я полагаю, что действительные машинные инструкции, вероятно, будут более краткими, чем последовательность смен для умножения.Но будет ли современный, скажем, x86, CPU иметь специальную инструкцию для unsigned / modulo math?Или выполнение математики со значениями без знака будет стоить дополнительной инструкции по сравнению с математикой со значениями со знаком?

(Да, было бы смешно заботиться об этом во время программирования; мне интересночистого любопытства.)

Ответы [ 7 ]

11 голосов
/ 10 июля 2011

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

Однако этоэто только половина истории.

C ++ определяет целочисленные переполнения со знаком как неопределенное поведение и целые числа без знака как модуль2.Это предлагает совершенно разные возможности оптимизации, которые приводят к другому коду.

Один пример:

int foo (int a)
{
  return a * 1000 / 500;
}

unsigned bar (unsigned a)
{
  return a * 1000 / 500;
}

Здесь foo можно оптимизировать так:

int foo (int a)
{
  return a * 2;
}

И бар останетсято же самое.

Обратите внимание, что математически эти две функции одинаковы, но они начинают давать разные результаты, если аргумент превышает INT_MAX / 1000.

Поскольку эффект переполнения со знаком не определену компилятора есть возможность просто притвориться, что INT_MAX не существует, когда речь идет об упрощении выражений.Для арифметики без знака это не так, и компилятор должен выдавать код, который выполняет умножение и деление.Это, конечно, медленнее, чем оптимизированный вариант.

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

OTOH мы обсуждали истории, в которых программисты на C / C ++ попадают в эту ловушку более одного раза из-за переполнения стека.

11 голосов
/ 10 июля 2011

Нет, больше инструкций не требуется, по крайней мере на x86.

Для некоторых операций (например, сложение и вычитание) одна и та же инструкция используется для типов со знаком и без знака. Это возможно, поскольку они работают одинаково при использовании представления дополнения 2 со знаковыми значениями.

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

Для других операций (например, сдвиг вправо) существуют отдельные инструкции: SHR (сдвиг вправо) для значений без знака и SAR (сдвиг арифметики вправо) для значений со знаком, в котором сохраняется бит знака.

Существуют также отдельные инструкции для умножения и деления со знаком / без знака: MUL / IMUL и DIV / IDIV, где IMUL и IDIV используются для значений со знаком.

2 голосов
/ 10 июля 2011

Предполагая переполнение по кругу, что в любом случае делают большинство (все?) Арифметические инструкции ЦП на оборудовании двух дополнений, << для типов без знака эквивалентно умножению. Поэтому единственная проблема, с которой вы сталкиваетесь, - это когда вы делаете арифметику с типом, который меньше, чем регистр, в котором он содержался.

Правила продвижения по крайней мере до int (или unsigned int) в арифметических выражениях в значительной степени разработаны, чтобы избежать этого: когда вы умножаете, скажем, unsigned short на 2, результат равен int (или unsigned int, если short и int имеют одинаковый размер). Что бы это ни было, нет необходимости брать какой-либо модуль, когда размер регистра соответствует типу. И с дополнением два, вам все равно не нужны разные инструкции для умножения C ++ со знаком и без знака: переполнение с переносом охватывает оба, если только оборудование не предлагает бит переполнения, и вы не заботитесь о его значении (-1 * 2 будет переполнением без знака, но не переполнение со знаком, даже если результирующий битовый шаблон остается тем же).

Единственное время, когда может потребоваться маска, - это если / когда вы конвертируете результат обратно в unsigned short. Даже тогда, я думаю, что с осторожностью реализация может иногда оставлять дополнительные «нерелевантные» биты в верхней части регистра размером int, используемого для хранения промежуточного значения unsigned short. Вы знаете, что эти дополнительные старшие биты не влияют на результаты сложения, умножения или вычитания по модулю и что они будут замаскированы, если значение будет сохранено в памяти (при условии, что инструкция, хранящая 2 младших байта int) регистр до 2 байт памяти, модуль в принципе свободен). Поэтому реализация должна быть осторожна, чтобы замаскировать ее перед делением, сдвигом вправо, сравнением и всем остальным, о чем я забыл, или используйте соответствующие инструкции, если они доступны.

1 голос
/ 10 июля 2011

Я думаю, что вы ошиблись: на беззнаковых типах данных, смещение битов в точности соответствует тому, что написано на олове, а незанятые биты заполнены нулями.Это вызывает правильные модульные арифметические операции над значениями типов для сдвига влево, то есть умножения.Сдвиг вправо не имеет арифметического аналога, потому что Z / nZ вообще не является делительным кольцом и нет понятия деления;сдвиг вправо - это просто усеченное деление.

С другой стороны, подписанные типы страдают от неоднозначности, поскольку существуют разные способы интерпретации битового шаблона как целого числа со знаком.С левым сдвигом на 2-х комплементах вы получите ожидаемый «переворот» для умножения, но нет канонического выбора поведения с правым сдвигом.В старом стандарте C я считаю, что он полностью определен реализацией, но я думаю, что C99 сделал это поведение специфичным.

1 голос
/ 10 июля 2011

ответ Interjay охватывает основы. Еще пара деталей:

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

Это зависит от процессора. В старые времена, когда транзисторы были дорогими, процессоры, такие как 6500 и 6800, имели инструкции, которые сдвигались только на один бит влево или вправо за один раз.

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

Или выполнение математики со значениями без знака будет стоить дополнительной инструкции по сравнению с математикой со значениями со знаком?

Никогда. Когда операция будет отличаться между неподписанным и подписанным, для каждого будут отдельные инструкции.

1 голос
/ 10 июля 2011

Математика без знака переполняется и, следовательно, неявно по модулю их соответствующего диапазона.

1 голос
/ 10 июля 2011

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

...