Почему арифметическое переполнение игнорируется?

76

Вы когда-нибудь пытались суммировать все числа от 1 до 2 000 000 на вашем любимом языке программирования? Результат легко вычислить вручную: 2 000 001 000 000, что примерно в 900 раз превышает максимальное значение 32-разрядного целого числа без знака.

C # распечатывает -1453759936- отрицательное значение! И я думаю, что Java делает то же самое.

Это означает, что есть некоторые распространенные языки программирования, которые по умолчанию игнорируют арифметическое переполнение (в C # есть скрытые опции для изменения этого). Это поведение выглядит очень рискованным для меня, и не было ли крушение Ariane 5 вызванным таким переполнением?

Итак: какие дизайнерские решения стоят за таким опасным поведением?

Редактировать:

Первые ответы на этот вопрос выражают чрезмерные затраты на проверку. Давайте выполним короткую программу на C #, чтобы проверить это предположение:

Stopwatch watch = Stopwatch.StartNew();
checked
{
    for (int i = 0; i < 200000; i++)
    {
        int sum = 0;
        for (int j = 1; j < 50000; j++)
        {
            sum += j;
        }
    }
}
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);

На моей машине проверенная версия занимает 11015мс, в то время как непроверенная версия - 4125мс. Т.е. шаги проверки занимают почти вдвое больше времени, чем сложение чисел (всего в 3 раза больше исходного времени). Но с 10 000 000 000 повторений время, затрачиваемое на проверку, все равно составляет менее 1 наносекунды. Может быть ситуация, когда это важно, но для большинства приложений это не имеет значения.

Изменить 2:

Я перекомпилировал наше серверное приложение (служба Windows, анализирующая данные, полученные от нескольких датчиков, с некоторым перебором чисел) с /p:CheckForOverflowUnderflow="false"параметром (обычно я включаю проверку переполнения) и развернул его на устройстве. Мониторинг Nagios показывает, что средняя загрузка процессора осталась на уровне 17%.

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

Бернхард Хиллер
источник
19
просто как примечание, для C # вы можете использовать checked { }раздел, чтобы отметить части кода, которые должны выполнять проверки арифметического переполнения. Это связано с производительностью
Павел Лукасик
14
"Когда-нибудь пытались суммировать все числа от 1 до 2 000 000 на вашем любимом языке программирования?" - Да: (1..2_000_000).sum #=> 2000001000000. Еще один из моих любимых языков: sum [1 .. 2000000] --=> 2000001000000. Не мой любимый Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000. (Чтобы быть справедливым, последний обманывает.)
Йорг Миттаг
27
@BernhardHiller Integerв Haskell имеет произвольную точность, он будет содержать любое число до тех пор, пока у вас не закончится выделенная RAM.
Полигном,
50
Крушение Ariane 5 было вызвано проверкой на переполнение, которое не имело значения - ракета находилась в той части полета, где результат расчета больше не требовался. Вместо этого было обнаружено переполнение, и это привело к прерыванию полета.
Саймон Б,
9
But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.это признак оптимизации цикла. Также это предложение противоречит предыдущим числам, которые кажутся мне очень важными.
USR

Ответы:

86

Для этого есть 3 причины:

  1. Стоимость проверки на переполнения (для каждой отдельной арифметической операции) во время выполнения является чрезмерной.

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

  3. В некоторых случаях (например, вычисления CRC, библиотеки больших чисел и т. Д.) «Перенос по переполнению» более удобен для программистов.

Brendan
источник
10
@DmitryGrigoryev unsigned intне должен приходить в голову, потому что язык с проверкой переполнения должен проверять все целочисленные типы по умолчанию. Вы должны написать wrapping unsigned int.
user253751
32
Я не покупаю аргумент стоимости. ЦП проверяет переполнение при расчете целого числа КАЖДЫЙ и устанавливает флаг переноса в АЛУ. Отсутствует поддержка языка программирования. Простая didOverflow()встроенная функция или даже глобальная переменная, __carryкоторая разрешает доступ к флагу переноса, обойдется без процессорного времени, если вы его не используете.
Slebetman
37
@ Slebetman: Это x86. ARM нет. Например ADD, не устанавливает перенос (вам нужно ADDS). Itanium даже не имеют флаг переноса. И даже на x86 у AVX нет флагов переноса.
MSalters
30
@slebetman Устанавливает флаг переноса, да (заметьте, на x86). Но тогда вы должны прочитать флаг переноса и определиться с результатом - это дорогая часть. Поскольку арифметические операции часто используются в циклах (и при этом в узких циклах), это может легко предотвратить многие безопасные оптимизации компилятора, которые могут очень сильно повлиять на производительность, даже если вам нужна только одна дополнительная инструкция (и вам нужно намного больше, чем это ). Это означает, что это должно быть по умолчанию? Может быть, особенно на таком языке, как C #, где говорить uncheckedдостаточно легко; но вы можете переоценивать, как часто имеет значение переполнение.
Луаан
12
addsЦена ARM такая же, как add(это просто 1-битный флаг инструкции, который определяет, будет ли обновляться флаг переноса). addИнструкция MIPS перехватывает переполнение - вы должны попросить не перехватывать переполнение, используя adduвместо этого!
user253751
65

