польза неопределенности (англ.)

[avva]

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

Интересная запись в блоге проекта LLVM о том, почему неопределенное поведение в стандарте C - полезная штука. Я знал эти аргументы теоретически (что неопределенное поведение позволяет компилятору более агрессивно оптимизировать код), но о подробных примерах никогда не задумывался:

Например:

• если i - целая переменная с знаком, то компилятор может считать "i+1 > i" (или более сложное выражение, которое сводится к этому) автоматически истинным, несмотря на то, что для i==INT_MAX переполнение может сделать i+1 отрицательным. Если бы стандарт обязывал имплементацию C строго соблюдать "очевидную" логику переполнения, как это делает, например, Джава, то компилятор не смог бы почти никогда сделать эту оптимизацию.
  
  Подчеркну: дело тут не только в том, что стандарты C не обязывают имплементацию использовать 'дополнительный код' (two's complement) для представления отрицательных целых чисел. Даже если все имплементации используют это представление - что де-факто верно в современном мире - и даже если бы по другим причинам это представление было бы обязательным согласно стандарту, все равно может быть полезным оставить результат INT_MAX+1 неопределенным, а не "очевидным" - в точности по причине, объясненной в предыдущем абзаце. Эту довольно тонкую идею я недостаточно хорошо понимал, кажется.
  
  
• Последствия обращения к NULL-указателю не определены. В Джаве такое обращение гарантированно кидает исключение, и в этом несомненно есть много своих преимуществ; но как следствие этого, компилятор не может менять порядок вычисления других выражений относительно обращения к указателю. Например, если на Джаве написано что-то вроде: "c = a.b; c+= 5;", то компилятор не может сгенерировать код, который сначала поместит в c 5, а потом добавит содержимое a.b. Потому что если a==NULL, то исключение должно произойти до того, как в c что-то помещено. А C/C++ таких гарантий не дает, поведение неопределенное, поэтому компилятор может изменить порядок вычисления. В данном дурацком примере это ничему не поможет, но бывают случаи, когда это может сильно ускорить вычисление.
  

Ну и еще в записи по ссылке есть несколько примеров такого рода.

Update: исходную запись почему-то удалили; я пока заменил своей копией.

Comments

[javax-slr.livejournal.com]

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

[msh.livejournal.com]

.. а также вспомним использование неопределенного поведения memcpy при оптимизации для новых процессоров Intel :-)

[avva.livejournal.com]

Это библиотека, а не язык, но I take your point :)

[(Anonymous)]

Language design is library design. — Bjarne Stroustrup
Library design is language design. — Andrew Koenig

[gdy.livejournal.com]

