Как проявляется баг?
- Сложность std::map::merge и std::set::merge вместо заявленной стандартом N*log(size()+N)), где N — размер добавляемой части, оказывается примерно N в квадрате.
- Если с помощью merge был добавлен контейнер с достаточно большим количеством элементов — при уничтожении результирующего контейнера получим stack overflow.
- Контейнер после работы merge приходит в некорректное состояние, поэтому возможны и другие проявления.
Что говорит Microsoft?
Багрепорт был отправлен мной в Microsoft почти 2 месяца назад.
В Visual Studio 2019 Update 2 Preview 2 должны были исправить.
А вот в текущей версии Visual Studio 2017 15.9.12 не исправлено до сих пор, и, судя по последним сообщениям, ждать еще долго…
Баг заключается в некорректной маркировке цвета добавленных узлов в реализации красно-чёрного дерева.
Как воспроизвести?
//#include "pch.h"
#include <chrono>
#include <string>
#include <iostream>
#include <map>
#include <set>
const size_t mainSize = 50'000;
const size_t additionSize = mainSize;
auto getMainMap()
{
std::map<size_t, std::string> result;
while( result.size() < mainSize )
result.emplace(result.size(), "SomeText");
return result;
}
auto getAdditionMap()
{
std::map<size_t, std::string> result;
while ( result.size() < additionSize )
result.emplace(mainSize + result.size(), "SomeAdditionText");
return result;
}
int main()
{
{
auto mainMap = getMainMap();
auto addition = getAdditionMap();
auto start = std::chrono::steady_clock::now();
for ( auto const &elem : addition )
mainMap.emplace(elem);
auto end = std::chrono::steady_clock::now();
std::cout << "manual insertion with copy: "
<< std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
<< std::endl;
}
{
auto mainMap = getMainMap();
auto addition = getAdditionMap();
auto start = std::chrono::steady_clock::now();
mainMap.merge(addition);
auto end = std::chrono::steady_clock::now();
std::cout << "std::map::merge: "
<< std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
<< std::endl;
} // <---- and stack overflow here because of incorrect mainMap after merge
return 0;
}
Варьируя значение mainSize, можно получать разные результаты — либо только медленное выполнение, либо еще и крах.
Что делать?
Пересмотреть свой код и заменить обращения к merge ручной вставкой. Либо перейти на VS 2019.
А если скомпилированный код уже ушёл к заказчику… Оххх…
Комментарии (34)
Dubovik_a Автор
10.06.2019 21:47Для выявления этого бага даже внутреннее состояние проверять не обязательно — оно же просто крошится при очень небольшой нагрузке (порядка десятков тысяч элементов).
И опасный баг. Ох опасный. Т.к. зависит от того, какое количество данных пользователь надумает обработать.
datacompboy
10.06.2019 21:58не часто в юнит тестах пишут размерны тесты. тем более никто не пишет тест «скормить рандом и посмотреть что не упало» — ну кроме случая когда поймали уже такую вещь.
квикчек это сила.
даже интересно (студии нынче нет у меня) — если скормить github.com/emil-e/rapidcheck вот этому, баг изловится?Dubovik_a Автор
10.06.2019 22:11+1никто не пишет тест «скормить рандом и посмотреть что не упало»
Кто хочет подобных ляпов — пусть не тестирует. А я свои алгоритмы обычно прогоняю в том числе и на случайных данных. Более того, проверяю не просто «чтоб не упало», а еще и «чтобы результат обработки случайных данных совпал с ожидаемым» (да-да, при формировании случайной тестовой выборки зачастую можно сформировать и ожидаемый результат).datacompboy
10.06.2019 22:13Всё, что может быть автоматизировано — должно быть автоматизировано. Тестирование тоже.
0xd34df00d
11.06.2019 16:15Особенно в этом случае. Например, если загнать данные в rb-tree, а потом их оттуда прочитать, то мы должны получить искомый список, но отсортированный. У меня в моём решении задачек из purely functional data structures есть тесты вида
property $ \(list :: [Int]) -> RB.toList (RB.fromList list) == sort list
QC сам найдёт, если и где это опровергается.
Ну а потом уже можно какие-то там инварианты проверять, типа
property $ \(lst :: [Int]) -> RB.isSearchTree $ RB.toList list property $ \(lst :: [Int]) -> RB.noRedRedPath $ RB.toList list property $ \(lst :: [Int]) -> RB.sameBlackCount $ RB.toList list
Можно, конечно, доказывать корректность, но это сложнее и уж точно не на плюсах.
Dubovik_a Автор
11.06.2019 16:27А сортированность в данном случае и не нарушается. И мапа даже продолжает работать, почти как живая — производит вставки, ищет, итерирует. И это тоже часть опасности бага: прикладной разработчик, доверяющий реализации STL, может даже ничего и не заметить, если работает с небольшим количеством данных.
khim
11.06.2019 18:08Дык там возникает перекособоченное дерево. Как раз беда именно в том, что нарушаются гарантии по сложности, всё остальное работает.
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека. Был бы стек побольше — оно и с миллионами элементов работало бы…Dubovik_a Автор
11.06.2019 18:14гарантии по сложности влияют на необходимую глубину стека
Нет. На необходимую глубину стека влияет тот факт, что Майкрософт при уничтожении мапы использует рекурсивный алгоритм.khim
11.06.2019 18:22Дык ему должно быть пофигу в какие цвета там вершины расскрашены, разве нет?
Проблема в том, что если мапара «перекособоченная» — то грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла.
Или я чего-то не понял?Dubovik_a Автор
11.06.2019 18:27грубина рекурсии оказывается такой, как она ни при каких данных, без ошибки, оказаться бы не смогла
Да.
Но:
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека
Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?
Прогоните деструктор на больной вижле под дебаггером — станет понятнее, что там происходит.khim
11.06.2019 18:40Нет. Они влияют только на скорость. Как они могут влиять на глубину стека?
Очень просто: если у вас мапа — это красно-чёрное дерево, то там количество уровней — порядка логарифма от количества элементов. А если оно выродилось в список — то у вас там могут быть тысячи уровней для тысяч элементов… что в сбалансированном дереве не может случиться даже при количестве данных порядка эксабайтов…Dubovik_a Автор
11.06.2019 18:49Это понятно.
Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
В результате поиск по линии превратился из логарифмического в линейный, что нарушило соглашения о сложности поиска.
Не понятна только Ваша фраза:
А креши возникают потому что гарантии по сложности влияют на необходимую глубину стека
Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.khim
11.06.2019 18:58Мапа должа быть деревом, а глючный алгоритм мержа сломал дерево и добавленную часть выпрямил в линию.
Линия — это тоже дерево. Ваш К.О.
Если бы в деструкторе был применён нерекурсивный алгоритм, то деструктор даже на такой поломанной мапе не крошился бы. И даже работал бы с нормальной скоростью, т.к. его сложность что так, что эдак линейная.
С другой стороны если бы дерево оставалось красно-чёрным, то ни при каких разумных объёмах (влезающих а адресное пространтство x86-64 CPU) глубина стека не перешла бы 100, так что не очень понятно — имеет ли смысл усложнять алгоритм чтобы поддерживать версию либы в которой очевидная ошибка…
Dubovik_a Автор
11.06.2019 18:34Мне вот сейчас еще одна нестыковка в голову пришла.
В реализации RBTree от Microsoft в дебаге производится проверка корректности работы оператора сравнения. Я как-то раз вместо «operator<» подсунул «operator<=» — оно в итоге выкрошилось с вразумительной диагностикой.
Так вот. Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
А это не позволило бы багу случиться.khim
11.06.2019 18:54Проверка целостности внутреннего состояния (требования чередования «красный-чёрный») в дебаге выглядит даже более логичной, чем проверка внешнего оператора сравнения. Но не производится.
Что значит «более логичной»? Внешний оператор сравнения если вы подсовываете кривой — то у вас будут проблемы даже при идеально написанном дереве. Потому эта проверка помогает стороннему разработчику. А требования красно-чёрности — это чисто проверка на валидность реализации самого дерева… при правильно написанной реализации это никому, кроме разработчиков самой библиотеки, не нужно.
В GNU библиотеках есть так называемый «Maintainer Mode» — вот там такие проверки были бы уместны…Dubovik_a Автор
11.06.2019 19:00при правильно написанной реализации
Проблема в том, что мы тут обсуждаем именно неправильную реализацию. И даже не просто неправильную реализацию, а факт её выхода в релизную версию средства разработки. И разговор как-то пошёл в ключе «а как разработчики до такого докатились» и «что они должны были сделать, чтобы это предотвратить».khim
12.06.2019 00:50Ну уж вставлять странные проверки в код, которые будет запускать пользователь всяко не стоит.
А вот сделать тесты, которые будут проверять что дерево осталось красно-чёрным деревом поиска и скрестить их с фаззингом — самое то.
tangro
11.06.2019 10:54Зачем в коде для воспроизведения бага chrono и замеры времени? Код для воспроизведения должен быть минимальным.
Dubovik_a Автор
11.06.2019 10:57Одним из проявлений бага является медленное исполнение. Как предлагаете его проверять без chrono? С секундомером сидеть?
tangro
11.06.2019 11:02Во-первых, главный баг — это креш, а он воспроизводится и без таймеров. Во-вторых, как предполагается оценить замедление по этому коду? Ну, выведет он «100 микросекунд» — а как понять хорошо это или плохо?
Dubovik_a Автор
11.06.2019 11:09А Вы этот код запускали? Он не одну цифру выведет, а две. И конкретно в приведённом коде они будут различаться раз так в 400-500.
Упадёт ли код в stack overflow, зависит от размера стэка. Чтобы код гарантированно упал при любом разумном размере стэка, надо бахнуть эдак миллион элементов, которые будут мержиться проблемным алгоритмом минут 30.tangro
11.06.2019 11:29Две-то две, но что они покажут? Сравнение работы «emplace в цикле» и «merge». А стандарт нигде не говорит, что эти операции должны быть как-то связаны. Да, есть оценка О для обеих, но там могут быть совершенно разные коэфициенты.
Я бы сказал, что если уж браться за замеры времени, то нужно показать рост времени с ростом размера выборки для «emplace в цикле» и для merge. Тогда будет видно, что один логарифмичный, а второй квадратичный.Dubovik_a Автор
11.06.2019 11:34+2В данном случае такая дотошность определённо излишняя.
Этот код вполне убедил Microsoft, что баг у них есть.
И этот код позволяет в течение минуты любому читателю статьи проверить, содержится ли этот баг в его инструменте.
По-моему, именно это от тестового кода и требуется.
Dubovik_a Автор
11.06.2019 11:21Падение еще и от битности зависит. При размере стэка по умолчанию в x64 16'000 еще проходят, а 17'000 — уже нет.
А в x86 43'000 проходят, а 44'000 — уже нет.
tangro
11.06.2019 10:56+1Тот редкий случай, когда на собеседовании нужно было попросить разрабочика развернуть на доске красно-чёрное дерево :)
vassabi
11.06.2019 11:38+1это еще что. Вот когда вин10 была еще в стадии анонсов, и ее можно было погонять вместе с анонсированным VS2015 (записавшись в «программу инсайдеров» — вам можно было скачать билды до их официального релиза) в очередном билде они выкатили ошибку в strlcat (ЕМНИП не работала конкатенация, если первая строка нулевой длины).
Хотя казалось бы — ну ладно, кто-то жестоко протупил, но зачем вообще надо было трогать тот код?khim
11.06.2019 14:28+1У меня нет VS2015, чтобы проверить, но могу предположить что «потрогать» код решили из-за поддержки SSE4.2.
Инструкции STTNI (входящие в SSE4.2) позволяют ускорить строковые функции — причём хорошо так ускорить, разика 2-3… однако только для длинных строк.
Чтобы производительность на коротких строках не упала «ниже плинтуса» (а strlcat и на коротких строках используют тоже) нужен довольно-таки большой шаманский бубен…
Видимо у Microsoft шаман был не проспавшимся, когда этот бубен прилаживал…vassabi
13.06.2019 11:01… просто от функции уровня strlcat я такого не ожидал.
в отличии от комментатора ниже, я все же не думаю, что "индустрия катится в бездну", но я был ранее уверен, что там более полные тесты стандартных либ CRL\STL.
gecube
13.06.2019 11:38На самом деле она катится, но это явно не вопрос этого топика (посмотрите только на количество кода на каком-нибудь гитхабе в разрезе его качества).
khim
13.06.2019 14:24Все считают, что уж что-то, а стандартную библиотеку кто-нибудь протестирует… кто-нибудь другой.
Дима Вьюков рассказывает, как они фаззят всякие вещи, но при этом стандартная библиотка… заменяется загрушками (и считается, что с ней всё в порядке априори).
Есть, правда, и тесты на стандартную библиотеку отдельные, но иногда да — таки получается эффект «у семи нянек — дитя без глазу».
gecube
13.06.2019 09:23Вы своей статьей разрушили мой внутренний мир. Я-то думал, что реализация STL в MSVC эталонная и ей как минимум можно доверять. Оказыватся, что нет. Я считаю, что это просто вопиющий случай безалаберности и показывает как наша индустрия катится в бездну.
datacompboy
Интересно… QuickCheck-style тестирование с проверками на корректность состояния бы таки помогли, да?
JekaMas
Тоже очень любопытно про property based testing. Обычного fuzzing в проектах уже не хватает.