Кто сказал, что это плохой компромисс ?!

Я запускаю все свои производственные приложения с включенной проверкой переполнения. Это опция компилятора C #. Я фактически оценил это и не смог определить разницу. Стоимость доступа к базе данных для генерации (не игрушечного) HTML затмевает затраты на проверку переполнения.

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

В случае, если мне нужна производительность, что иногда имеет место, я отключаю проверку переполнения, используя unchecked {}детальный анализ. Когда я хочу сказать, что я полагаюсь на операцию, не переполняющуюся, я мог бы избыточно добавить checked {}код, чтобы документировать этот факт. Я помнил о переполнениях, но я не обязательно должен быть благодаря проверке.

Я считаю, что команда C # сделала неправильный выбор, когда они решили не проверять переполнение по умолчанию, но этот выбор теперь закреплен из-за серьезных проблем совместимости. Обратите внимание, что этот выбор был сделан примерно в 2000 году. Аппаратное обеспечение было менее способным, а .NET пока не имело большого значения Возможно .NET хотел обратиться к программистам на Java и C / C ++ таким образом. .NET также предназначен для возможности быть ближе к металлу. Вот почему у него небезопасный код, структуры и отличные возможности нативных вызовов, которых нет в Java.

Чем быстрее работает наше оборудование и чем эффективнее компиляторы, тем привлекательнее проверка по умолчанию.

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

У JavaScript проблемы с переполнением еще хуже. Числа JavaScript - это двойные числа с плавающей запятой. «Переполнение» проявляется как оставление полностью точного набора целых чисел. В результате получаются слегка неправильные результаты (например, отключение по одному - это может превратить конечные циклы в бесконечные).

Для некоторых языков, таких как C / C ++, проверка переполнения по умолчанию явно неуместна, поскольку приложения, которые пишутся на этих языках, нуждаются в производительности. Тем не менее, есть усилия , чтобы сделать C / C ++ в более безопасном языке, позволяя выбрать в в более безопасный режим. Это похвально, так как 90-99% кода имеет тенденцию быть холодным. Примером является fwrapvопция компилятора, которая принудительно оборачивает дополнение 2. Это функция «качества реализации» компилятором, а не языком.

У Haskell нет логического стека вызовов и не указан порядок оценки. Это делает исключения происходить в непредсказуемых точках. В a + bэто определено ли aили bоценивается первым и являются ли эти выражения прекращается вообще или нет. Поэтому для Haskell имеет смысл использовать неограниченные целые числа большую часть времени. Этот выбор подходит для чисто функционального языка, потому что исключения действительно неуместны в большинстве кодов на Haskell. И деление на ноль действительно является проблематичным пунктом в дизайне языка Haskells. Вместо неограниченных целых чисел они могли бы также использовать целые числа с фиксированной шириной, но это не соответствует теме «сосредоточиться на правильности», которую поддерживает язык.

Альтернативой исключениям переполнения являются ядовитые значения, которые создаются неопределенными операциями и распространяются через операции (например, NaNзначение с плавающей запятой ). Это кажется намного дороже, чем проверка переполнения, и делает все операции медленнее, а не только те, которые могут дать сбой (за исключением аппаратного ускорения, которое обычно имеет плавающее значение, а целое число обычно не имеет - хотя у Itanium есть NaT, который не является «вещью» ). Я также не совсем вижу смысла заставлять программу продолжать хромать вместе с плохими данными. Это как ON ERROR RESUME NEXT. Он скрывает ошибки, но не помогает получить правильные результаты. Supercat указывает, что иногда это делает оптимизацию производительности.