Вам не хочется несколько раз подумать, как вы относитесь к UB, чтобы понять, хотели ли бы вы работать над одним проектом (http://avva.livejournal.com/2323823.html) с таким человеком как вы? )

[iratus.livejournal.com]

Я не понимаю, разве в джаве есть pointer arithmetic, что ее там надо как-то оптимизировать?

[avva.livejournal.com]

речь идет об оптимизации обычной арифметики, в которой используются значения из объектов. См. пример в записи.

[iratus.livejournal.com]

А, понял, сорри.

[spamsink.livejournal.com]

Хардверщикам это хорошо известно: если при каких-то условиях результат "don't care", то схему можно соптимизировать лучше, например,
A ? B : C ? D : 0 = A ? B : CD = AB|(~A)CD, а (X = don't care)
A ? B : C ? D : X = A ? B : D = AB|(~A)D

[hotgiraffe.livejournal.com]

ну в Яве тоже не всё так очевидно
если c - локальная переменная с областью действия меньше ближайшего try/catch - то видимо можно

а вообще больше всего мне конечно понравилось у Регера про баскетбол

[zigmar.livejournal.com]

Я где-то читал, что в Фортране определенные вычислительные задачи работают быстрее их аналогов в С/С++ - это из за отсутствия алиасинга, что позволяет компилятору оптимизировать гораздо агрессивнее.

[ygam.livejournal.com]

Фрэнсис Аллен жаловалась на то, что переход от Фортрана к Си убил множество оптимизаций - например, замену массива из структур на структуру из массивов.

интересно

[secondary-tea.livejournal.com]

не подскажете, где?

Re: интересно

[ygam.livejournal.com]

Кажется, в книжке Masterminds of Programming.

Re: интересно

[secondary-tea.livejournal.com]

Masterminds of Programming
Edited by Federico Biancuzzi and Shane Warden -- слово фортран не встречается ни разу...

Re: интересно

[ygam.livejournal.com]

Я ошибся: это была книжка Coders at Work.

Re: интересно

[secondary-tea.livejournal.com]

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

[lazyreader.livejournal.com]

Разве не очевидно, что, когда результат может быть любым, добиваться его легче? "Куда мне отсюда идти? -- А куда ты хочешь попасть? -- Мне всё равно. -- Тогда всё равно, куда идти."

В общем, необходимость объявленной неопределённости поведения - всё ещё сомнительная вещь для меня.

[(Anonymous)]

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

[http://users.livejournal.com/_navi_/]

Есть ещё очень хороший A Guide to Undefined Behavior in C and C++ (http://blog.regehr.org/archives/213) в трёх частях.

[codedot.livejournal.com]

Есть русский термин для «2's complement» — «двоичное дополнение».

[kmmbvnr.livejournal.com]

Не хватает теперь статистики, на сколько эти undefined оптимизации помогают на реальном а не игрушечном коде.

p.s. А пост уже удалили

[(Anonymous)]

Ну вот взять джаву, например. В джаве нет UB. Есть еще отличия от C++, разумеется, но они не такие уж и радикальные (сборку мусор, например, можно присобачить и в C++, без особого ущерба для производительности).

Ни одна из ссылок не работает

[kyukhin.livejournal.com]

Причем полчаса назад работало

[nbuwe.livejournal.com]

Удалили, видимо, из-за того, что даже для популярного текста она написана уж слишком sloppy...

It is worth noting that unsigned overflow is guaranteed to be defined as 2's complement (wrapping) overflow.

О каком 2's complement для unsigned может идти речь? Стандарт там очень аккуратно всё проговаривает. Более того, в нескольких местах явно говориться, что с unsigned по определению не бывает overflow.

Dereferences of Wild Pointers ...

Что такое "wild" pointer?

dereferencing a null pointer in C is undefined ...and if you mmap a page at 0...

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

This falls out of the rules that forbid dereferencing wild pointers...

Нет такого правила; стандарт-то как раз и говорит, что if an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined.

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

[helvegr.livejournal.com]

> Что такое "wild" pointer?

Там же пояснено: random pointers (like NULL, pointers to free'd memory, etc).

> О каком 2's complement для unsigned может идти речь?

Имеется в виду, что поведение при переполнении аналогично. INT_MAX + 1 == INT_MIN. UINT_MAX + 1 == 0.

[nbuwe.livejournal.com]

Ну нельзя говорить о стандарте, особенно о такой теме, как undefined behaviour, и быть настолько неаккуратным.

Зачем для красного словца изобретать "wild" и "объяснять" его через "random", когда стандарт написан в терминах valid/invalid?

Про доступ за границы массива - вообще какая-то каша ни о чем. Стандарт, кстати, вполне определяет осмысленные случаи доступа, которые будут "за границы" массива (см. напр. 6.5.9/6 про равенство указателя "за" последний элемент и указателя на первый элемент массива, который в памяти лежит непосредственно за первым массивом). Массивы и арифметика указателей в C и так одно из неочевидных мест, зачем еще больше путать людей?

Говорить о двоичном дополнительном представлении (отрицательных чисел!) в применении к беззнаковым(!) типам - это не просто неаккуратно, а очень неаккуратно. А уж фраза про то, что такое поведение беззнаковых определено "at least by Clang and other commonly available C compilers" - это уже просто за гранью добра из зла.

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

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

[avva.livejournal.com]

Я согласен с вами в том, что написано несколько неряшливо, но мне это не кажется столь большим недостатком, как вам. Основная мысль о том, почему undefined behavior может быть полезным, выражена хорошо, а недочеты, связанные с неточным использованием терминов стандарта или придумыванием своих, вряд ли кого-то сильно запутают. Согласен, что стоило упомянуть про NULL, необязательно побитово равный нулю, об этом мало кто знает; добавлю, что объясняя это, надо еще объяснить, что сравнивать указатель с нулем все равно можно и корректно.

Кстати, спасибо за подробные и информативные комментарии о языковых стандартах, выдержанные в корректном тоне; часто приходится видеть другое :-)

[nbuwe.livejournal.com]

Я просто высказал догадку, что статью убрали из-за того, что для официального блога LLVМ такой уровень неряшливости все-таки не комильфо. :)

Мой скромный опыт толкования стандарта подсказывает, что если с терминологией быть поаккуратней, то обсуждение многих вопросов достигает каких-то положительных результатов гораздо быстрее. На самом деле можно (и было бы очень поучительно) много написать о том, как устроен язык стандарта, и как они там ловко выворачиваются, чтобы с одной стороны продолжать поддерживать (почти) все эти нижнеуровневые хаки а-ля ассемблер PDP-11, а с другой стороны поддерживать и совсем уж странные архитектуры.

Сравнивать с литералом 0 можно, но создает плохую привычку. В контексте varargs (например execl) приведение типов уже не спасет. Кажется именно с этим я в свое время сталкивался, собирая разный софт под Xenix/286 :)

Ну и раз уж зашла речь про unsigned - вот довольно милый, по-моему, пример на понимание этого места стандарта:

http://nxr.netbsd.org/xref/src/usr.bin/make/cond.c#487

Что делает -(double)-l_val и почему это не хак, а вполне defined поведение.

[avva.livejournal.com]

Действительно милый пример :)

[secondary-tea.livejournal.com]

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