Всем привет,
Сегодня при дорешивании Харьковской Зимней Школы (а у них стоит G++ 4.5.3) столкнулся с такой проблемой, что довольно очевидное дерево отрезков получало WA2, когда как у меня часовой стресс-тест никаких багов не нашёл. Задача такая: дан массив, поступают запросы "GET l r a b", нужно выводить количество чисел на [l,r], значения которых находятся в промежутке [a,b].
Мой код: http://pastie.org/3810241 Наивное решение: http://pastie.org/3810252 Тест: http://pastie.org/3810319 Скрин: http://imgur.com/tquWU
После часа шаманства нашёл причину, если код функции calc просто перенести в query, или же тупо написать inline перед calc, то всё становится окей.
Причём у меня на GCC 4.6.x разницы никакой нет, а на 4.5 ветке ответы получаются разными. Компилирую с "-O2".
Я не особо знаток плюсов, помогите пожалуйста, почему так получается?
На ideone.com с GCC 4.3.4 тоже самое: http://ideone.com/9XbOr
а пробовали свой бинпоиск писать?
Я пробовал за линию проходить. Всё равно та же тема: http://ideone.com/mj3im
Но там тоже прикол есть. Если линию переписать на итераторы, то становится правильно: http://ideone.com/fEOY4
Просто я столкнулся с проблемой, когда уже убрал все векторы (там обновлять значения просто нужно), написал декартово дерево и там та же проблема. Если функцию подсчёта значений в дереве заинлайнить, то всё ок: http://ideone.com/2WxDs , без инлайна: http://ideone.com/WzkyZ
Там налицо какой-то баг оптимизатора. Например добавление
cerr <<"!!!"<<v<<" "<<l <<" "<<r<<" "<<tl<<" "<<tr<<" "<<a<<" "<<b<< " -> "<<res<<endl;в функцию calc приводит к адекватной работе. Сейчас попробую точно разобраться что происходит.Я думаю оптимизаторы набажили с регистрами, забыв обнулить регистр или поюзав один регистр для разных переменных. Надо послать разработчикам и забить. Но если вы хотите поизучать машинный код, ваше право, мьсе.
Ну глубже ассемблера лезть точно глупо, а знания его, чтобы разобраться что происходит мне не хватит.А отправлять разработчикам почти бессмысленно — на более новых версиях не проявляется. Уже отрепортили видимо.
Сильно уменьшенная версия кода.
А теперь магия! Вот тут баг не проявляется. Оптимизатор демон. как он это делает?
UPD: Видимо с нулем баг не компилятора, а мой. Там просто ответ правильный меняется. Так де по просьбам трудящихся лучше отформатированный и еще уменьшенный код.
Я не вижу разницы в коде, только разницу в стиле расцветки, сделай одинаковую пожалуйста, иначе полный бред.
там в одном res = 0, в другом res = 1. Но да, Паша, сделай одну расцветку и форматирование :)
Это случайно. Сейчас пофикшу. Разница в том, что в одном случае
res = 1в другомres = 0Ага, я уже увидел, когда скопировал оба куска кода в блокнот.
В 4.4 и 4.6 не проявляется.
Я не знаю, как они умудрились, но в asm-коде тупо нету присваивания res = ..., в него сразу кладется результат вычисления calc(). Это видно при сравнении кода в gcc4.6 и в gcc4.5