USR
источник
2
Отличный ответ. Так какова ваша теория о том, почему они решили сделать это таким образом? Просто копировать всех, кто копировал C и, в конечном счете, сборку и двоичный файл?
jpmc26
19
Когда 99% вашей пользовательской базы ожидают поведения, вы склонны отдавать его им. А что касается «копирования C», то на самом деле это не копия C, а ее расширение. C гарантирует поведение без исключений unsignedтолько для целых чисел. Поведение целочисленного переполнения со знаком - фактически неопределенное поведение в C и C ++. Да, неопределенное поведение . Так уж сложилось, что почти каждый реализует это как переполнение дополнения 2. C # фактически делает его официальным, а не оставляет его UB, как C / C ++
Cort Ammon
10
@CortAmmon: язык, который разработал Деннис Ритчи, определил поведение обтекания целых чисел со знаком, но на самом деле не подходил для использования на платформах, не являющихся дополнением к двум. Хотя допущение определенных отклонений от точного переноса с двумя дополнениями может значительно помочь в некоторых оптимизациях (например, если компилятору заменить x * y / y на x, можно сохранить умножение и деление), авторы компилятора интерпретируют Undefined Behavior не как возможность сделать что имеет смысл для данной целевой платформы и области применения, а скорее как возможность выбросить смысл из окна.
суперкат
3
@CortAmmon - Проверьте код, сгенерированный gcc -O2для x + 1 > x(где xесть int). Также см. Gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . Поведение 2-дополнения при переполнении со знаком в C является необязательным , даже в реальных компиляторах, и по gccумолчанию игнорирует его на обычных уровнях оптимизации.
Джонатан В ролях
2
@supercat Да, большинство авторов компиляторов Си больше заинтересованы в том, чтобы некоторые нереалистичные тесты выполнялись на 0,5% быстрее, чем пытались обеспечить разумную семантику для программистов (да, я понимаю, почему это не простая задача, и есть некоторые разумные оптимизации, которые могут вызвать неожиданные результаты при объединении, Яда, Яда, но все же это просто не фокус, и вы заметите это, если вы будете следить за разговорами). К счастью, есть люди, которые пытаются добиться большего .
Voo
30

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

Килиан Фот
источник
28
Это все равно что сказать, что проверки на переполнение буфера должны быть опущены, потому что они вряд ли когда-либо происходят ...
Бернхард Хиллер
73
@BernhardHiller: и это именно то, что делают C и C ++.
Майкл Боргвардт,
12
@DavidBrown: Как и арифметические переполнения. Первые не компрометируют ВМ, хотя.
дедупликатор
35
@Deduplicator делает отличную точку. CLR был тщательно спроектирован таким образом, чтобы проверяемые программы не могли нарушать инварианты среды выполнения, даже когда происходят плохие вещи. Безопасные программы могут, конечно, нарушать свои собственные инварианты, когда происходят плохие вещи.
Эрик Липперт
7
@svick Арифметические операции, вероятно, встречаются гораздо чаще, чем операции индексации массивов. И большинство целочисленных размеров достаточно велики, поэтому очень редко можно выполнять арифметику с переполнением. Таким образом, соотношение затрат и выгод очень разные.
Бармар
20

Какие дизайнерские решения стоят за таким опасным поведением?

«Не заставляйте пользователей платить за производительность за функцию, которая им может не понадобиться».

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

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

Майкл Боргвардт
источник
18
Это определенно не упущение в дизайне C #. Разработчики C # сознательно создали два режима: checkedи uncheckedдобавили синтаксис для переключения между ними локально, а также переключатели командной строки (и настройки проекта в VS), чтобы изменить его глобально. Вы можете не согласиться с установкой uncheckedпо умолчанию (я делаю), но все это явно очень обдумано.
свик
8
@slebetman - просто для справки: здесь стоимость - это не стоимость проверки на переполнение (тривиально), а стоимость запуска другого кода в зависимости от того, произошло ли переполнение (что очень дорого). Процессоры не любят условные операторы ветвления.
Джонатан В ролях
5
@jcast Разве предсказание ветвления на современных процессорах почти не устранит штраф за условные операторы ветвления? В конце концов, в нормальном случае не должно быть переполнения, поэтому это очень предсказуемое поведение ветвления.
CodeMonkey
4
Согласитесь с @CodeMonkey. Компилятор вставил бы условный переход в случае переполнения на страницу, которая обычно не загружена / не загружена. Прогноз по умолчанию для этого «не принят», и он, вероятно, не изменится. Всего накладных расходов является одна инструкция в конвейере. Но это одна служебная инструкция на арифметическую инструкцию.
MSalters
2
@MSalters да, есть дополнительные инструкции. И влияние может быть значительным, если у вас проблемы исключительно с процессором. Я полагаю, что в большинстве приложений со смешанным объемом ввода-вывода и загруженным процессором влияние будет минимальным. Мне нравится способ Rust: добавлять служебные данные только в сборках Debug, но удалять их в сборках Release.
CodeMonkey
20

наследие

