Как стать автором
Обновить
81
0
Егор Суворов @yeputons

Пользователь

Отправить сообщение

Но это же другие инструкции. Например, флаг CR не всегда будет установлен сдвигом, в отличие от умножения. Где граница между "очевидный вычислительный метод" и "привязка к конкретному процессору"?

	mov ecx, 0x50000000
	shl ecx, 3  ; CR = 0
	
	mov eax, 0x50000000
	mov ebx, 8
	imul ebx    ; CR = 1

Единственное промежуточное состояние между полным UB и "привязаться к конкретному процессору" (как сделали в Java), мне кажется — это заставить компилятор чётко документировать под каждый процессор всё поведение.

Не то чтобы нормально, но эту битву пользователи компиляторов проиграли почти двадцать лет назад, когда GCC начал убирать наивные проверки на переполнение вроде if (a + 100 < a): https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475#c4

Для хранения бит — да, но выражение -INT_MIN всё ещё может быть не равно самому себе: https://godbolt.org/z/aM3nTc35P

соответствующее логике написанного кода

Так в этом и проблема. Если в коде написано x * 2, а компилятор заменяет на x << 1 — это соответствует логике? А замена x - x на 0? А замена -x на ~x + 1? Стандарт говорит, что да, потому что он говорит про арифметические операции, а как там числа представляются — внутреннее дело компилятора.

И вместе с тем стандарт не определяет абсолютно все операции с целыми числами. Например результат -x определён только если это значение помещается в int, а если не помещается — стандарт ничего не обещает. Вот все такие штуки надо строго определить, чтобы говорить про "логику кода",

Проблема в любой попытке "отменить оптимизации" одна: а какое поведение "правильное" или "не соптимимзированное"? Это либо надо чётко прописывать (в тот же стандарт, что безумно муторно), либо надеяться, что ваша интуиция совпадёт с интуицией разработчиков компиляторов. Оба варианта мне кажутся малореалистичными.

Например, кому-то очевидно, что в 32-битных программах для вещественных чисел надо использовать сопроцессор x87 с 80-битными числами (потому что вдруг мы компилируем под что-то безумно древнее), а кому-то очевидно, что надо использовать SSE с 64-битными числами если доступно. А это отличие влияет на excess precision и добавляет/убирает некоторую недетерминированность вычислений с вещественными числами.

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

Ну а то что такой соптимизированный код соответствует лишь стандарту C++, но не интуиции под конкретный процессор — упс.

> А без оптимизации я даже примерно представляю, что должно получиться в ассемблере и там всё норм, поведение определено архитектурой.

Я бы не был так уверен, потому что граница между "оптимизация" и "не оптимизация" весьма тонка. Даже с -O0 компилятор может "наоптимизировать". Из тривиального — арифметика будет заменена на побитовые операции или будут сокращены слагаемые или c == -c окажется верным даже для INT_MIN.

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

void print(bool x) {
    const char *names[] = {"false", "true"};
    printf(names[x]);
}

В любом языке в многопоточности будет полное UB и может ломаться внутренний метод и вести себя неожиданно. За исключением разве что языков, где выполнение всегда гарантированно однопоточное, вроде JavaScript и Python.

И даже это всё не помогает даже на уровне учебных задач для студентов. Я несколько лет требовал всё это (кроме фаззинга, а зря) в автоматическом режиме для получения ненулевых баллов по домашним заданиям, и всё равно возникали проблемы с UB. В итоге получился доклад: https://cppconf.ru/talks/dd008542beaf4076be59f6a4a2064df9/

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

  • Бывают баги в комбинациях (компилятор, стандартная библиотека, динамический анализатор): показывает UB там, где его нет. Было минимум два раза.

  • Бывает много интересного UB, которое не ловится санитайзерами: вызов std::exit() в деструкторе глобальной переменной, например.

  • Бывают баги в компиляторах: в MinGW очень сильно сломан thread_local.

  • В сторонних библиотеках (даже Boost) регулярно встречается UB, которое ловят санитайзеры, но по факту пока ещё не рушит код. Хотим санитайзеры — надо сразу править у себя зависимости.

  • Санитайзеры умеют находить далеко не все простые выходы за границу массива.

  • Даже в статическом анализаторе компилятора бывают баги: говорит, что есть очевидный use-after-free, а его на самом деле нет.

  • По стандарту C++ есть много странных мест. Например, конструкция for (int element : some_vector) в C++03 (который не поддерживает range-based-for) имеет полное право компилироваться и рушить программу.

  • По факту есть некоторые запрещённые вещи, не указанные ни в стандарте, ни в документации. Просто знать надо. Например, нельзя создать глобальную переменнуюint read; и слинковать с ключом -static. Даже под виндой.

А что ещё? Вопрос неироничный, правда интересно. Какие-нибудь случайные ключи сгенерировать, запросить список устройств чтобы драйвера закэшировать — всё ещё секунды, не минуты.

