Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 34
Интересно… QuickCheck-style тестирование с проверками на корректность состояния бы таки помогли, да?
Для выявления этого бага даже внутреннее состояние проверять не обязательно — оно же просто крошится при очень небольшой нагрузке (порядка десятков тысяч элементов).
И опасный баг. Ох опасный. Т.к. зависит от того, какое количество данных пользователь надумает обработать.
И опасный баг. Ох опасный. Т.к. зависит от того, какое количество данных пользователь надумает обработать.
не часто в юнит тестах пишут размерны тесты. тем более никто не пишет тест «скормить рандом и посмотреть что не упало» — ну кроме случая когда поймали уже такую вещь.
квикчек это сила.
даже интересно (студии нынче нет у меня) — если скормить github.com/emil-e/rapidcheck вот этому, баг изловится?
квикчек это сила.
даже интересно (студии нынче нет у меня) — если скормить github.com/emil-e/rapidcheck вот этому, баг изловится?
никто не пишет тест «скормить рандом и посмотреть что не упало»
Кто хочет подобных ляпов — пусть не тестирует. А я свои алгоритмы обычно прогоняю в том числе и на случайных данных. Более того, проверяю не просто «чтоб не упало», а еще и «чтобы результат обработки случайных данных совпал с ожидаемым» (да-да, при формировании случайной тестовой выборки зачастую можно сформировать и ожидаемый результат).
Всё, что может быть автоматизировано — должно быть автоматизировано. Тестирование тоже.
А сортированность в данном случае и не нарушается. И мапа даже продолжает работать, почти как живая — производит вставки, ищет, итерирует. И это тоже часть опасности бага: прикладной разработчик, доверяющий реализации STL, может даже ничего и не заметить, если работает с небольшим количеством данных.
Дык там возникает перекособоченное дерево. Как раз беда именно в том, что нарушаются гарантии по сложности, всё остальное работает.
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека. Был бы стек побольше — оно и с миллионами элементов работало бы…
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека. Был бы стек побольше — оно и с миллионами элементов работало бы…
гарантии по сложности влияют на необходимую глубину стека
Нет. На необходимую глубину стека влияет тот факт, что Майкрософт при уничтожении мапы использует рекурсивный алгоритм.
Дык ему должно быть пофигу в какие цвета там вершины расскрашены, разве нет?
Проблема в том, что если мапара «перекособоченная» — то грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла.
Или я чего-то не понял?
Проблема в том, что если мапара «перекособоченная» — то грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла.
Или я чего-то не понял?
грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла
Да.
Но:
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека
Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?
Прогоните деструктор на больной вижле под дебаггером — станет понятнее, что там происходит.
Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?Очень просто: если у вас мапа — это красно-чёрное дерево, то там количество уровней — порядка логарифма от количества элементов. А если оно выродилось в список — то у вас там могут быть тысячи уровней для тысяч элементов… что в сбалансированном дереве не может случиться даже при количестве данных порядка эксабайтов…
Это понятно.
Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
В результате поиск по линии превратился из логарифмического в линейный, что нарушило соглашения о сложности поиска.
Не понятна только Ваша фраза:
Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.
Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
В результате поиск по линии превратился из логарифмического в линейный, что нарушило соглашения о сложности поиска.
Не понятна только Ваша фраза:
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека
Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.
Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.Линия — это тоже дерево. Ваш К.О.
Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.С другой стороны если бы дерево оставалось красно-чёрным, то ни при каких разумных объёмах (влезающих а адресное пространтство x86-64 CPU) глубина стека не перешла бы 100, так что не очень понятно — имеет ли смысл усложнять алгоритм чтобы поддерживать версию либы в которой очевидная ошибка…
Мне вот сейчас еще одна нестыковка в голову пришла.
В реализации RBTree от Microsoft в дебаге производится проверка корректности работы оператора сравнения. Я как-то раз вместо «operator<» подсунул «operator<=» — оно в итоге выкрошилось с вразумительной диагностикой.
Так вот. Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
А это не позволило бы багу случиться.
В реализации RBTree от Microsoft в дебаге производится проверка корректности работы оператора сравнения. Я как-то раз вместо «operator<» подсунул «operator<=» — оно в итоге выкрошилось с вразумительной диагностикой.
Так вот. Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
А это не позволило бы багу случиться.
Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.Что значит «более логичной»? Внешний оператор сравнения если вы подсовываете кривой — то у вас будут проблемы даже при идеально написанном дереве. Потому эта проверка помогает стороннему разработчику. А требования красно-чёрности — это чисто проверка на валидность реализации самого дерева… при правильно написанной реализации это никому, кроме разработчиков самой библиотеки, не нужно.
В GNU библиотеках есть так называемый «Maintainer Mode» — вот там такие проверки были бы уместны…
при правильно написанной реализации
Проблема в том, что мы тут обсуждаем именно неправильную реализацию. И даже не просто неправильную реализацию, а факт её выхода в релизную версию средства разработки. И разговор как-то пошёл в ключе «а как разработчики до такого докатились» и «что они должны были сделать, чтобы это предотвратить».
Зачем в коде для воспроизведения бага chrono и замеры времени? Код для воспроизведения должен быть минимальным.
Одним из проявлений бага является медленное исполнение. Как предлагаете его проверять без chrono? С секундомером сидеть?
Во-первых, главный баг — это креш, а он воспроизводится и без таймеров. Во-вторых, как предполагается оценить замедление по этому коду? Ну, выведет он «100 микросекунд» — а как понять хорошо это или плохо?
А Вы этот код запускали? Он не одну цифру выведет, а две. И конкретно в приведённом коде они будут различаться раз так в 400-500.
Упадёт ли код в stack overflow, зависит от размера стэка. Чтобы код гарантированно упал при любом разумном размере стэка, надо бахнуть эдак миллион элементов, которые будут мержиться проблемным алгоритмом минут 30.
Упадёт ли код в stack overflow, зависит от размера стэка. Чтобы код гарантированно упал при любом разумном размере стэка, надо бахнуть эдак миллион элементов, которые будут мержиться проблемным алгоритмом минут 30.
Две-то две, но что они покажут? Сравнение работы «emplace в цикле» и «merge». А стандарт нигде не говорит, что эти операции должны быть как-то связаны. Да, есть оценка О для обеих, но там могут быть совершенно разные коэфициенты.
Я бы сказал, что если уж браться за замеры времени, то нужно показать рост времени с ростом размера выборки для «emplace в цикле» и для merge. Тогда будет видно, что один логарифмичный, а второй квадратичный.
Я бы сказал, что если уж браться за замеры времени, то нужно показать рост времени с ростом размера выборки для «emplace в цикле» и для merge. Тогда будет видно, что один логарифмичный, а второй квадратичный.
Падение еще и от битности зависит. При размере стэка по умолчанию в x64 16'000 еще проходят, а 17'000 — уже нет.
А в x86 43'000 проходят, а 44'000 — уже нет.
А в x86 43'000 проходят, а 44'000 — уже нет.
Тот редкий случай, когда на собеседовании нужно было попросить разрабочика развернуть на доске красно-чёрное дерево :)
это еще что. Вот когда вин10 была еще в стадии анонсов, и ее можно было погонять вместе с анонсированным VS2015 (записавшись в «программу инсайдеров» — вам можно было скачать билды до их официального релиза) в очередном билде они выкатили ошибку в strlcat (ЕМНИП не работала конкатенация, если первая строка нулевой длины).
Хотя казалось бы — ну ладно, кто-то жестоко протупил, но зачем вообще надо было трогать тот код?
Хотя казалось бы — ну ладно, кто-то жестоко протупил, но зачем вообще надо было трогать тот код?
У меня нет VS2015, чтобы проверить, но могу предположить что «потрогать» код решили из-за поддержки SSE4.2.
Инструкции STTNI (входящие в SSE4.2) позволяют ускорить строковые функции — причём хорошо так ускорить, разика 2-3… однако только для длинных строк.
Чтобы производительность на коротких строках не упала «ниже плинтуса» (а strlcat и на коротких строках используют тоже) нужен довольно-таки большой шаманский бубен…
Видимо у Microsoft шаман был не проспавшимся, когда этот бубен прилаживал…
Инструкции STTNI (входящие в SSE4.2) позволяют ускорить строковые функции — причём хорошо так ускорить, разика 2-3… однако только для длинных строк.
Чтобы производительность на коротких строках не упала «ниже плинтуса» (а strlcat и на коротких строках используют тоже) нужен довольно-таки большой шаманский бубен…
Видимо у Microsoft шаман был не проспавшимся, когда этот бубен прилаживал…
… просто от функции уровня strlcat я такого не ожидал.
в отличии от комментатора ниже, я все же не думаю, что "индустрия катится в бездну", но я был ранее уверен, что там более полные тесты стандартных либ CRL\STL.
в отличии от комментатора ниже, я все же не думаю, что "индустрия катится в бездну", но я был ранее уверен, что там более полные тесты стандартных либ CRL\STL.
На самом деле она катится, но это явно не вопрос этого топика (посмотрите только на количество кода на каком-нибудь гитхабе в разрезе его качества).
Все считают, что уж что-то, а стандартную библиотеку кто-нибудь протестирует… кто-нибудь другой.
Дима Вьюков рассказывает, как они фаззят всякие вещи, но при этом стандартная библиотка… заменяется загрушками (и считается, что с ней всё в порядке априори).
Есть, правда, и тесты на стандартную библиотеку отдельные, но иногда да — таки получается эффект «у семи нянек — дитя без глазу».
Дима Вьюков рассказывает, как они фаззят всякие вещи, но при этом стандартная библиотка… заменяется загрушками (и считается, что с ней всё в порядке априори).
Есть, правда, и тесты на стандартную библиотеку отдельные, но иногда да — таки получается эффект «у семи нянек — дитя без глазу».
Вы своей статьей разрушили мой внутренний мир. Я-то думал, что реализация STL в MSVC эталонная и ей как минимум можно доверять. Оказыватся, что нет. Я считаю, что это просто вопиющий случай безалаберности и показывает как наша индустрия катится в бездну.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Внимание! Опасный баг в реализации C++ std::map::merge и std::set::merge в Visual Studio 2017