Я бы сказал, что проблема, вероятно, коренится в наследстве. В С:

  • переполнение со знаком - неопределенное поведение (компиляторы поддерживают флаги для его переноса),
  • беззнаковое переполнение - это определенное поведение (оно переносится).

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

Приводит к Стату-кво

Тот факт, что C (и, соответственно, расширение C ++) не требуют обнаружения переполнения по очереди, означает, что проверка переполнения является вялой.

Аппаратное обеспечение в основном обслуживает C / C ++ (серьезно, в x86 есть strcmpинструкция (также известная как PCMPISTRI с SSE 4.2)!), И, поскольку C не заботится, обычные ЦП не предлагают эффективных способов обнаружения переполнений. В x86 вы должны проверять флаг для каждого ядра после каждой потенциально переполненной операции; когда то, что вы действительно хотите, - это «испорченный» флаг на результате (так же, как распространяется NaN). И векторные операции могут быть еще более проблематичными. Некоторые новые игроки могут появиться на рынке с эффективной обработкой переполнения; а пока х86 и ARM пофиг.

Оптимизаторы компилятора не способны оптимизировать проверки переполнения или даже оптимизировать при наличии переполнения. Некоторые ученые, такие как Джон Регер, жалуются на это статуэтку , но факт заключается в том, что когда простой факт создания переполнений «сбои» предотвращает оптимизацию даже до того, как сборка попадает в ЦП, это может нанести вред. Особенно, когда это предотвращает автовекторизацию ...

С каскадными эффектами

Таким образом, в отсутствие эффективных стратегий оптимизации и эффективной поддержки ЦП, проверка переполнения является дорогостоящей. Гораздо дороже, чем упаковка.

Добавьте немного раздражающего поведения, например, x + y - 1может переполниться, когда x - 1 + yнет, что может законно раздражать пользователей, и проверка переполнения обычно отбрасывается в пользу переноса (который обрабатывает этот пример и многие другие изящно).

Тем не менее, не вся надежда потеряна

В компиляторах clang и gcc была предпринята попытка внедрить «дезинфицирующие средства»: способы инструментальной обработки двоичных файлов для обнаружения случаев неопределенного поведения. При использовании -fsanitize=undefinedподписанное переполнение обнаруживается и прерывает программу; очень полезно во время тестирования.

В языке программирования Rust по умолчанию включена проверка переполнения в режиме отладки (для повышения производительности используется арифметика обтекания в режиме выпуска).

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

Матье М.
источник
6
@DmitryGrigoryev - это противоположность эффективному способу проверки на переполнение, например, в Haswell он снижает пропускную способность с 4 обычных добавлений за цикл до только 1 проверенного сложения, и это до рассмотрения влияния ошибочных прогнозов ветвлений joи более глобальные эффекты загрязнения они добавляют к состоянию предсказателя ветвления и увеличению размера кода. Если бы этот флаг был липким, это дало бы некоторый реальный потенциал ... и тогда вы все равно не сможете сделать это правильно в векторизованном коде.
3
Поскольку вы ссылаетесь на сообщение в блоге, написанное Джоном Регером, я подумал, что было бы целесообразно также сослаться на другую его статью , написанную за несколько месяцев до той, на которую вы ссылались. В этих статьях рассказывается о разных принципах: в предыдущей статье целые числа имеют фиксированный размер; целочисленная арифметика проверяется (т. е. код не может продолжать свое выполнение); есть либо исключение, либо ловушка. В новой статье говорится об исключении целых чисел фиксированного размера, что исключает переполнения.
Rwong
2
@rwong Целые числа бесконечного размера также имеют свои проблемы. Если ваше переполнение является результатом ошибки (которая часто бывает), он может превратить быстрый сбой в длительную агонию, которая потребляет все ресурсы сервера, пока все не выйдет из строя ужасно. Я в основном поклонник подхода «провалить рано» - меньше шансов отравить всю окружающую среду. 1..100Вместо этого я предпочел бы типы Pascal-ish - будьте явными относительно ожидаемых диапазонов, а не «принудительно» в 2 ^ 31 и т. Д. Конечно, некоторые языки предлагают это, и они имеют тенденцию делать проверку переполнения по умолчанию (иногда в даже во время компиляции).
Луаан
1
@Luaan: Интересно то, что часто промежуточные вычисления могут временно переполняться, но результат - нет. Например, в вашем диапазоне 1..100 x * 2 - 2может произойти переполнение, когда значение xравно 51, даже если результат соответствует, что заставит вас перестроить вычисления (иногда неестественным образом). По своему опыту я обнаружил, что обычно предпочитаю выполнять вычисления более крупного типа, а затем проверять, подходит ли результат или нет.
Матье М.
1
@MatthieuM. Да, вот где вы попадаете на территорию «достаточно умного компилятора». В идеале значение 103 должно быть действительным для типа 1..100, если оно никогда не используется в контексте, где ожидается истинное значение 1..100 (например, x = x * 2 - 2должно работать для всех случаев, xкогда назначение приводит к действительному значению 1). .100 номер). То есть операции над числовым типом могут иметь более высокую точность, чем сам тип, при условии, что присваивание соответствует. Это было бы весьма полезно в тех случаях, (a + b) / 2когда игнорирование (без знака) переполнения может быть правильным вариантом.
Луаан
10

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