Конкретно std::gcd может медленно работать в GCC, потому что реализован через алгоритм Евклида не делением, а бинарно. Это в среднем сразу на 20% медленнее работает абсолютно не по делу. К тому же ядом с ним сразу хочется использовать std::lcm, а он при вызове от двух intов возвращает int. Что иногда приводит к переполнению и UB.

Похожие проблемы есть у некоторых алгоритмов и классов из стандартной библиотеки. Например, std::complex<double> старательно а) разбирает кучу случаев с NaN и +/-inf; б) сохраняет совместимость с сишным _Complex и вызывает функции для операций без инлайнинга. Это тоже существенно замедляет код.

Фатальные для задачи проблемы:

  1. В вашем условии потерялось требование x <= n. Валидатор его тоже не требует (в соответствии с условием), но в тестах этого нет. А зря.

  2. В вашем условии потерялось требование "связный подграф размера x". А чекер его при этом требует.

  3. Чекер верит файлу с ответом на слово и не проверяет его в случае YES. Всегда надо проверять оба поданных файла (с ответом участника и с ответом жюри), смотри секцию "readAns paradigm" вот тут (там вообще много полезного про testlib): заводите функцию для чтения файла с ответом и запускаете её и для файла жюри, и для файла участника. И только если оба ответа верны — можно начинать сравнивать. Если у жюри ответ лучше — Wrong Answer, если у участнкиа — Jury Error. Иначе можно случайно сгенерировать все тесты с ответом NO и участники будут получать Wrong Answer.

  4. Непонятно зачем в чекере константа maxN. Вы так добавляете ещё одно место (помимо валидатора и условия) которое надо менять. А чекеру эта константа не нужна.

  5. В ошибках чекера вершины нумеруются с нуля, а не с единицы, как в условии задачи.

  6. Зря используете gcc-специфичный __gcd. Напишите свой (у std::gcd в C++17 свои проблемы, с ним осторожно). В решениях на контесте использовать специфичные конструкции ещё приемлемо, там решение живёт не больше нескольких часов, но в пакете задачи надо всё-таки писать код, который будет работать и через десять лет. Задачи живут очень долго.

  7. Ваш генератор всегда выводит рёбра в определённом порядке: от корня к листьям, родитель всегда идёт первым концом. Некоторые решения могут этим пользоваться. Надо перемешивать и порядок рёбер, и порядок вершин внутри ребра, не только сами вершины. Кстати, есть полустандартные генераторы.

Претензии к валидатору, чекеру и генераторам:

  1. checkGraphIsTree у вас на самом деле ещё и читает. Название путает, лучше readTree(). Аналогично с checkPermutation — лучше readPermutation(). Я смотрел на main и не понимал, где вы считываете граф.

  2. Хорошо бы получать более подробные пояснения от валидатора. Например, если не перестановка — значит, какое-то число встретилось два раза, вот его бы хорошо вывести. Если не дерево — значит, какая-то вершина недостижима из 1, хорошо бы вывести. Имена переменных лучше указывать сразу с индексом: не "v", а "v[" + to_string(i + 1) + "]". Аналогичные претензии к чекеру: не только нет индексов, но и дублируются названия переменных при чтении. Это сильно мешает при отладке.

  3. Непонятно зачем вы несколько раз делаете shuffle перестановки в getRandomTree. Достаточно один раз сделать случайную перестановку. Любые попытки "увеличить рандом" дальше в лучшем случае ничего не делают, в худшем случае ухудшают рандомизированность.

Придирки по оформлению условия:

  1. Традиционно в условиях пишут не просто "YES", а "YES" (без кавычек). Иначе неоднозначно. Аналогично с нумерацией вершин в формате вывода — с нуля или с единицы. Хотя есть и другое мнение — "примеры являются частью условия".

  2. Также хорошо бы выделять строки, которые надо записать в файл напрямую, моноширинным: <<\texttt{YES}>> (без кавычек).

  3. Вместо ~--- лучше использовать "---. В английской типографике, если правильно понимаю, тире принято не отделять пробелами от соседних слов, поэтому обычное длинное тире в TeX пишется как --- и приклеивается с двух сторон к словам. В русской типографике принято отделять пробелами. Можно поставить костыль в виде Тире~---это что-то такое (заменили пробел перед тире на неразрывный пробел в виде ~), а можно сразу использовать тире в русском стиле "---. Тогда его как раз отбиваем пробелами с двух сторон в исходном коде, и оно само правильно расставляет неразрывности.

  4. Вместо \lfloor лучше сразу писать \left\lfloor и \right\rfloor (аналогично с любыми видами парных вещей, вроде скобок). Тогда при компиляции в TeX эти парные штуки станут правильной высоты, чтобы соответствовать внутренностям. Возможно, MathJax делает это автоматически, но это его специфика.

И немного по мелочи:

а потом в Make файле в вашем редакторе указать зависимость.

