Comments 102
Вот только "раньше работало же". Трюк-то популярный был...
Даже здесь в комментариях можно отследить, что такая подача информации формирует мнение о компиляторе что он «чудит». А компилятор работает в согласии со Стандартом, никаких чудес нет.
Любая эксплуатация UB кроме его ликвидации — это хорошая такая мегатонна, заложенная под проект.
Ну если компилятор это компилирует, да еще и делует это в согласии со Стандартом, то получается, что чудут стандарт.
Если честно, у меня в голове не укладывается, как мог родиться, а тем более стать настолько популярным, язык с UB. Ведь само существование UB — это хорошая такая мегатонна, заложенная под все проекты на этом языке.
А что, были какие‐либо другие альтернативы без UB, производительные и пригодные для написания кода для разных экзотических платформ с различными ограничениями? Тут всё просто: либо вы рисуете UB в стандарте, либо вы рисуете там «implementation‐defined», что не намного лучше: в случае с UB программист не знает, что там сделает компилятор, в случае с «implementation‐defined» программист не знает, что сделает компилятор на другой платформе, только, в отличие от оптимизаций на UB, это незнание вылезет только на той самой другой платформе. Либо вы рисуете в стандарте твёрдые гарантии определённого поведения и проседаете в производительности, иногда очень сильно.
https://habrahabr.ru/post/230777/
Гораздо логичнее в этом случае просто не компилироваться. Видишь UB — отказываешься компилироваться. И никаких подстав.
2. Не все случаи наличия UB можно логически доказать, имея только код программы.
3. Для выдачи предупреждений о возможном UB есть статические анализаторы, которые работают эвристически (делают вид, что они — ваш опытный коллега, который бедокод детектирует на уровне интуиции, потому как за свою карьеру видел километры мозговых извержений разной степени тяжести).
4. Принцип единой ответственности: задача компилятора — собрать программу, опираясь на стандарт языка; Искать потенциальные проблемы — не задача компилятора.
Поиск плохого кода — на статический анализатор. Поиск утечек памяти и прочего, что на статике не увидеть — на динамический анализатор.
С такой хотелкой, вам имеет смысл обратить более пристальное внимание на java. Там подход именно такой, что все должно быть 100% детерминированно, никаких UB не допускается.
В C++ переменная в принципе не может быть равна её значению, потому что в C++ вообще нельзя сравнивать переменные с чем бы то ни было, можно сравнивать только значения переменных. Но даже если взять язык, в котором можно (например, Common Lisp), то заголовок всё равно был бы не слишком осмысленным, т.к. переменная может быть равна своему значению только если значение этой переменной — сама эта переменная. Т.е., если выражаться терминами C++, если она — ссылка на саму себя, что в C++ сделать не позволит система типов.
На самом деле, все беды лечатся грамотным code review, который приведенный выше код не должен проходить.
А ещё все люди должны быть добрыми и помогать друг другу.
Будет куча false positive в кросс-платформенных библиотеках, где константные условия используются для выбора нужной реализации.
Не логично. Во‐первых, код с препроцессором может плохо выглядеть, в отличие от if (HAS_FEATURE) {}. Во‐вторых, иногда есть выбор между «использовать нельзя» (#define HAS_FEATURE 0), «использовать нужно, если включена настройка» (выбор поведения в runtime, #define HAS_FEATURE use_feature) и «использовать нужно всегда». Без использования «dead code elimination» (DCE) при постоянном условии такой тройной выбор будет выглядеть ужасно. В‐третьих, компилятор проводит некоторые проверки до оптимизаций, но исключённый препроцессором код не будет в них участвовать. А это удобно — узнавать, что вы написали «helpres» вместо «helpers» до того, как код дойдёт до CI.
В‐четвёртых, попробуйте засунуть #ifdef в функцию, которая сама определяется #define’ом. Если у вас есть «библиотека макросов», генерирующая вам функции, то исключать оттуда код можно только полагаясь на DCE. И нет, никаких шаблонов: я пишу на C. А оптимизации для C и C++ во многом пересекаются.
Я понимаю, что в стандарте UB, но кто оказался таким тупым, что не предусмотрел переполнения, и решил, что переменная только растет? То есть, половину дела он продумал, а половину нет?
На самом деле тут было вычисление по модулю 232. До того, как компиляторы "научились" использовать UB для оптимизации — для вычислений в кольце вычетов по такому модулю надо было всего лишь игнорировать переполнения.
Это идёт с больших и суперкомпьютеров, где одно время была мода в ряде семейств вообще не реализовывать отдельное целочисленное АЛУ, а использовать в качестве целых чисел ненормализованные вещественные, с мантиссой в прямом коде.
Ну да, платформо-зависимый код, и что? Это, кстати, совершенно нормально для такой области как хеш-функции.
Эти "специальные типы" нужны как раз для обеспечения платформо-независимости. Здесь же такая задача попросту не стояла, вот и все.
Если мне не изменяет память (а проверять лень), вопрос, растрогавший автора поста, исчерпывающе разобран в книге Меткалфа “Оптимизация в Фортране”, написанной ещё до рождения многих современных программистов.
Clang и GCC всё-таки стараются предупреждать об оптимизациях, использующих предположение об отсутствии UB.
Дело в том, что в традиционной схеме представления отрицательных чисел:
MAX_VALUE = (2^n) -1
MIN_VALUE = -(2^n)
Если их сложить, получим -1.
Так же, рекомендую заглянуть в мою заметку (post/278329/) и в каменты к ней. Там подняты некоторые близкие вопросы багов, связанных с переполнением.
Легко на x86, x86-64, arm5/7 размер int в gcc 4 байта.
От того, что MAX_INT заменят на INT_MAX из limits.h (или что там у вас в C++ вместо этого, вроде какая‐то std:: шняга специальная есть вида std::numeric_limits<int>::max()) смысл статьи не изменится. Но на месте автора я бы всё же заменил.
Отвечая на вопрос безотносительно статьи: запросто. NaN не равно самому себе.
std::vector<int> vec;
vec.reserve(1024);
for ( int i = 0; i < 600; i++ ){
vec.push_back(i * i);
}
Для каких-то частных случаев сообщение может и выдается, но в общем случае оно будет бесполезным с кучей false positives.
Информировать о таких вещах — задача все же для статического анализатора, там и работа идет с представлением гораздо ближе к исходному коду, и есть более внятный контроль за ложноположительными срабатываниями.
Просто конкретно в этом моменте косяк хорошо видно, но зная злостный оптимизатор С++ считаю, что выдавать warning/hint в таких случаях жизненно необходимо.
Язык — нет, но платформа — да. На С++ иногда платформо-зависимый код пишут, и это нормально.
А int — он что — платформо‐независимый?
А в данном случае надо использовать что-нибудь из серии uint32_t.
И как это поможет? В момент приведения его к int (или int32_t) для борьбы с переполнением оптимизатор опять посчитает, что можно выкинуть мертвый код.
@vadimr предложил uint32_t, а не int/int32_t. Никакого UB при переполнении здесь не будет. Даже если потом приводить результат к int (зачем?) и сравнивать с нулём, по стандарту это implementation‐defined, а не undefined behaviour и сравнение с нулём при приведении 32‐битного беззнакового целого к 32‐битному знаковому не выкинут (вот в случае uint16_t→int32_t выкинули бы, только не думаю, что кто‐то здесь будет считать, что это недопустимо).
Что здесь со ссылками на пользователей, на vadimr она то формируется, то нет?
Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения, значения для неопределенности, и переполнений.
Открываем стандарт ISO C, смотрим, мотаем на ус…
H.2.2 Integer types
1 The signed C integer types int, long int, long long int, and the corresponding
unsigned types are compatible with LIA−1. If an implementation adds support for the
LIA−1 exceptional values ‘‘integer_overflow’’ and ‘‘undefined’’, then those types are
LIA−1 conformant types. C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense
in that overflows or out-of-bounds results silently wrap. An implementation that defines
signed integer types as also being modulo need
6.2.6.2 Integer types
1 For unsigned integer types other than unsigned char, the bits of the object
representation shall be divided into two groups: value bits and padding bits (there need
not be any of the latter). If there are N value bits, each bit shall represent a different
power of 2 between 1 and 2N−1, so that objects of that type shall be capable of
representing values from 0 to 2N − 1 using a pure binary representation; this shall be
known as the value representation. The values of any padding bits are unspecified.53)
2 For signed integer types, the bits of the object representation shall be divided into three
groups: value bits, padding bits, and the sign bit. There need not be any padding bits;
signed char shall not have any padding bits. There shall be exactly one sign bit.
Each bit that is a value bit shall have the same value as the same bit in the object
representation of the corresponding unsigned type (if there are M value bits in the signed
type and N in the unsigned type, then M ≤ N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, the value shall be modified in one of the
following ways:
— the corresponding value with sign bit 0 is negated (sign and magnitude);
— the sign bit has the value −(2M) (two’s complement);
— the sign bit has the value −(2M − 1) (ones’ complement).
Which of these applies is implementation-defined, as is whether the value with sign bit 1
and all value bits zero (for the first two), or with sign bit and all value bits 1 (for ones’
complement), is a trap representation or a normal value. In the case of sign and
magnitude and ones’ complement, if this representation is a normal value it is called a
negative zero.
Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения
В дополнительном коде не бывает знака у нулевого значения
Тут речь шла о том, что нету разницы между int32_t etc и int кроме размера контейнера.
Поскольку первые ревизии стандартов IEEE Std 1003.1 включали частично стандарты ANSI C, которые давно устарели.
В данный момент все IEEE Std 1003.xx устарели и нужно использовать ISO/IEC/IEEE 9945:2009/Cor 1:2013
-fno-strict-overflow для GCC выключает эту херню в оптимизаторе
Тем не менее, идея отключить UB при целочисленном знаковом переполнении в одном из модулей (не во всех!), где собраны функции, производящие вычисления в кольце вычетов по модулю 2^32 или 2:64 — довольно здравая.
Иногда знаковый тип требуется на выходе… и не всегда отрицательное значение является ошибкой. Приведение же к типу int с переполнением также даст UB, ЕМНИП.
1. Начнем с того что x[i] это char, а он уже знаковый тип.
2. Далее для в исходном коде константа 27752 а не 27753 как в дизассемблированом. Оба числа не простые, а ближайшее простое 27751.
3. Первый цикл несет абсолютно бессмысленную с точки зрения хэширования операцию 13*27752+x[i] видимо ее добавили для компенсации переполнения на второй итерации.
4. Размер константы 27752 или 27753 на 7 бит больше чем нужно для хэширования, что ведет к большому числу лишних коллизий.
Чтобы работало, как «Должно» нужно привести x[i] к целочисленному типу, далее умножать на максимальное простое число для представления которого достаточно unsigned char или на бит больше (253 или 257 в зависимости от окраски входных данных), для h нужно применить целочисленный тип, которого гарантировано достаточно для хранения результата без переполнения, h нужно инициализировать 0. Потом можно взять результат по модулю 2N где N необходимый порядок выходных слотов или по модулю ближайшего простого числа соответствующему числу выходных слотов хэш функции. Иначе будут лишние неравномерные коллизии.
Еще лучше, конечно, применить стандартные HASH функции выведенные лучшими собаководами.
Если брать результат по модулю 2N — то переполнение при вычислении h допустимо.
По стандарту char не знаковый, а implementation‐defined. Символы из “basic execution character set” гарантированно неотрицательны (C99, в стандарте C++11 я такого заявления не нашёл). Однозначно знаковым является signed char, однозначно беззнаковым unsigned char, а сам char вообще не принадлежит ни одному из классов целочисленных типов, описанных в документации.
Скажите это разработчикам glibc или gnump, всяких кодеков, например. Да на самом деле дофига реально существующих библиотек использует хоть где-то в коде подобные уловки.
Нужно использовать без знаковый тип это раз.
Кроме того затычка с проверкой знака, будучи не выкинутой компилятором, увеличивает число коллизий данного хэша в два раза для определенного множества входных строк (или окрашивает спектр для любого множества случайных входных значений, кому так понятнее).
Можно не цепляться за этот конкретный код, так как он всего лишь демонстрирует общую проблему с default установками оптимизации в последних версиях GCC. Эта оптимизация вступает в противоречие с приемами, которые по сути являются общей практикой для многих библиотек, где много работы с числами (например, вычисления с числами высокой разрядности, криптография, кодеки). Эта оптимизация помогает в редких случаях, но может испортить работу древнего хардкорного кода, который создавали, отлаживали и оптимизировали годами. Не понимаю, нафига они врубили ее именно по умолчанию.
Посыл про то, что эта оптимизация не нужна тоже мягко говоря странный.
Если программист собирает свои программы с опциями оптимизации, то он должен понимать, что делает и стоит посмотреть, что они подразумевают.
Если он использует новую версию компилятора, то заглянуть в changelog тоже стоит.
Мне вот например не понятно почему для gcc не включена по умолчанию -Wconversion -Wbad-function-cast -Wcast-qual
P.S.: Исходя из названия, кстати, ожидал увидеть что-нибудь про адреса объектов при множественном наследовании (вроде этого).
del
if (h < 0) h += MAX_INT;
на
if (h < 0) h ^= 0x80000000;
т.е. смена старшего разряда (там знак) с 1 на 0. Так число гарантированно станет положительным. Можно использовать маску 0xFFFFFFFF, это будет равносильно h = -h-1
И раз уж вы используете C++, то используйте std::numeric_limits.
Иначе ваши возмущения по поводу того, что в разных местах у вас работает по-разному выдает в вас новичка.
В ассемблерном коде выполняется честная, хотя и магическая проверка
sar eax, 31 # some magic check
and eax, dword ptr [rip + _MAX_INT] # yet another magic
add eax, edx
Эх молодежь…
Вобщем-то простейшая оптимизация.
Как это работает:
команда «sar» это арифметический сдвиг вправо (Shift ArithmeticRight).
При сдвиге регистра вправо нужно придумать что положить в самый старший бит (влево тоже, но сейчас не об этом).
Есть несколько стандартных вариантов (класть 0, размножать старший бит, класть то что было в младшем и т.п.). В данном случае делается размножение старшего бита, напирмер (сократим до 8 бит для наглядности):
10001100 -> sar r,1 -> 11000110
00001100 -> sar r,1 -> 00000110
такой сдвиг сохраняет знак числа и примерно соответствует операции деления целого числа на 2 (поэтому он и называется арифметическим).
Особо интересными случаями являются применение этой операции к единице и минус единице:
1 (00000001) -> sar r,1 -> 0 (00000000)
-1 (11111111) -> sar r,1 -> -1 (11111111)
т.е. если применить эту опреацию много-много раз к положительному числу, мы получим 0, а если к отрицательному то -1 (11111111).
Собственно это здесь и делается: в результате арифметического сдвига вправо на 32 бита в eax будет 0, если исодное значение было положительным, или 0xffffff если отрицательным.
Соответственно вторая строчка — операция and с константой MAX_INT. т.к. в eax у нас возможны только 0 и 0xffffffff, результатом этого and будет либо 0, либо MAX_INT (в зависимости от знака исходного значения).
Ну и последней строчкой добавляем это значение к результату функции.
В терминах C это можно переписать так:
h += h>=0 ? MAX_INT : 0;
Зачем это надо:
Современные процессоры очень не любят команды условных переходов. Такая оптимизация позволяет сделать эквивалентный код без переходов.
Собственно это здесь и делается: в результате арифметического сдвига вправо на 32 бита в eax будет 0, если исодное значение было положительным, или 0xffffff если отрицательным.
Поправка: сдвиг на 31 бит, а не на 32. Сдвиг на 32 бита не изменит число, потому что используются только младшие 5 бит операнда.
Как переменная может быть не равной её собственному значению