for (int i=0; i<100; i++)
{
  Operation1();
  x+=i;
  Operation2();
}

если начальное значение x вызовет переполнение на 47-м проходе через цикл, Operation1 выполнится 47 раз, а Operation2 выполнится 46. При отсутствии такой гарантии, если ничего внутри цикла не использует x, и ничего будет использовать значение x после сгенерированного исключения с помощью Operation1 или Operation2, код можно заменить на:

x+=4950;
for (int i=0; i<100; i++)
{
  Operation1();
  Operation2();
}

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

if (x < INT_MAX-4950)
{
  x+=4950;
  for (int i=0; i<100; i++)
  {
    Operation1();
    Operation2();
  }
}
else
{
  for (int i=0; i<100; i++)
  {
    Operation1();
    x+=i;
    Operation2();
  }
}

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

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

(*) Если язык обещает, что обо всех переполнениях будет сообщено, то выражение, подобное, x*y/yнельзя упростить до тех xпор, пока x*yне будет гарантировано, что оно не будет переполнено. Аналогично, даже если результат вычисления будет проигнорирован, язык, который обещает сообщить обо всех переполнениях, должен будет выполнить его так или иначе, чтобы он мог выполнить проверку переполнения. Поскольку переполнение в таких случаях не может привести к арифметически некорректному поведению, программе не нужно будет выполнять такие проверки, чтобы гарантировать, что никакие переполнения не привели к потенциально неточным результатам.

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

#include <stdint.h>
uint32_t test(uint16_t x, uint16_t y) { return x*y & 65535u; }
uint32_t test2(uint16_t q, int *p)
{
  uint32_t total=0;
  q|=32768;
  for (int i = 32768; i<=q; i++)
  {
    total+=test(i,65535);
    *p+=1;
  }
  return total;
}

GCC сгенерирует код для test2, который безоговорочно увеличивает (* p) один раз и возвращает 32768 независимо от значения, переданного в q. По своим соображениям, вычисление (32769 * 65535) и 65535u вызовет переполнение, и, таким образом, нет необходимости для компилятора рассматривать любые случаи, когда (q | 32768) будет давать значение, превышающее 32768. Даже если нет Поскольку вычисления (32769 * 65535) и 65535u должны учитывать верхние биты результата, gcc будет использовать переполнение со знаком в качестве оправдания для игнорирования цикла.

