Signed integers are two’s complement (JF Bastien) is the result of a courtroom drama in both WG21 (C++) and WG14 (C). After intense prosecutorial cross-examination, the witness finally admitted in both courts that, yes, all known modern computers are two’s complement machines, and, no, we don’t really care about using C++ (or C) on the ones that aren’t. The C standard is likely to adopt the same change.
Здравствуйте, Vamp, Вы писали:
Ш>>новости от Саттера Ш>>Стандарт утвердит двоично-дополнительный код. V>К сожалению, знаковое переполнение по-прежнему не определено, и практического смысла лично для себя я не вижу.
Практический смысл есть — если утвердили P0907R4 в полном виде, то оно также специфицирует, что
1) signed x и unsigned x имеют одинаковое количество смысловых бит для любого x из стандартного набора,
Change If there are M value bits in the signed type and N in the unsigned type, then M = N-1 (whereas C says M ≤ N).
(Тут формулировка не включает знаковый бит, но суть та же)
2) конверсия unsigned->signed сохраняет все биты,
For integral types other than bool, the result is the unique value of the destination type that is congruent to the source integer modulo 2**N, where N is the number of value bits in the destination type. [Note: This conversion is conceptual; there is no change in the bit pattern other than that high-order bits may either be discarded or added. All added high-order bits will have the same value. —end note]
и в результате, имея какой-нибудь int, выполнив (int)((unsigned)a + (unsigned)b), получаешь гарантированное wrapping-сложение для знаковых. В предыдущих версиях оно было implementation-defined: формально финальная конверсия могла дать неожиданный результат.
А вот с этим сложением уже можно получать всё, что самому нужно.
А с учётом того, что 1) внутри эти конверсии превращаются в NOPʼы и хорошо оптимизируются, 2) в C++ получить беззнаковую пару к знаковому типу и наоборот — есть стандартные средства, то всё это ещё и шаблонизируется и эффективно компилируется.
PS:
Да, хотелось бы чего-то получше. Например, я агитирую за стиль, в котором режим операции задаётся контекстом, например, имея что-то вроде
a1 = [[arith(truncating)]] (a2 + a3);
получаешь, что будет сделано просто усечение до выходной разрядности; а сделав
#pragma STDC arith(checked)
получаешь до конца блока (или всего исходника) генерацию исключения при любой проблеме (не только переполнение, но и деление на 0, сдвиг на недопустимо большое количество бит, и т.д.)
Есть те, кто идёт почти тем же путём (C#), есть те, кто выносит такое в методы класса чисел (Rust), и, возможно, вскоре придём к этому.
Но тут для C++ решили сделать топорнее — просто прибить гвоздями факт окружающей реальности.
Что ж, и с этим можно работать.
Здравствуйте, σ, Вы писали:
V>>К сожалению, знаковое переполнение по-прежнему не определено, и практического смысла лично для себя я не вижу.
σ>Можно пример практического применения знакового переполнения?
Ваш вопрос принципиально некорректен. Суть не в каком-то "практическом применении", хотя оно тоже может вполне быть. Суть в предсказуемости поведения кода, где такое переполнение может происходить там, где оно как раз _не должно_ происходить согласно задумке.
Политика C/C++ в этом плане одна из самых неудачных и исторически неровных: задача отсутствия таких переполнений возлагается на программиста в случае типов со знаком, а компилятор за счёт этого получает хорошую гибкость для оптимизации. Тут же в случае беззнаковых такой гибкости нет, а операции однозначно определены как работающие по модулю. Это именно что корявый исторический артефакт — он возник от того, что в условиях отсутствия определённости варианта представления со знаком, и вообще, выполнится ли операция (или будет исключение), было постановлено, что такое переполнение непереносимо.
В то же время, даже для глубоко системного кода и соответствующих языков типа C++, подавляющему большинству кода не нужен никакой из этих вариантов: нужна именно защита с генерацией ошибки (как она будет представляться — сигнал, исключение, как-то иначе — это уже местные особенности). Небольшая часть операций требует заворачивания (оно же усечение). И только малая часть кода в узких местах реально требует той оптимизации, которую позволяет предположение о непереполнении.
Поэтому, адекватная политика состоит в том, что:
1. Для операции определяется, как она будет выполняться, и тут возможны основные варианты: 1) гарантированно оставляем основную часть результата, игнорируя переполнение; 2) гарантированно генерируем ошибку (исключение, сигнал, как-то иначе — уже местные особенности); 3) получаем полную свободу, но автор кода отвечает за последствия.
2. Политика может задаваться с достаточной грануляцией — вплоть до конкретной операции. Задание должно быть на этапе компиляции и контекстное (например, на блок или выражение). На каждую операцию — годится как слегка удобная, но подъёмная альтернатива. Ещё вариант — на тип, но он обычно самый неудобный.
Ничего этого в стандарт, к сожалению, не внесено, хотя и местные реализации есть, и предложения были.
GCCʼшные __builtin_mul_overflow() и т.п. — отличная база для построения, и их надо было стандартизовать в первую очередь. Оттуда же опции -ftrapv, -fwrapv — контекстное задание, хоть и на целый файл.
Здравствуйте, netch80, Вы писали:
>3) получаем полную свободу, но автор кода отвечает за последствия.
Объясните пожалуйста эту мысль? Я не вижу как это может отличаться от варианта 1 кроме как фиктивно/декларативно. В реалиях мы всегда имеем обрезанный результат в результате регистровых операций и флаг для условного перехода. Что за режим свободы? Для страждущих? :D
Здравствуйте, Mystic Artifact, Вы писали:
MA>Здравствуйте, netch80, Вы писали:
>>3) получаем полную свободу, но автор кода отвечает за последствия.
MA> Объясните пожалуйста эту мысль? Я не вижу как это может отличаться от варианта 1 кроме как фиктивно/декларативно.
тред и описанные там эффекты.
Если бы "не отличалось от варианта 1", то компилятор бы просто вывел младшие биты в i*1000000000. А он, увидев эту операцию, предположил, что программист гарантировал, что -2 <= i <= 2, и началось "мракобесие и джаз".
За счёт того, что компилятору позволено считать, что переполнения не происходит, он может выполнять множество операций в сторону оптимизации, включая:
1) выкидывание избыточных проверок — например, в коде в примере он выкинул в исходном случае проверку условия выхода из цикла как всегда истинную; аналогично, он может считать, что a+b>a всегда истинно, если знает, что b>0; или a+c>b+c заменить на a>b для любого c;
2) замену условий на вроде бы синонимичную; в том же треде в переделанном
варианте на два итератора цикла — решил, что надо условие i<10 усилить до i<3; или он может выражение i*3/3 заменить на просто i;
и так далее, причём учтите, что многие из участвующих сущностей могут быть не выражены в коде явно — например, возникать из макросов, inline-функций, или из результатов уже переделанных компилятором выражений, и предсказать их участие просто невозможно во всех случаях.
Где-то видел ссылку, что на подобных эффектах в коде, который ведёт целочисленные расчёты или работает с типичными задачами, которые ложатся на векторные операции с применением SSE и аналогов — средний выигрыш от подобных возможностей составляет около 20%, а иногда бывает и больше. Увы, сейчас не нашёл заново. Но это уже такой куш, от которого не отказываются (представьте себе игру, у которой на 20% больше fps, чем у конкурентов?)
И это не единственный эффект — вот на использование указателя, а уж про strict aliasing и type punning должен слышать любой, кто использует низкоуровневые действия.
MA> В реалиях мы всегда имеем обрезанный результат в результате регистровых операций и флаг для условного перехода.
Не-а — см. выше. До того, как операции лягут на регистровые операции, они успеют пройти 100500 трансформаций внутри компилятора.
И про "флаги для условного перехода" вы слишком ограниченно смотрите. Да, в двух самых актуальных на сейчас архитектурах — x86 и ARM — именно так, флаги (хотя и тут тонкость — у x86 на вычитании и сравнении CF это заём, а у ARM C — перенос). Но это уже достоверно показано как узкое место, и в новых разработках такие флаги не делают.
MA> Что за режим свободы? Для страждущих? :D
Для страждущих, да. Страждущих максимальной оптимизации.
Проблема в том, что те же люди в том же коде в большинстве случаев этого как раз не хотят, за исключением небольшого набора самых узких мест.
Поэтому, как уже говорил, я выступаю за введение синтаксического контекста, и умолчание в сторону генерации ошибки на любой такой операции.
Спасибо за столь развернутый ответ. Достаточно было просто немного уточнить и я бы понял. Вчера прочитал когда, видать зазевался и не уловил ход мысли, устал.
Я честно говоря категорически против всяких оптимизаций за счет UB, полагаю не должно быть в языке UB всяких, но это уже не про C++. Ничего не должно мешать добиваться тех же результатов в плане оптимизации, но опираясь на явно заданное поведение.
Но смысл "неограниченных" операций я понял. Хотя пока не уверен как это в идеале должно быть.
Здравствуйте, netch80, Вы писали:
N>И про "флаги для условного перехода" вы слишком ограниченно смотрите. Да, в двух самых актуальных на сейчас архитектурах — x86 и ARM — именно так, флаги (хотя и тут тонкость — у x86 на вычитании и сравнении CF это заём, а у ARM C — перенос). Но это уже достоверно показано как узкое место, и в новых разработках такие флаги не делают.
Закостенелось мозга, трудное детство с Z80.
А как делают сейчас? В чем разница? Если есть можно просто название какой-нибудь архитектуры / примеров для того что б погуглить?
N>Поэтому, как уже говорил, я выступаю за введение синтаксического контекста, и умолчание в сторону генерации ошибки на любой такой операции.
Мне эта идея нравится. Я даже в шарпе явно пишу checked / unchecked в выражениях, где это важно. Ну и в реалиях дотнета лучше б они по дефолту бы ставили checked режим в настройках проекта, а то и там фичей не шибко то пользуются, хотя она есть да и не тормозит оно абсолютно для большинства случаев.
Здравствуйте, Mystic Artifact, Вы писали:
MA>Спасибо за столь развернутый ответ. Достаточно было просто немного уточнить и я бы понял. Вчера прочитал когда, видать зазевался и не уловил ход мысли, устал.
Ну, считайте, я воспользовался шансом прочитать небольшую лекцию и чуть структурировать это для себя же, и для тех, кто зайдёт позже из какого-нибудь поиска.
MA>Я честно говоря категорически против всяких оптимизаций за счет UB, полагаю не должно быть в языке UB всяких, но это уже не про C++. Ничего не должно мешать добиваться тех же результатов в плане оптимизации, но опираясь на явно заданное поведение.
Ну это тема для длительной и сложной дискуссии. Например в таких именно на эту тему часто влезает khim@habr, утверждая, что подобные UdB неизбежны и даже полезны, и приводя примеры, как они встречаются и в сильно более высокоуровневых языках, типа Java. Можете посмотреть его комментарии на эту тему.
Мне тоже кажется, что совсем от таких проблем избавиться нельзя. Но минимизировать до разумного предела и максимально устранить именно там, где они неожиданнее и неприятнее всего бьют — можно и нужно.
Здравствуйте, Mystic Artifact, Вы писали:
N>>И про "флаги для условного перехода" вы слишком ограниченно смотрите. Да, в двух самых актуальных на сейчас архитектурах — x86 и ARM — именно так, флаги (хотя и тут тонкость — у x86 на вычитании и сравнении CF это заём, а у ARM C — перенос). Но это уже достоверно показано как узкое место, и в новых разработках такие флаги не делают.
MA> Закостенелось мозга, трудное детство с Z80. MA> А как делают сейчас? В чем разница? Если есть можно просто название какой-нибудь архитектуры / примеров для того что б погуглить?
Для начала, все классические RISC-машины: из более-менее распространившихся это MIPS, Alpha, и активно растущий сейчас RISC-V.
Делают так:
1. Таких флагов, как NZVC или более сокращённые аналогичные наборы, нет вообще. Команды операций не используют их, не проверяют и не ставят.
2. Вместо команд проверки условий по флагам используются команды сравнений значений регистров. То есть достаточно 10 сравнений (==, != — независимо от знака; <, <=, >, >= — в знаковом и беззнаковом варианте).
Вот пример из спеки по RISC-V, где они, кроме утверждения, вводят некоторые пояснения:
We did not include special instruction set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches. Overflow checking for unsigned addition requires only a single additional branch instruction after the addition:
add t0, t1, t2;
bltu t0, t1, overflow
For signed addition, if one operand’s sign is known, overflow checking requires only a single branch after the addition: addi t0, t1, +imm; blt t0, t1, overflow. This covers the common case of addition with an immediate operand. For general signed addition, three additional instructions after the addition are required, leveraging the observation that the sum should be less than one of the operands if and only if the other operand is negative.
Сложение в обоих случаях — оставление младших бит результата (32 или 64, не важно тут).
bltu — это "branch on less than, unsigned"; то есть перейти, если t0 < t1, без знака. Понятно, что этого достаточно для проверки факта переполнения без знака.
slti, slt — это установка значения целевого регистра (первого аргумента) в 1, если условие выполнено, и 0, если не выполнено. То есть во втором примере t3 ставится в 1, если t2 < 0; t4 — в 1, если t0 < t1.
Понятно, что при обрезании младших бит проверка переполнения c=a+b делается (если писать на C)
(c<a) != (b<0)
и ровно это и проверяется в тех командах.
Для умножения, проверка переполнения делается умножением N*N->2N бит и сравнением старших N бит результата с нулём (для беззнаковых) и знаком младшей части (для знаковых). Кстати, без длинного произведения тут самая тяжёлая для эмуляции ситуация — если есть только умножение N*N->N, то иногда приходится даже делать обратно деление для проверки результата. Вот эти вещи таки лучше перекладывать на ассемблер (ну или на __builtin_mul_overflow, если он есть, как в GCC и Clang).
На MIPS, Alpha делают по сути то же самое. У MIPS есть специфика — команды сложения-вычитания идут парами: например, addu просто складывает, а add генерирует исключение (но не ставит флаг), если было знаковое переполнение. Для исключения по беззнаковому переполнению у них нет аналога. Похоже, тут влияние того же перекоса в C/C++.
Кстати про переходы — в zSeries, несмотря на то, что у них собственная система флагов условий (более старая — 2 бита, а не 4), добавлены инструкции перехода по сравнению двух регистров без промежуточных флагов: группа CRB, CRJ и тому подобные. И их активно используют в компилированном.
Польза от неиспользования флагов условий — то, что легко развязать операции с разными данными. Флаговый регистр — удобно, но он один. Поэтому получаются, что заметная часть инструкций дерётся за доступ к нему и влияние на его значения, соответственно это тормозит работу. Без такого узкого места "сразу такая приятность гибкость в теле образуется". Хотя я бы предпочёл варианты инструкций, где в качестве флагового задан ещё один общий регистр (если не нужен, как для ~99% выполняемых инструкций — ставить в пустой регистр).
N>>Поэтому, как уже говорил, я выступаю за введение синтаксического контекста, и умолчание в сторону генерации ошибки на любой такой операции. MA> Мне эта идея нравится. Я даже в шарпе явно пишу checked / unchecked в выражениях, где это важно. Ну и в реалиях дотнета лучше б они по дефолту бы ставили checked режим в настройках проекта, а то и там фичей не шибко то пользуются, хотя она есть да и не тормозит оно абсолютно для большинства случаев.
Здравствуйте, σ, Вы писали:
σ>Но на самом деле скорее всего означает, что просто её не осилил.
С опытом приходит понимание того, что всё что надо "осилять" — кривое изначально.
Правильные вещи всегда просты и интуитивно понятны.
Причём это касается всего: и библиотек, и языков, и программных сред, и научных теорий...
AS>С опытом приходит понимание того, что всё что надо "осилять" — кривое изначально. AS>Правильные вещи всегда просты и интуитивно понятны. AS>Причём это касается всего: и библиотек, и языков, и программных сред, и научных теорий...
N>Делают так: N>1. Таких флагов, как NZVC или более сокращённые аналогичные наборы, нет вообще. Команды операций не используют их, не проверяют и не ставят. N>2. Вместо команд проверки условий по флагам используются команды сравнений значений регистров. То есть достаточно 10 сравнений (==, != — независимо от знака; <, <=, >, >= — в знаковом и беззнаковом варианте).
Все новое — хорошо забытое старое.
В машинах 50-х годов и в начале 60-х было так же...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
N>>Делают так: N>>1. Таких флагов, как NZVC или более сокращённые аналогичные наборы, нет вообще. Команды операций не используют их, не проверяют и не ставят. N>>2. Вместо команд проверки условий по флагам используются команды сравнений значений регистров. То есть достаточно 10 сравнений (==, != — независимо от знака; <, <=, >, >= — в знаковом и беззнаковом варианте). LVV>Все новое — хорошо забытое старое. LVV>В машинах 50-х годов и в начале 60-х было так же...
В каких именно?
Смотрю, например, на линию БЭСМ, а там (БЭСМ-6)
26 ПО Переход по ω == 0
27 ПЕ Переход по ω != 0
Рядом есть
34 ПИО Переход по нулю индекс-регистра
35 ПИНО Переход по ненулю индекс-регистра
но это по нулю одного регистра (причём индекса), а не сравнению двух => ещё вычесть надо; а как проверить на больше или меньше 0?
Минск-22 — да, переход по знаку (два адреса одновременно заданы) и по равенству нулю. Это уже ближе. Но всё равно вычитать надо.
Какие ещё были показательны в этом плане?
Но тут важнее то, что если в 50-60-х такое проектировали от незнания альтернатив, то в RISC это делают сознательно. И не всегда и не везде.
ARM, например, идёт другим путём — там NZVC, но набор операций, которые их используют, обычно ограничен, соответствующий флажок ставят только при явной необходимости.
Кроме того, там есть явный переход по равенству/неравенству регистра нулю, что исключает прохождение через CC для этого.
На сейчас это почти оптимально (могли бы ещё добавить явные сравнения, и совсем было бы хорошо).