Это не Make, это CMake, и речь наверняка не про абстрактный редактор, а конкретно про CLion. Плюс не надо использовать \\ — это будет работать только под Windows, используйте прямой слеш /. Хотя это всё происходит локально, так что неважно. Но если локально — то можете просто скопировать testlib.h себе в папку include рядом с компилятором.

но если кто хочет, отдельно про testlib можно почитать тут.

Ссылка битая.

Но для нашей задачи придумать решение, которое получит TL (и при этом будет достаточно адекватным), довольно непросто.

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

Мне казалось, 700 мс — вполне типичное время запуска виртуальной машины с нуля и подгрузки всех классов.

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

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

Функции с циклами не инлайнятся, но допустим, что да.

Не очень понял, вот буквально в этом же примере инлайнятся:get_first превратилась в один if. Или вы про другое? Там только версия gcc 4.1.2 не инлайнит, все более новые (начиная с 4.4.7) инлайнят.

Банальный поиск по файлам по имени функции с включенными опциями поиска слова целиком и с учётом регистра позволяет найти практически все места.

В конкретном случае проблем никаких.

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

Удалить функцию и посмотреть все места с ошибкой компиляции тоже может не помочь — есть перегрузки.

и рассказывает проджект менеджерам что это все потому что это "нереалистичное требование".

Я не слышал ни про одну команду, которой бы удалось написать крупный или хотя бы средний проект на C++ без UB. Пусть даже с простыми багами, главное, чтобы к UB не приводили. Не верю, что можно, буду удивлён узнать хотя бы про один пример.

Работающий на конкретном компиляторе и конкретных данных — да. Но так чтобы можно было хотя бы версию компилятора обновить и ничего не сломать — нет. Да у людей проекты начинают ломаться даже если перед std::sort случайным образом элементы перемешать, потому что они рассчитывают на стабильность сортировки или что-то близкое к ней. Конечно так не надо делать, в стандарте этого не гарантируется, но по факту-то так почему-то люди продолжают регулярно делать. Что в мелких компаниях, что размером с Google.

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

Кстати, а как по вашему должна была бы разрешиться такая ситуация?

Хороший идей у меня нет. Все что есть (включая текущую) — чем-то серьёзно плохи. То количество кода сильно увеличивается, то ещё нетривиальные UB добавляются, то ещё что-то. Да даже когда вводили move semantics в C++11 — это делали наиболее изящным способом, мне кажется, но только с учётом существующих ограничений. Так-то проблем всё равно куча.

Да, поэтому и хотим предупреждение — некорректный код.

Я это к чему: вот перед вами два примера кода. В первом код корректен и предупреждений не ожидается. Но после инлайнинга f в main оказывается, что if лишний: условие всегда неверно. Предупреждение выдавать всё ещё не хочется. Вывод: нельзя выдавать предупреждения на заинлайненых if, если условие всегда неверно.

В другом код некорректен и предупреждения ожидаются. Их можно выдать только если len заинлайнен в get_first, причём предупреждение возникнет только после анализа заинлайненого if (!s): условие всегда неверно из предположения "никто не будет разыменовывать нулевой указатель". Вывод: если заинлайнен if с всегда неверным условием, нужно выдавать предупреждение.

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

Более того, может у нас вообще в проекте базе есть договорённость "нулевой указатель не является корректной строкой". Тогда код остаётся абсолютно такой же,get_first корректен, len содержит лишнюю проверку, а некорректен уже main, вызывающий get_first(nullptr). Компилятору это понять без шансов.

Так вот в данном случае выкидывается if, написанный человеком. Предупреждение не хочется. Но если считать, что инлайнинг — это считается написанным компилятором, то вот абсолютно аналогичный пример с точки зрения синтаксиса, когда предупреждение всё-таки хочется:

#include <iostream>
int len(const char *s) {
  if (!s) {
    return 0;
  }
  int l = 0;
  while (s[l]) l++;
  return l;
}
int get_first(const char *s) {
  int f = static_cast<unsigned char>(s[0]);
  if (len(s) == 0) {
    f = -1;
  }
  return f;
}
int main() {
  std::cout << get_first("hello") << "\n";
  std::cout << get_first(nullptr) << "\n";
}

Здесь компилятор может заинлайнить len (которая используется в куче разных мест) в get_first. После этого увидеть, что из-за строчки `f = s[0]` можно предполагать, что s — не nullptr, и убрать заинлайненную проверку `if (!s)`. И не выдать предупреждение, ведь этот иф "написал компилятор". Но в данном случае предупреждение как раз хочется: get_first думает что случай "пустая строка" разобран, а на самом деле разобран не до конца. Конечно, в данном случае легко увидеть вызов от nullptr, но его можно делать из другой единицы трансляции, сторонней библиотеки, или вообще замаскировать.

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

Информация

В рейтинге
Не участвует
Откуда
Санкт-Петербург, Санкт-Петербург и область, Россия
Дата рождения
Зарегистрирован
Активность