Supercat
источник
2
«это модно для современных компиляторов ...» - аналогично, разработчикам некоторых известных ядер было недолго модно выбирать не читать документацию относительно используемых ими флагов оптимизации, а затем рассердиться по всему интернету. потому что они были вынуждены добавить еще больше флагов компилятора, чтобы получить поведение, которое они хотели ;-). В этом случае -fwrapvприводит к определенному поведению, хотя и не к поведению, которое хочет спрашивающий. Конечно, оптимизация gcc превращает любой вид разработки на C в тщательный анализ стандартов и поведения компилятора.
Стив Джессоп
1
@SteveJessop: C был бы гораздо более здоровым языком, если бы авторы компиляторов распознавали диалект низкого уровня, где «неопределенное поведение» означало «делать все, что имело бы смысл на базовой платформе», а затем добавляли способы для программистов отказаться от лишних гарантий, подразумеваемых этим, вместо того, чтобы предполагать, что фраза «непереносимая или ошибочная» в Стандарте просто означает «ошибочная». Во многих случаях оптимальный код, который можно получить на языке со слабыми поведенческими гарантиями, будет намного лучше, чем можно получить с более сильными гарантиями или без гарантий. Например ...
суперкат
1
... если программист должен оценить x+y > zтаким образом, чтобы он никогда не делал ничего, кроме yield 0 или yield 1, но любой результат был бы одинаково приемлемым в случае переполнения, компилятор, который предлагает такую ​​гарантию, часто мог бы генерировать лучший код для Выражение, x+y > zчем любой компилятор сможет генерировать для оборонительно написанной версии выражения. Реально говоря, какую долю полезных оптимизаций, связанных с переполнением, можно исключить гарантией того, что целочисленные вычисления, кроме деления / остатка, будут выполняться без побочных эффектов?
суперкат
Признаюсь, я не полностью разбираюсь в деталях, но тот факт, что ваше недовольство в целом связано с «авторами компиляторов», а не конкретно с «кем-то на gcc, который не примет мой -fwhatever-makes-senseпатч», настоятельно рекомендует мне, чтобы было больше к этому, чем прихоть с их стороны. Обычные аргументы, которые я слышал, это то, что встраивание кода (и даже расширение макроса) выигрывает от максимально возможного вывода о конкретном использовании конструкции кода, поскольку любая вещь обычно приводит к вставленному коду, который обрабатывает случаи, в которых он не нуждается к тому, что окружающий код «доказывает» невозможность.
Стив Джессоп
Так что для упрощенного примера, если я напишу foo(i + INT_MAX + 1), авторы компилятора стремятся применить оптимизацию к встроенному foo()коду, который полагается на правильность его аргумента, являющегося неотрицательным (возможно, извращенные трюки с divmod). В соответствии с вашими дополнительными ограничениями они могут применять только те оптимизации, поведение которых для отрицательных входных данных имеет смысл для платформы. Конечно, лично я был бы рад, если бы этот -fпараметр включался и -fwrapvт. Д., И, вероятно, должен был отключить некоторые оптимизации, для которых нет флажка. Но это не значит, что я могу заниматься этой работой сам.
Стив Джессоп
9

Не все языки программирования игнорируют целочисленные переполнения. Некоторые языки предоставляют безопасные целочисленные операции для всех чисел (большинство диалектов Lisp, Ruby, Smalltalk, ...) и другие через библиотеки - например, существуют различные классы BigInt для C ++.

То, делает ли язык целочисленное значение безопасным от переполнения по умолчанию или нет, зависит от его назначения: системные языки, такие как C и C ++, должны обеспечивать абстракции с нулевой стоимостью, и «большое целое число» не одно. Языки производительности, такие как Ruby, могут и действительно предоставляют большие целые числа из коробки. Такие языки, как Java и C #, находящиеся где-то посередине, должны ИМХО идти с целыми целыми числами из коробки, поскольку они этого не делают.

Неманья Трифунович
источник
Обратите внимание, что существует разница между обнаружением переполнения (а затем сигнала, паники, исключения, ...) и переключением на большие числа. Первое должно быть выполнимо намного дешевле, чем второе.
Матье М.
@MatthieuM. Абсолютно - и я понимаю, что мне не ясно об этом в моем ответе.
Неманя Трифунович
7

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

Если бы вы представили новый язык, который во многих аспектах похож на C #, но в 3 раза медленнее, получить долю на рынке было бы нелегко, даже если в конечном итоге большинство ваших конечных пользователей получат больше преимуществ от проверок переполнения, чем они. от более высокой производительности.

Дмитрий Григорьев
источник
10
Это особенно относится к C #, который на ранних этапах сравнивался с Java и C ++, а не с показателями производительности труда разработчиков, которые трудно измерить, или с показателями «деньги, спасенные от нарушений безопасности», которые трудно измерить, но на тривиальных показателях производительности.
Эрик Липперт
1
И, вероятно, производительность процессора проверяется с помощью простого вычисления чисел. Таким образом, оптимизация для обнаружения переполнения может дать «плохие» результаты в этих тестах. Словить 22.
Бернхард Хиллер
5

Помимо множества ответов, которые оправдывают отсутствие проверки переполнения на основе производительности, существует два различных вида арифметики:

  1. расчеты индексации (индексация массива и / или арифметика указателей)

  2. другая арифметика

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

Таким образом, проверки распределения памяти достаточно при работе с арифметикой указателей и индексированием выражений, включающих выделенные структуры данных. Например, если у вас есть 32-разрядное адресное пространство, и вы используете 32-разрядные целые числа и допускаете выделение максимум 2 ГБ кучи (около половины адресного пространства), вычисления индексации / указателя (в основном) не будут переполнены.

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

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

В последнем случае программисты часто используют альтернативные типы данных, такие как doubleили некоторые BigInt. Многие расчеты требуют decimalтипа данных, а не double, например, финансовых расчетов. Если они этого не делают и придерживаются целочисленных типов, то им нужно позаботиться о проверке переполнения целых чисел - иначе, да, программа может достичь необнаруженного состояния ошибки, как вы указываете.

