unsigned MAX_INT = 2147483647;
int hash_code(std::string x) {
int h = 13;
for (unsigned i = 0; i < 3; i++) {
h += h * 27752 + x[i];
}
if (h < 0) h += MAX_INT;
return h;
}На некоторых строках, в частности, на строке «bye», и только на сервере (что интересно, на своем компьютере все было в порядке) функция возвращала отрицательное число. Но как же так, ведь в случае, если число отрицательное, к нему прибавится MAX_INT и оно должно стать положительным.
Тут стоит посмотреть на различия сервера и локального компьютера: во-первых на локальном компьютере стояла OS X и использовался компилятор clang, тогда как на сервере стояла Gentoo с компилятором gcc, и во-вторых на сервере компиляция происходила с флагом -O2. Что же, давайте скомпилируем командой
g++ -O2 -S -masm=intel a.cppна стороне сервера и посмотрим ассемблерный код этой функции.
_Z9hash_codeNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE:
.LFB661:
.cfi_startproc
mov rdx, QWORD PTR [rdi]
mov eax, 13
lea rsi, [rdx+3]
.L2: # begin of the cycle
movsx ecx, BYTE PTR [rdx]
add rdx, 1
imul eax, eax, 27753
add eax, ecx
cmp rsi, rdx
jne .L2 # end of the cycle
rep ret # returning the value right awayКак можно увидеть, никакого сравнения в ассемблерном коде после цикла нет. Получается, компилятор решил, что переменная, хранящая неотрицательное значение и которую только увеличивают, стать меньше нуля не может, и это правильно с точки зрения целочисленной арифметики, которую и реализует int. А это значит, что сравнение с нулём не нужно, и можно выполнить dead code elimination (удаление мертвого кода). Нас предупреждали, что переполнение int'а вызывает undefined behaviour.
А что если вывести, равна ли переменная её собственному значению?
printf("%i\n", h == -348700627);На выводе мы получим 0, а в ассемблерном коде будет:
xor edx, edx
mov esi, OFFSET FLAT:.LC0
mov edi, 1
xor eax, eax
call __printf_chkгде в регистре edx передается аргумент на вывод. Он равен нулю, никаких проверок не производится. Вообще логично, если число не меньше нуля, зачем сравнивать его с отрицательным. Таким образом, получается, что при переполнении могут не работать функции сравнения целых чисел, а переменная может быть не равной собственному значению! Но на то оно и undefined behaviour.
Давайте попробуем сравнить переменную с положительным числом. Конечно результат будет false, но интересно, будет ли компилятор делать реальную проверку? С помощью двоичного поиска было найдено, что компилятор делает реальную проверку только когда выполняется сравнение с числом 360662 и больше. Это число очень близко к 27752 * 13. Совпадение или нет? Не знаю.
Стоит еще сказать, что на OS X с оптимизацией -O2 таких ошибок не было замечено. Правда теперь использовался clang, а не gcc. В ассемблерном коде выполняется честная, хотя и магическая проверка:
## BB#1:
shr eax, 8
movsx eax, al
movsx ecx, byte ptr [rdi + 2]
inc rdi
jmp LBB0_3
LBB0_2:
mov rdi, qword ptr [rdi + 16]
movsx eax, byte ptr [rdi]
movsx ecx, byte ptr [rdi + 1]
LBB0_3:
imul eax, eax, 27753
lea eax, [rax + rcx + 1423042525]
movsx ecx, byte ptr [rdi + 2]
imul edx, eax, 27753
add edx, ecx
mov eax, edx
sar eax, 31 # some magic check
and eax, dword ptr [rip + _MAX_INT] # yet another magic
add eax, edx
pop rbp
retТаким образом, даже простое переполнение int'a может сделать код нерабочим и принести кучу проблем.
P.S. Все-таки полиномиальные хеши стоит писать по основанию большого простого числа. И сравнение будет работать, и гораздо сложнее найти строки, которые сломают Вашу функцию.
Комментарии (101)
humbug
14.08.2016 15:16+4Рекомендую автору почитать http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c, посчитать 27752 в 3 степени и понять, почему хэш от 2 букв считается нормально, а от 3х уже с какими-то странными результатами.
naryl
14.08.2016 15:29+5Я попридираюсь к терминам, можно?: )
В C++ переменная в принципе не может быть равна её значению, потому что в C++ вообще нельзя сравнивать переменные с чем бы то ни было, можно сравнивать только значения переменных. Но даже если взять язык, в котором можно (например, Common Lisp), то заголовок всё равно был бы не слишком осмысленным, т.к. переменная может быть равна своему значению только если значение этой переменной — сама эта переменная. Т.е., если выражаться терминами C++, если она — ссылка на саму себя, что в C++ сделать не позволит система типов.
mezastel
14.08.2016 15:44На самом деле, все беды лечатся грамотным code review, который приведенный выше код не должен проходить.
bolk
14.08.2016 19:40А ещё все люди должны быть добрыми и помогать друг другу.
withkittens
14.08.2016 20:25-1Code Review — не доброта и взаимопомощь?
bolk
14.08.2016 20:42+2Где как, но мой комментарий не об этом. А о том, что в идеальном мире много что должно быть, в реальности бывает по-разному.
Shifty_Fox
15.08.2016 07:51-1На самом деле, было бы неплохо, если бы _вместо_ оптимизации, компилятор выдавал бы предупреждение, о том что у вас unused code.
mayorovp
15.08.2016 09:12+1Будет куча false positive в кросс-платформенных библиотеках, где константные условия используются для выбора нужной реализации.
Shifty_Fox
15.08.2016 18:35Константные условия это проверки с const или препроцессор? Компилятор сначала разворачивает препроцессор, сохраняя code map. И логично использовать для таких вещей препроцессор, чтобы в сборку точно попадал только код под нужную платформу. Неиспользуемый код есть неиспользуемый код.
ZyXI
15.08.2016 20:27+2Не логично. Во?первых, код с препроцессором может плохо выглядеть, в отличие от
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++ во многом пересекаются.
Revertis
14.08.2016 16:01-6> Как можно увидеть, никакого сравнения в ассемблерном коде после цикла нет. Получается, компилятор решил, что переменная, хранящая неотрицательное значение и которую только увеличивают, стать меньше нуля не может…
Я понимаю, что в стандарте UB, но кто оказался таким тупым, что не предусмотрел переполнения, и решил, что переменная только растет? То есть, половину дела он продумал, а половину нет?mayorovp
14.08.2016 19:59На самом деле тут было вычисление по модулю 232. До того, как компиляторы "научились" использовать UB для оптимизации — для вычислений в кольце вычетов по такому модулю надо было всего лишь игнорировать переполнения.
vadimr
16.08.2016 16:21Не во всех архитектурах целые числа образуют кольцо вычетов.
Это идёт с больших и суперкомпьютеров, где одно время была мода в ряде семейств вообще не реализовывать отдельное целочисленное АЛУ, а использовать в качестве целых чисел ненормализованные вещественные, с мантиссой в прямом коде.mayorovp
16.08.2016 16:25Ну да, платформо-зависимый код, и что? Это, кстати, совершенно нормально для такой области как хеш-функции.
vadimr
16.08.2016 16:28Так его и надо тогда оформлять, как платформо-зависимый, благо, в стандартах С и С++ предусмотрены для этого специальные типы.
mayorovp
16.08.2016 17:25Эти "специальные типы" нужны как раз для обеспечения платформо-независимости. Здесь же такая задача попросту не стояла, вот и все.
vadimr
16.08.2016 17:34Ну так что тогда удивляться, что программа работает только на определённой платформе в определённом режиме компиляции?
Если мне не изменяет память (а проверять лень), вопрос, растрогавший автора поста, исчерпывающе разобран в книге Меткалфа “Оптимизация в Фортране”, написанной ещё до рождения многих современных программистов.
andybelo
15.08.2016 09:40А интересно, в функциональных языках есть такая прелесть, как MAX_INT? И как в таких случаях компилятор поступает? Ей, минусаторы, отзовитесь!
warlock13
15.08.2016 11:38Есть. В Haskell по стандарту так же как в C: беззнаковые числа считаются по модулю, знаковые — UB. Но GHC гарантирует, что и в знаковом лучае будет вычисляться по модулю. Про другие компиляторы не знаю.
Shamov
14.08.2016 16:25+13Это лишь частный случай более общей оптимизации. На самом деле, оптимизатор подобным образом работает не только с переполнением, но и с любым другим UB. При принятии решений об оптимизации он исходит из того, что UB нигде нет. Если, например, в программе будет разыменование указателя, а где-нибудь ниже по коду этот же указатель будет проверяться на NULL, то оптимизатор уберёт проверку (и весь код, который должен быть выполнен в том случае, когда NULL), поскольку к этому моменту уже точно известно, что указатель не равен NULL. Ведь если бы был NULL, то выше по коду случилось бы UB… а такого не может быть, потому что программист не должен такого допускать.
red75prim
14.08.2016 22:36+1Clang и GCC всё-таки стараются предупреждать об оптимизациях, использующих предположение об отсутствии UB.
chabapok
14.08.2016 16:28+4Даже в том случае, если проверка на отрицательность не выбрасывается компилятором, и даже если при этом при переполнении int код не вызывет UB, а ведет себя как простой битовый счетчик, есть шанс напороться на отрицательное число.
Дело в том, что в традиционной схеме представления отрицательных чисел:
MAX_VALUE = (2^n) -1
MIN_VALUE = -(2^n)
Если их сложить, получим -1.
Так же, рекомендую заглянуть в мою заметку (post/278329/) и в каменты к ней. Там подняты некоторые близкие вопросы багов, связанных с переполнением.
senia
14.08.2016 18:25Я не специалист по с++, так что поправьте меня, пожалуйста, но разве в стандарте специфицирован размер int? Как в коде вообще могла оказаться захардкоженая константа максимального значения для int?
ZyXI
14.08.2016 23:29+2От того, что MAX_INT заменят на INT_MAX из limits.h (или что там у вас в C++ вместо этого, вроде какая?то std:: шняга специальная есть вида
std::numeric_limits<int>::max()) смысл статьи не изменится. Но на месте автора я бы всё же заменил.
rogoz
14.08.2016 23:33Есть заголовочный файл climits, в нём есть константа INT_MAX. Судя по всему про этот файл автор тоже не знает.
SfairatOd
14.08.2016 18:28+19А можно было просто сделать int unsigned'om, выпилить проверку, и получить код, который абсолютно легален с точки зрения стандарта.
Stiver
14.08.2016 18:29+9>> Как переменная может быть не равной её собственному значению
Отвечая на вопрос безотносительно статьи: запросто. NaN не равно самому себе.
MrShoor
14.08.2016 19:42А warning/hint компилятор на это дело выдает? Типа бесполезная проверка (h < 0), я её выкину вместе с кодом: h += MAX_INT;
meduzik
14.08.2016 20:21+2То, что видит оптимизатор, мало напоминает исходный код. Это может быть результат раскрытия макросов, специализации шаблонов, кучи inline подстановок, других проходов оптимизации. Возможно, в процессе оптимизации были применены знания о конкретной платформе, и тогда удаление кода условия — «компилятор молодец», а не «программист накосячил». А что если оптимизатор удаляет (после соответствующих подстановок) код проверки на необходимость роста вектора в подобном случае?
std::vector<int> vec; vec.reserve(1024); for ( int i = 0; i < 600; i++ ){ vec.push_back(i * i); }
Для каких-то частных случаев сообщение может и выдается, но в общем случае оно будет бесполезным с кучей false positives.
Информировать о таких вещах — задача все же для статического анализатора, там и работа идет с представлением гораздо ближе к исходному коду, и есть более внятный контроль за ложноположительными срабатываниями.MrShoor
15.08.2016 01:26-1Я вас понял, но ситуация все равно гнусная. Где-то в дебрях кода может проскочить «неудачный» тайпкаст к знаковому типу, а в итоге компилятор наворотит делов.
Просто конкретно в этом моменте косяк хорошо видно, но зная злостный оптимизатор С++ считаю, что выдавать warning/hint в таких случаях жизненно необходимо.
LifeKILLED
14.08.2016 20:01-4Компилятор с непривычки начудил, но я бы тоже удивился, увидев такую странную магию чисел в функции.
vadimr
14.08.2016 20:34+3Я что-то пропустил, и язык теперь гарантирует использование дополнительного кода для представления отрицательных чисел? Знаковый тип для контрольной суммы — это просто грубая ошибка.
mayorovp
14.08.2016 23:17Язык — нет, но платформа — да. На С++ иногда платформо-зависимый код пишут, и это нормально.
vadimr
14.08.2016 23:45Для платформо-зависимого кода надо бы использовать платформо-зависимые типы.
ZyXI
14.08.2016 23:49+1А
int— он что — платформо?независимый?vadimr
15.08.2016 08:29+1Сам тип int — независимый (в отличие, скажем, от int32_t, гарантирующего реализацию именно только на платформах в дополнительном коде). Зависит от платформы только реализация int, на которую хорошая программа не должна завязываться.
А в данном случае надо использовать что-нибудь из серии uint32_t.splav_asv
15.08.2016 09:25+1У вас с оппонентом разное понимание термина платформо-независимый. У вас — реализующийся на всех платформах(т.е. базовый, обзательный к реализации для всех платформ и компиляторов языка). У аппонента — имеющий одинаковые параметры на всех платформах. Лично я больше привык ко второй трактовке.
sysprg
16.08.2016 00:26И как это поможет? В момент приведения его к int (или int32_t) для борьбы с переполнением оптимизатор опять посчитает, что можно выкинуть мертвый код.
ZyXI
16.08.2016 00:58+2@vadimr предложил
uint32_t, а неint/int32_t. Никакого UB при переполнении здесь не будет. Даже если потом приводить результат кint(зачем?) и сравнивать с нулём, по стандарту это implementation?defined, а не undefined behaviour и сравнение с нулём при приведении 32?битного беззнакового целого к 32?битному знаковому не выкинут (вот в случае uint16_t>int32_t выкинули бы, только не думаю, что кто?то здесь будет считать, что это недопустимо).
f1inx
16.08.2016 13:071. int32_t по сравнению с int по стандарту гарантирует только размер контейнера.
Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения, значения для неопределенности, и переполнений.
Открываем стандарт 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.vadimr
16.08.2016 13:12+2Вообще-то в вашей цитате ясным английским языком написано, что отрицательные числа могут представляться в прямом, обратном или дополнительном коде, в зависимости от реализации.
mayorovp
16.08.2016 13:35Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения
В дополнительном коде не бывает знака у нулевого значения
f1inx
16.08.2016 16:50Я поэтому и взял в кавычки, т.к. в дополнительном коде и паддинга не бывает, а видимо на некоторых архитектурах он есть…
Тут речь шла о том, что нету разницы между int32_t etc и int кроме размера контейнера.vadimr
16.08.2016 16:55Разница есть. В соответствии с IEEE Std 1003.1, тип int32_t не должен быть определён, если представление отрицательных целых чисел отлично от дополнительного кода. В отличие от типа int, определённого на всех платформах.
f1inx
18.08.2016 16:34Тут дополнительно нужно уточнять, какого года IEEE Std 1003.1 вы имеете в виду?
Поскольку первые ревизии стандартов IEEE Std 1003.1 включали частично стандарты ANSI C, которые давно устарели.
В данный момент все IEEE Std 1003.xx устарели и нужно использовать ISO/IEC/IEEE 9945:2009/Cor 1:2013f1inx
18.08.2016 16:39IEEE Std 1003.1-2008/Cor 1-2013;
vadimr
18.08.2016 19:52IEEE Std 1003.1-2008/Cor 1-2013:
The typedef name int N _t designates a signed integer type with width N, no padding bits, and a two's-complement representation.
Разумеется, это вопрос POSIX, а не стандарта языка, как и вообще все вопросы внутренней реализации libc.
f1inx
18.08.2016 17:11Не совсем так. Для POSIX наличие целочисленных типов intXX_t и uintXX_t с заданными размерами контейнеров 8,16,32 bit обязательно (знаковые обязаны быть в дополнительном коде) «required». 64 bit требуется, если правильно реализован. Все это описано как расширение ISO C.
sysprg
14.08.2016 21:44-6-fno-strict-overflow для GCC выключает эту херню в оптимизаторе
Prototik
15.08.2016 08:12+6Это в коде херня, и это её надо убирать куда-нибудь подальше, а не выключать оптимизации в компиляторе.
mayorovp
15.08.2016 09:14+1Тем не менее, идея отключить UB при целочисленном знаковом переполнении в одном из модулей (не во всех!), где собраны функции, производящие вычисления в кольце вычетов по модулю 2^32 или 2:64 — довольно здравая.
Prototik
15.08.2016 09:31+2Зачем? Используете unsigned int — и всё будет работать, как и должно работать.
mayorovp
15.08.2016 09:43Иногда знаковый тип требуется на выходе… и не всегда отрицательное значение является ошибкой. Приведение же к типу int с переполнением также даст UB, ЕМНИП.
warlock13
15.08.2016 11:47Приведение же к типу int с переполнением также даст UB.
В C++ можно использовать reinterpret_cast чтобы получить implementation-defined behavior вместо UB. В C, по-идее, можно добиться того же через указатели или union.
f1inx
16.08.2016 12:41Это не так, работать будет, но не как Должно.
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 функции выведенные лучшими собаководами.mayorovp
16.08.2016 13:45Если брать результат по модулю 2N — то переполнение при вычислении h допустимо.
ZyXI
16.08.2016 19:07+3По стандарту
charне знаковый, а implementation?defined. Символы из “basic execution character set” гарантированно неотрицательны (C99, в стандарте C++11 я такого заявления не нашёл). Однозначно знаковым являетсяsigned char, однозначно беззнаковымunsigned char, а самcharвообще не принадлежит ни одному из классов целочисленных типов, описанных в документации.
sysprg
16.08.2016 00:14Скажите это разработчикам glibc или gnump, всяких кодеков, например. Да на самом деле дофига реально существующих библиотек использует хоть где-то в коде подобные уловки.
f1inx
15.08.2016 18:35+1Проблема приведенного исходного кода от этого никуда не девается.
Нужно использовать без знаковый тип это раз.
Кроме того затычка с проверкой знака, будучи не выкинутой компилятором, увеличивает число коллизий данного хэша в два раза для определенного множества входных строк (или окрашивает спектр для любого множества случайных входных значений, кому так понятнее).sysprg
16.08.2016 00:22Можно не цепляться за этот конкретный код, так как он всего лишь демонстрирует общую проблему с default установками оптимизации в последних версиях GCC. Эта оптимизация вступает в противоречие с приемами, которые по сути являются общей практикой для многих библиотек, где много работы с числами (например, вычисления с числами высокой разрядности, криптография, кодеки). Эта оптимизация помогает в редких случаях, но может испортить работу древнего хардкорного кода, который создавали, отлаживали и оптимизировали годами. Не понимаю, нафига они врубили ее именно по умолчанию.
f1inx
16.08.2016 14:22Есть стандарт имплементации языка, если его за годы не прочитали, то это странно.
Посыл про то, что эта оптимизация не нужна тоже мягко говоря странный.
Если программист собирает свои программы с опциями оптимизации, то он должен понимать, что делает и стоит посмотреть, что они подразумевают.
Если он использует новую версию компилятора, то заглянуть в changelog тоже стоит.
Мне вот например не понятно почему для gcc не включена по умолчанию -Wconversion -Wbad-function-cast -Wcast-qual
warlock13
15.08.2016 00:03Стоит еще сказать, что на OS X с оптимизацией -O2 таких ошибок не было замечено.
Просто повесьте рядом с компьютером с OS X зеркало и посмотрите в него — тогда вы может быть всё-таки заметите ошибку (причём независимо от уровня оптимизации).
semenyakinVS
15.08.2016 01:19Я благодарен автору статьи хотя бы за то, что из комментария выше узнал про отношение оптимизаций и UB при компиляции кода.
P.S.: Исходя из названия, кстати, ожидал увидеть что-нибудь про адреса объектов при множественном наследовании (вроде этого).
D_T
15.08.2016 11:36Чтобы наверняка работало надо заменить
if (h < 0) h += MAX_INT;
на
if (h < 0) h ^= 0x80000000;
т.е. смена старшего разряда (там знак) с 1 на 0. Так число гарантированно станет положительным. Можно использовать маску 0xFFFFFFFF, это будет равносильно h = -h-1
kosmos89
15.08.2016 14:27+5Стоит еще добавить, что std::string — состоит из char, а char может быть как знаковым, так и беззнаковым на разных платформах.
И раз уж вы используете C++, то используйте std::numeric_limits.
Иначе ваши возмущения по поводу того, что в разных местах у вас работает по-разному выдает в вас новичка.
pwl
15.08.2016 20:54+6В ассемблерном коде выполняется честная, хотя и магическая проверка
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;
Зачем это надо:
Современные процессоры очень не любят команды условных переходов. Такая оптимизация позволяет сделать эквивалентный код без переходов.mayorovp
16.08.2016 08:30+1Собственно это здесь и делается: в результате арифметического сдвига вправо на 32 бита в eax будет 0, если исодное значение было положительным, или 0xffffff если отрицательным.
Поправка: сдвиг на 31 бит, а не на 32. Сдвиг на 32 бита не изменит число, потому что используются только младшие 5 бит операнда.
pwl
16.08.2016 20:02да, согласен, 31. есть еще несколько ошибок в тексте… (условие в C-ном выражении противоположное написал), но когда заметил редактировать уже не давало. Но так можт и лучше — видно что кто-то прочитал. :)
gbg
Стоп-стоп-стоп. Переполнение int — это UB в C++. Собственно, все прочие рассуждения смысла не несут — достаточно знать Стандарт.
mayorovp
Вот только "раньше работало же". Трюк-то популярный был...
andybelo
Ну вот, уже 6 умных с утра.
andybelo
Ага, двое уже испугались.
andybelo
А седьмой подоспел, видать нооскопист
andybelo
Количество умніх анонимов нарастает по єкспоненте
andybelo
Всего-то 9 умных на весь Хабр? Слабовато. Помню раньше было по -54. Ребята, лучше угадайте, какую страну гугльтранслейт перевёл с английского, как «Я побежал»? Видимо им фрилансеры не отладили нервную сеть.
andybelo
Замечу, что минусуют москвичи после работы. Да, не легка ты судьба внутримкадца.
semenyakinVS
Откройте секрет — это какой социальный эксперимент или банальный бытовой хабраслив?
andybelo
Так вы тоже не знаете какую страну назвали «Я побежал»? Видимо это печально. И с чего вы взяли про какой-то слив, раньше было -54. Постепенно у людей появляются дела, и гадить на стенах становиться некогда. Я рад за них, взрослеем, грамар-наци наконец-то занялись настоящим делом.
И кстати о вас. Я тоже на С++ много писал, но необходимость создавать типы во время исполнения программы уже давно ставит крест на компилируемых языках.
На хабре не нужны радикалы. На хабре нужны мозги, знания и переводы.
AC130
Автор просто описывает поведение компилятора при UB, причём несколько раз упоминая что там UB.
gbg
Это совершенно бессмысленное занятие.
Даже здесь в комментариях можно отследить, что такая подача информации формирует мнение о компиляторе что он «чудит». А компилятор работает в согласии со Стандартом, никаких чудес нет.
Любая эксплуатация UB кроме его ликвидации — это хорошая такая мегатонна, заложенная под проект.
homm
Ну если компилятор это компилирует, да еще и делует это в согласии со Стандартом, то получается, что чудут стандарт.
Если честно, у меня в голове не укладывается, как мог родиться, а тем более стать настолько популярным, язык с UB. Ведь само существование UB — это хорошая такая мегатонна, заложенная под все проекты на этом языке.
ZyXI
А что, были какие?либо другие альтернативы без UB, производительные и пригодные для написания кода для разных экзотических платформ с различными ограничениями? Тут всё просто: либо вы рисуете UB в стандарте, либо вы рисуете там «implementation?defined», что не намного лучше: в случае с UB программист не знает, что там сделает компилятор, в случае с «implementation?defined» программист не знает, что сделает компилятор на другой платформе, только, в отличие от оптимизаций на UB, это незнание вылезет только на той самой другой платформе. Либо вы рисуете в стандарте твёрдые гарантии определённого поведения и проседаете в производительности, иногда очень сильно.
gaki
Вот, например, статья, объясняющая:
https://habrahabr.ru/post/230777/
Saffron
Я вот упорно не понимаю фанатов UB. Если у вас случился UB, то значит можно всё? Файлы с диска поудалять, процессы поубивать, ssh на внешний адрес отрыть? А что, неопределённое поведение — как хочу, так и насру?
Гораздо логичнее в этом случае просто не компилироваться. Видишь UB — отказываешься компилироваться. И никаких подстав.
D_T
Переполнение UB только для стандарта с/с++, для проца (асма) оно вовсе не UB, поэтому на использовании переполнения построены кучи алгоритмов, в т.ч. расчета хэшей, и данный пример не исключение, он тоже использует переполнение. h += h * 27752 + x[i]; дает переполнение неоднократно.
Saffron
Ну мы то имеем дело с c++, а не с процом(асмом). И если он не может справиться — то пусть честно отказывается компилироваться. Мозгов соптимизировать и выкинуть проверку у него хватает, а мозгов признаться в собственной ограниченности — нет.
gbg
1. Компилятор залезть в голову к программисту не может. Некоторые UB случаются в зависимости от входных данных.
2. Не все случаи наличия UB можно логически доказать, имея только код программы.
3. Для выдачи предупреждений о возможном UB есть статические анализаторы, которые работают эвристически (делают вид, что они — ваш опытный коллега, который бедокод детектирует на уровне интуиции, потому как за свою карьеру видел километры мозговых извержений разной степени тяжести).
4. Принцип единой ответственности: задача компилятора — собрать программу, опираясь на стандарт языка; Искать потенциальные проблемы — не задача компилятора.
Поиск плохого кода — на статический анализатор. Поиск утечек памяти и прочего, что на статике не увидеть — на динамический анализатор.
chabapok
«Видишь UB — отказываешься компилироваться.»
С такой хотелкой, вам имеет смысл обратить более пристальное внимание на java. Там подход именно такой, что все должно быть 100% детерминированно, никаких UB не допускается.