Как программисты, мы должны быть чувствительны к нашему выбору числовых типов данных и их последствиям с точки зрения возможностей переполнения, не говоря уже о точности. В целом (и особенно при работе с языками семейства C с желанием использовать быстрые целочисленные типы) мы должны быть чувствительны и понимать различия между индексными вычислениями и другими.

Эрик Эйдт
источник
3

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

Поскольку устранение переполнения иногда является желаемым поведением, существуют также версии операторов, которые никогда не проверяют переполнение.

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

Hjulle
источник
2
Rust также предоставляет такие методы, как checked_mul, который проверяет, произошло ли переполнение, и возвращает, Noneесли так, в Someпротивном случае. Это можно использовать как в производственном, так и в режиме отладки: doc.rust-lang.org/std/primitive.i32.html#examples-15
Akavall,
3

В Swift любые целочисленные переполнения обнаруживаются по умолчанию и мгновенно останавливают программу. В случаях, когда вам нужно поведение с циклическим изменением, есть разные операторы & +, & - и & *, которые достигают этого. И есть функции, которые выполняют операцию и сообщают, было ли переполнение или нет.

Интересно наблюдать, как новички пытаются оценить последовательность Коллатца и у них происходит сбой кода :-)

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

PS. В C, C ++ целочисленное арифметическое переполнение со знаком Objective-C является неопределенным поведением. Это означает, что все, что делает компилятор в случае целочисленного переполнения со знаком, является правильным по определению. Типичные способы справиться с целочисленным переполнением со знаком - это игнорировать его, принимая любой результат, который дает вам процессор, встроив в компилятор допущения, что такого переполнения никогда не произойдет (и заключите, например, что n + 1> n всегда истинно, поскольку переполнение является предполагается, что это никогда не произойдет), и возможность, которая редко используется, заключается в проверке и сбое в случае переполнения, как это делает Swift.

gnasher729
источник
1
Я иногда задавался вопросом, пытались ли люди, которые толкают UB-управляемое безумие в C, тайно пытаться подорвать его в пользу какого-то другого языка. Это имело бы смысл.
суперкат
Лечение , x+1>xкак безусловно то не потребуется компилятор делать какие - либо предположения «» о х , если компилятор имеет право оценивать целые выражения с использованием произвольных больших типов , как удобно (или вести себя так , как будто он делает это). Более неприятным примером основанных на переполнении «допущений» было бы решение о том, что данный uint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; }компилятор может использовать sum += mul(65535, x)для принятия решения, которое xне может быть больше 32768 [поведение, которое, вероятно, шокирует людей, написавших Обоснование C89, что предполагает один из решающих факторов. ..
суперкат
... в unsigned shortпродвижении signed intбыл тот факт, что две реализации дополнения без вывода сообщений (т.е. большинство используемых тогда реализаций C) будут обрабатывать код, подобный приведенному выше, одинаково, независимо от того, unsigned shortповышен ли он до intили unsigned. Стандарт не требовал реализации на оборудовании с дополнительным дополнением без вывода сообщений для обработки кода, подобного приведенному выше, но авторы стандарта, похоже, ожидали, что они все равно это сделают.
суперкат
2

На самом деле, настоящая причина этого чисто техническая / историческая: по большей части знак игнорирования ЦП . Обычно есть только одна инструкция для добавления двух целых чисел в регистры, и ЦПУ не имеет значения, интерпретируете ли вы эти два целых числа как подписанные или без знака. То же самое касается вычитания и даже умножения. Единственная арифметическая операция, в которой необходимо учитывать знаки, - это деление.

Причиной, по которой это работает, является представление дополнения 2 со знаком целых чисел, которое используется практически всеми процессорами. Например, в 4-битном дополнении 2 добавление 5 и -3 выглядит так:

  0101   (5)
  1101   (-3)
(11010)  (carry)
  ----
  0010   (2)

Понаблюдайте, как циклическое поведение отбрасывания выносного бита дает правильный подписанный результат. Аналогично, процессоры обычно реализуют вычитание x - yкак x + ~y + 1:

  0101   (5)
  1100   (~3, binary negation!)
(11011)  (carry, we carry in a 1 bit!)
  ----
  0010   (2)

Это реализует вычитание как дополнение в аппаратном обеспечении, настраивая только входы в арифметико-логическую единицу (АЛУ) тривиальными способами. Что может быть проще?

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

Очевидно, что так как C был разработан для работы близко к металлу, он принял то же самое поведение, что и стандартизированное поведение арифметики без знака, позволяя только арифметике со знаком давать неопределенное поведение. И этот выбор перенесен на другие языки, такие как Java, и, очевидно, C #.

cmaster
источник
Я пришел сюда, чтобы дать этот ответ, а также.
Мистер Листер
К сожалению, некоторые люди считают крайне необоснованным представление о том, что люди, пишущие низкоуровневый код C на платформе, должны иметь смелость ожидать, что компилятор C, подходящий для таких целей, будет вести себя ограниченным образом в случае переполнения. Лично я считаю разумным, чтобы компилятор вел себя так, как если бы вычисления выполнялись с произвольно расширенной точностью для удобства компилятора (например, в 32-битной системе, если x==INT_MAX, тогда x+1может произвольно вести себя как +2147483648 или -2147483648 в компиляторе удобство), но ...
суперкат
некоторые люди думают, что если xи yесть, uint16_tи код в 32-битной системе вычисляется, x*y & 65535uкогда значение yравно 65535, компилятор должен предполагать, что код никогда не будет достигнут, когда xзначение больше 32768.
суперкат
1

В некоторых ответах обсуждалась стоимость проверки, и вы отредактировали свой ответ, чтобы оспорить, что это разумное обоснование. Я постараюсь рассмотреть эти вопросы.

В C и C ++ (в качестве примеров) одним из принципов проектирования языков не является предоставление функциональности, которая не запрашивалась. Обычно это выражается фразой «не платите за то, что вы не используете». Если программист хочет проверить переполнение, он может попросить об этом (и заплатить штраф). Это делает язык более опасным для использования, но вы решаете работать с языком, зная это, поэтому вы принимаете на себя риск. Если вам не нужен этот риск или вы пишете код, в котором безопасность имеет первостепенное значение, вы можете выбрать более подходящий язык, где компромисс между производительностью и риском отличается.

Но с 10 000 000 000 повторений время, затрачиваемое на проверку, все равно составляет менее 1 наносекунды.

В этом рассуждении есть несколько ошибок:

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

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

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

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

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

Джон Бентли
источник
-1

Есть хорошие ответы, но я думаю, что здесь есть упущенный момент: эффекты целочисленного переполнения не обязательно являются плохой вещью, и после этого трудно понять, произошло ли iиз-за того, MAX_INTчто MIN_INTбыло, быть из-за проблемы переполнения или если это было сделано намеренно путем умножения на -1.

Например, если я хочу сложить все представимые целые числа больше 0, я бы просто использовал for(i=0;i>=0;++i){...}цикл сложения - и при переполнении он останавливает сложение, что является целевым поведением (выбрасывание ошибки означало бы, что мне нужно обойти произвольная защита, потому что она мешает стандартной арифметике). Это плохая практика ограничивать примитивную арифметику, потому что:

  • Они используются во всем - замедление в примитивной математике - замедление в каждой работающей программе
  • Если они нужны программисту, они всегда могут их добавить
  • Если они у вас есть, а программисту они не нужны (но им нужны более быстрые среды выполнения), они не смогут легко их удалить для оптимизации
  • Если они у вас есть и программисту нужно, чтобы их там не было (как в приведенном выше примере), программист одновременно принимает удар во время выполнения (что может или не может иметь значение), и программист все равно должен потратить время на удаление или работать вокруг «защиты».
Delioth
источник
3
На самом деле программист не может добавить эффективную проверку переполнения, если язык этого не предусматривает. Если функция вычисляет значение, которое игнорируется, компилятор может оптимизировать вычисления. Если функция вычисляет значение, которое проверяется на переполнение, но в противном случае игнорируется, компилятор должен выполнить вычисление и перехватить его, если оно переполнится, даже если переполнение в противном случае не повлияет на вывод программы и может быть безопасно проигнорировано.
суперкат
1
Вы не можете перейти от INT_MAXк INT_MINумножением на -1.
Дэвид Конрад
Очевидно, что решение состоит в том, чтобы предоставить программисту возможность отключить проверки в данном блоке кода или модуле компиляции.
Дэвид Конрад
for(i=0;i>=0;++i){...}это стиль кода, который я стараюсь не поощрять в своей команде: он опирается на специальные эффекты / побочные эффекты и не дает четкого выражения того, что он должен делать. Но все же я ценю ваш ответ, поскольку он показывает другую парадигму программирования.
Бернхард Хиллер
1
@Delioth: Если iэто 64-битный тип, даже в реализации с согласованным поведением «молчание-обертка-два», выполняющей миллиард итераций в секунду, такой цикл может быть гарантированно найдет наибольшее intзначение, только если ему разрешено работать для сотни лет. В системах, которые не обещают согласованного поведения в режиме без вывода сообщений, такое поведение не гарантируется, независимо от длины кода.
суперкат