Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера.
Интересно было то, что как только обнаружилась причина проблемы, как все ее косвенные проявления сразу встали на свои места, а их объяснение стало абсолютно логичным.
Может быть будет интересно кому еще, поэтому выкладываю здесь.
Есть класс (C++), представляющий из себя коллекцию некоторых записей. Назовем его Rowset. Работал он долго, без каких-либо видимых проблем. Но в один прекрасный день кто-то заметил, что на платформе S этот Rowset отнимает необычно много памяти, когда количество записей достигает где-то сто тысяч. На других платформах, L (A и H), такого эффекта не наблюдалось. Стали экспериментировать, оказалось что если добавлять в Rowset записи по одной и их количество довести до пол-милиона/миллион, то на платформе S наш процесс с Rowset вылетает с ошибкой out-of-memory, достигая в памяти размера 4GB. На платформах L (A,H) вроде все с памятью нормально. Но только там при большом количестве записей, Rowset начинает как-то подозрительно медленно работать. Т.е. десятки тысяч записей добавляются за секунду-две, а сотни тысяч уже сотню секунд, несколько минут (при этом отнимая в памяти где-то около 100MB, т.е. не так много). Наоборот, на платформе S, какое-то непропорциональное разбухание в памяти, т.е. до определенного количество записей размер выделяемой памяти не сильно отличается от того, что наблюдается на платформах L (A,H), а потом он резко растет.
Поискали утечки памяти. Вроде все нормально, утечек нет. Да и потом, как так может быть, что утечки есть только на одной платформе, а на других этот же код выполняется без утечек?
Внимание, вопрос: в чем может быть проблема и как ее искать?
Здравствуйте, Сергей Мухин, Вы писали:
СМ>Здравствуйте, alexeiz, Вы писали:
A>>Внимание, вопрос: в чем может быть проблема и как ее искать?
СМ>такое поведение может быть при неверной hash функции
Здравствуйте, alexeiz, Вы писали:
СМ>>такое поведение может быть при неверной hash функции
A>Каким образом?
если она всегда выдает одно значение (а это легко может быть платформозависимо), то вместо равномерного распределения, получите одну обыкновенную цепочку, с соответсвущ потерей памяти (правда не значительно) и большой потерей производительности.
Здравствуйте, alexeiz, Вы писали:
A>Может быть будет интересно кому еще, поэтому выкладываю здесь.
Данетка?
A>Есть класс (C++), представляющий из себя коллекцию некоторых записей.
А какой контейнер в коллекции?
Так навскидку похоже на поведение хэш-таблицы — в одном случае (когда кончается память) происходит слишком широкое перераспределение, а в другом (с тормозами) его не происходит, но в корзинке образуется много коллизий и поиск внутри корзинки начинает тормозить. По идее, это и является критерием для перераспределения, непонятно, почему его не происходит, особенно если хэш-функция одна и та же и реализация таблицы (т.е. параметры, управляющие перераспределением) тоже одна и та же. Но если и то, и другое разное на разных платформах, это может быть причиной.
Здравствуйте, jazzer, Вы писали:
J>Так навскидку похоже на поведение хэш-таблицы — в одном случае (когда кончается память) происходит слишком широкое перераспределение, а в другом (с тормозами) его не происходит, но в корзинке образуется много коллизий и поиск внутри корзинки начинает тормозить. По идее, это и является критерием для перераспределения, непонятно, почему его не происходит, особенно если хэш-функция одна и та же и реализация таблицы (т.е. параметры, управляющие перераспределением) тоже одна и та же. Но если и то, и другое разное на разных платформах, это может быть причиной.
да, про ошибку в перераспределение я и забыл. но ее вероятность меньше, а так же сложней сделать эту часть платформозависимой. а хэш ф-ия легко — например используются адреса объектов, а они могут иметь какие-то быить всегда 0 (или 1) на конкр платфо.
Здравствуйте, alexeiz, Вы писали:
A>Поискали утечки памяти. Вроде все нормально, утечек нет. Да и потом, как так может быть, что утечки есть только на одной платформе, а на других этот же код выполняется без утечек?
A>Внимание, вопрос: в чем может быть проблема и как ее искать?
Как недавно были убедился, но отсутствие утечек памяти не говорит, что с памятью всё в порядке. Была ситуация, когда всё работает отлично, НО при завершении работы, когда идёт всеобщая чистка, примерно в одном случае из пяти вываливалось предупреждение о записи в уже освобождённую ранее память кучи, при этом стек мог указывать на любое место от деструкторов std коллекций до вызова функции с cdcdcdcd данными. Для повышения вероятности появления ошибки поток данных надо было довести до нескольких сотен тысяч записей. Так как это была не утечка, которую можно поймать простым макросом по перегрузке new, то после безуспешных поисков в Интернете просто переписал new и delete на свои функции, которые при инициализации просто выделяют огромный кусок памяти (простой массив), а при каждом обращении берут очередной элемент и отдают его, протоколируя в какой момент какие участки памяти были выделены и освобождены (повторного использования памяти не было). С первого же раза отладчик поймал нужную функцию. Причина оказалась в том, что у меня были два класса А и Б, при этом для А выделялись куски при первичном обращении, а Б это постоянные new и delete. Думал, и всё время ошибки оказывались рядом с классом Б, поэтому его new и delete и перегрузил, а проблема была в классе А, где я два раза умудрялся вызвать delete.
Поэтому если проблема с памятью, то надо постараться просто отследить какие куски кода выделяются/освобождаются и вывести в лог файл, кто запросил и почему. В любом случае, ошибка должна быть в программе, хотя постоянно и хочется верить в чудеса.
и еще. На одной и windows системе (давно было наверно это был windowsNT4, а мб еще раньше) было замечено очень плохое поведение кучи, когда число аллокаций приближается к миллиону. Очень медленно работало. Пришлось написать свою кучу. Но в след windows версии — все работало быстро.
Здравствуйте, alexeiz, Вы писали:
A>Внимание, вопрос: в чем может быть проблема и как ее искать?
А не используется ли каких временных сущностей? Например, преобразование в DOM-модель и обратно, с целью верификации? Или ведение лога обработанных сущностей? Или какой-то статистической таблицы — тоже можно весьма шустро (и нелинейно) нарастить аппетиты по памяти с ростом объема данных.
Здравствуйте, jazzer, Вы писали:
J>Здравствуйте, alexeiz, Вы писали:
A>>Может быть будет интересно кому еще, поэтому выкладываю здесь. J>Данетка?
A>>Есть класс (C++), представляющий из себя коллекцию некоторых записей. J>А какой контейнер в коллекции? J>Так навскидку похоже на поведение хэш-таблицы — в одном случае (когда кончается память) происходит слишком широкое перераспределение, а в другом (с тормозами) его не происходит, но в корзинке образуется много коллизий и поиск внутри корзинки начинает тормозить. По идее, это и является критерием для перераспределения, непонятно, почему его не происходит, особенно если хэш-функция одна и та же и реализация таблицы (т.е. параметры, управляющие перераспределением) тоже одна и та же. Но если и то, и другое разное на разных платформах, это может быть причиной.
Код выполняется абсолютно один и тот же на всех платформах. Если бы на одной было перераспределение, то и на других оно бы было тоже.
Rowset не использует хэш-таблицы. Там ничего сложнее векторов нет. Правда код там запутанный. Сразу идти и анализировать код с надеждой наткнуться на причину было бы бесполезно.
Здравствуйте, valaar, Вы писали:
V>Как недавно были убедился, но отсутствие утечек памяти не говорит, что с памятью всё в порядке. Была ситуация, когда всё работает отлично, НО при завершении работы, когда идёт всеобщая чистка, примерно в одном случае из пяти вываливалось предупреждение о записи в уже освобождённую ранее память кучи, при этом стек мог указывать на любое место от деструкторов std коллекций до вызова функции с cdcdcdcd данными. Для повышения вероятности появления ошибки поток данных надо было довести до нескольких сотен тысяч записей.
Прострелов по памяти не оказалось. На платформе S, заменили malloc/free на slab аллокатор с отладочными опциями. Ни утечек, ни прострелов. Однако, эффект out-of-memory пропал...
Здравствуйте, alexeiz, Вы писали:
A>Здравствуйте, valaar, Вы писали:
V>>Как недавно были убедился, но отсутствие утечек памяти не говорит, что с памятью всё в порядке. Была ситуация, когда всё работает отлично, НО при завершении работы, когда идёт всеобщая чистка, примерно в одном случае из пяти вываливалось предупреждение о записи в уже освобождённую ранее память кучи, при этом стек мог указывать на любое место от деструкторов std коллекций до вызова функции с cdcdcdcd данными. Для повышения вероятности появления ошибки поток данных надо было довести до нескольких сотен тысяч записей.
A>Прострелов по памяти не оказалось. На платформе S, заменили malloc/free на slab аллокатор с отладочными опциями. Ни утечек, ни прострелов. Однако, эффект out-of-memory пропал...
Фрагментацию памяти смотрели?
Только не спрашивайте как
Что за платформа хоть? если Linux то там valgrind есть.
Я бы еще с версиями STL поигрался бы. Бывают всякие эффекты.
Здравствуйте, Sheridan, Вы писали:
S>Приветствую, valaar, вы писали:
v>> , где я два раза умудрялся вызвать delete. S>Полезно всетаки после delete указатель в NULL сбрасывать.
Так делают те "админы", у кого утечки памяти и двойное удаление — постоянная головная боль, которую они пытаются уменьшить с помощью таких "полезных" приемов. Ирония в том, что после сбрасывания указателя в NULL, его повторное (и ошибочное) удаление пройдёт абсолютно незамеченным, тем самым закапывая баг в программе, который приводит к этому двойному удалению, еще глубже.
Приветствую, alexeiz, вы писали:
a> Так делают те "админы", у кого утечки памяти и двойное удаление — постоянная головная боль, которую они пытаются уменьшить с помощью таких "полезных" приемов. Ирония в том, что после сбрасывания указателя в NULL, его повторное (и ошибочное) удаление пройдёт абсолютно незамеченным, тем самым закапывая баг в программе, который приводит к этому двойному удалению, еще глубже.
Здравствуйте, alexeiz, Вы писали:
A>Код выполняется абсолютно один и тот же на всех платформах.
ну и что, это не делает его платформо независимым.
A>Rowset не использует хэш-таблицы. Там ничего сложнее векторов нет. A>Правда код там запутанный. Сразу идти и анализировать код с надеждой наткнуться на причину было бы бесполезно.
т.е. свой код мы не смотрим, а сразу просим разобраться RSDN!
при этам ведем себя как партизан. Ни как устроен Rowset, ни что за платформы...
A>>Rowset не использует хэш-таблицы. Там ничего сложнее векторов нет. A>>Правда код там запутанный. Сразу идти и анализировать код с надеждой наткнуться на причину было бы бесполезно.
СМ>т.е. свой код мы не смотрим, а сразу просим разобраться RSDN!
СМ>при этам ведем себя как партизан. Ни как устроен Rowset, ни что за платформы...
в первом сообщении автор же написал "Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера."
то есть ошибка уже найдена и устранена, но предлагает подумать и предложить версии, что могло быть причиной
Здравствуйте, valaar, Вы писали:
V>в первом сообщении автор же написал "Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера." V>то есть ошибка уже найдена и устранена, но предлагает подумать и предложить версии, что могло быть причиной
вы вообще понимаете, что нам НИЧЕГО не предложили. Как можно искать алгоритмическую ошибку не зная, даже примерно, алгоритма?
И как алгоритм может зависеть от платформы (хотя выбор алгоритма может)? Ошибка в реализации алгоритма.
т.е. если помочь человеку или нельзя или поздно (раз сам решил). Жаль время.
Здравствуйте, alexeiz, Вы писали:
A>Поискали утечки памяти. Вроде все нормально, утечек нет. Да и потом, как так может быть, что утечки есть только на одной платформе, а на других этот же код выполняется без утечек?
A>Внимание, вопрос: в чем может быть проблема и как ее искать?
MALLOC_OPTIONS=KK ?
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, alexeiz, Вы писали:
A>Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера.
A>Есть класс (C++), представляющий из себя коллекцию некоторых записей. Назовем его Rowset....
A>Внимание, вопрос: в чем может быть проблема и как ее искать?
"Дядя, а я знаю что у вас сломалось"
В программе, в чем же еще может быть проблема.
Я у себя (в страничном кэше с поддержкой многопоточного доступа) похожие тормоза искал с помощью тестов. Нашел линейней поиск в списке грязных страниц, переделал его на поиск через хеш — все стало "как у взрослых"
Искал очень долго ....
-- Пользователи не приняли программу. Всех пришлось уничтожить. --
Здравствуйте, Коваленко Дмитрий, Вы писали:
КД>"Дядя, а я знаю что у вас сломалось"
КД>Я у себя (в страничном кэше с поддержкой многопоточного доступа) похожие тормоза искал с помощью тестов. Нашел линейней поиск в списке грязных страниц, переделал его на поиск через хеш — все стало "как у взрослых"
это не объясняет разное поведение на различных платформах.
Здравствуйте, Сергей Мухин, Вы писали:
СМ>Здравствуйте, valaar, Вы писали:
V>>в первом сообщении автор же написал "Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера." V>>то есть ошибка уже найдена и устранена, но предлагает подумать и предложить версии, что могло быть причиной
СМ>вы вообще понимаете, что нам НИЧЕГО не предложили. Как можно искать алгоритмическую ошибку не зная, даже примерно, алгоритма? СМ>И как алгоритм может зависеть от платформы (хотя выбор алгоритма может)? Ошибка в реализации алгоритма.
СМ>т.е. если помочь человеку или нельзя или поздно (раз сам решил). Жаль время.
Во-первых, пока автор поступал честно. Надеюсь, что правильный ответ через некоторое время тоже сообщит.
Во-вторых, вопрос был не только "в чём может быть ошибка?", но и "как её искать?". Высказывайте свои версии и возможные инструменты, автор подсказывал как они будут себя вести. В чём-то похоже на текстовое adventure, где есть некоторое описание, а на возможные действия идёт различная реакция.
В-третьих, все уже обращали внимание, что "результат зависит от платформы". Хотя ошибка и была в алгоритме, но почему вела себя по-разному? Здесь алгоритм вообще можно рассматривать как чёрный ящик. Автор упомянул, что это коллекция, потому что без этого поведение по добавлению малого числа записей и большого было бы сложно описать. Бросаться сразу в отладчик и исходники можно, но это путь "грубой силы".
Здравствуйте, alexeiz, Вы писали:
A>Столкнулся недавно с интересной проблемой, которая себя очень странно проявляла, но в конце концов оказалась следствием ошибки алгоритмического характера.
... A>Внимание, вопрос: в чем может быть проблема и как ее искать?
Верно ли что (просьба уточнить):
а) Исходный код на C++ для каждой из платформ (S, L, A, H) компилировался отдельно своим компилятором?
б) Среди платформ L, A, H была платформа той же разрядности, что и платформа S?
в) Специфика платформ не использовалась? (Например, IOCP под windows.)
г) Использовались ли какие-нибудь мультиплатформенные (например, boost) библиотеки, которые могли внутри себя использовать специфику платформ?
Здравствуйте, Сергей Мухин, Вы писали:
КД>>Я у себя (в страничном кэше с поддержкой многопоточного доступа) похожие тормоза искал с помощью тестов. Нашел линейней поиск в списке грязных страниц, переделал его на поиск через хеш — все стало "как у взрослых"
СМ>это не объясняет разное поведение на различных платформах.
Ну, были еще (конкретные) проблемы с STL. Бинарник из под BCB5 летал (Rogue Wave STL?). А из под VS2005-2008 (думаю и с 2010 было бы тоже самое) — еле ползал. Особенно это было видно в многопоточной программе.
Проблема оказалась в std::locale.
Пусть поиграется с разными компиляторами/базовыми библиотеками. Может локализует причину
Один черт — нужны тесты, с демонстрацией стабильной деградации производительности.
-- Пользователи не приняли программу. Всех пришлось уничтожить. --
Здравствуйте, valaar, Вы писали:
V>Верно ли что (просьба уточнить): V>а) Исходный код на C++ для каждой из платформ (S, L, A, H) компилировался отдельно своим компилятором?
На каждой — свой компилятор. S — Solaris/SunCC, L — Linux/GCC, A — AIX/xlC, H — HPUX/aCC.
V>б) Среди платформ L, A, H была платформа той же разрядности, что и платформа S?
Той-же.
V>в) Специфика платформ не использовалась? (Например, IOCP под windows.)
Нет.
V>г) Использовались ли какие-нибудь мультиплатформенные (например, boost) библиотеки, которые могли внутри себя использовать специфику платформ?
Нет. Конечно, у нас есть платформно зависимые библиотеки. Но можно точно сказать, что они там не были задействованы.
Здравствуйте, minorlogic, Вы писали:
M>Тогда и вы скажите , что лежит у меня в кармане ?
M>Другими словами о чем тут думать если нет вводной даже о используемом контейнере ?
Об контейнерах, используемых в этом Rowset'е, я знал на тот момент не больше вашего
Здравствуйте, Сергей Мухин, Вы писали:
СМ>вы вообще понимаете, что нам НИЧЕГО не предложили. Как можно искать алгоритмическую ошибку не зная, даже примерно, алгоритма? СМ>И как алгоритм может зависеть от платформы (хотя выбор алгоритма может)? Ошибка в реализации алгоритма.
Алгоритм не зависит от платформы. Но ошибка в нем проявляется по разному на разных платформах. Вот так иногда бывает.
Здравствуйте, alpha21264, Вы писали:
A>Фрагментацию памяти смотрели? A>Только не спрашивайте как
Так как замена системного менеджера памяти перестает приводить к исчерпанию памяти, то это точно фрагментация. Осталось только найти из-за чего. Как здесь уже посоветовали, каждую аллокацию/деаллокацию записываем в лог. Большой лог получается, 150MB.
Но теперь мы уже не зависим от Rowset и его деталей реализации. Это важный момент. В коде Rowset можно было копаться долго и очень долго.
Проблему можно воспроизвести, проигрывая этот лог. Чем я и хотел заняться следующим делом. Но сначала я полез в него посмотреть, есть ли какой-нибудь цикличеки повторяющийся фрагмент. И он там сразу нашелся в самом начале лога. Около 30 аллокаций/деаллокаций — ничего серьезного. Было трудно поверить, что это и создает злодейскую фрагментацию памяти. Я уже начал писать простенький код, чтобы этот цикл прогонять энное количество раз. Но потом зачем-то полез в конец лога. И там обнаружилось...
alloc 399996
free 399992
... 30 alloc/free, что и в начале
alloc 400000
free 399996
... 30 alloc/free
и так далее
Ну, вот почти и все. Осталось только догадаться, чем в стандартной библиотеке можно создать такой pattern, и почему этот код очень сильно замедлялся на всех остальных платформах, где не наблюдалось фрагментации памяти.
Здравствуйте, alexeiz, Вы писали:
A>Здравствуйте, minorlogic, Вы писали:
M>>Тогда и вы скажите , что лежит у меня в кармане ?
M>>Другими словами о чем тут думать если нет вводной даже о используемом контейнере ?
A>Об контейнерах, используемых в этом Rowset'е, я знал на тот момент не больше вашего
Тогда откуда предположение что проблема в реализации Rowset?
Здравствуйте, alexeiz, Вы писали: A>alloc 399996 A>free 399992 A>... 30 alloc/free, что и в начале A>alloc 400000 A>free 399996 A>... 30 alloc/free A>и так далее A>Ну, вот почти и все. Осталось только догадаться, чем в стандартной библиотеке можно создать такой pattern, и почему этот код очень сильно замедлялся на всех остальных платформах, где не наблюдалось фрагментации памяти.
Была мысль о vector, который в обычно реализации может привести к троекратному перерасходу памяти. Но этого мало, да и не тормозило бы. А вот если в коде используется «оптимизация» (автор вероятно хотел «сэкономить» память), перед добавлением каждого элемента вызывается reserve(size()+1), то получим как раз указанное поведение. Мало того, что оно тормозит на любой платформе, постоянно переаллоцируя и копируя память, так ещё и на одних оно нагружает менеджер кучи дефрагментацией, а на других — валит с перерасходом фрагментированной неиспользуемой памяти.
Может и без reserve, а просто каждый раз создаётся новый вектор, ещё хуже. Может даже не вектор, а wstring.
Здравствуйте, alexeiz, Вы писали:
A>>Фрагментацию памяти смотрели? A>>Только не спрашивайте как
A>Так как замена системного менеджера памяти перестает приводить к исчерпанию памяти, то это точно фрагментация. Осталось только найти из-за чего. Как здесь уже посоветовали, каждую аллокацию/деаллокацию записываем в лог. Большой лог получается, 150MB.
A>Но теперь мы уже не зависим от Rowset и его деталей реализации. Это важный момент. В коде Rowset можно было копаться долго и очень долго.
A>Проблему можно воспроизвести, проигрывая этот лог. Чем я и хотел заняться следующим делом. Но сначала я полез в него посмотреть, есть ли какой-нибудь цикличеки повторяющийся фрагмент. И он там сразу нашелся в самом начале лога. Около 30 аллокаций/деаллокаций — ничего серьезного. Было трудно поверить, что это и создает злодейскую фрагментацию памяти. Я уже начал писать простенький код, чтобы этот цикл прогонять энное количество раз. Но потом зачем-то полез в конец лога. И там обнаружилось...
Здравствуйте, gegMOPO4, Вы писали:
MOP>Была мысль о vector, который в обычно реализации может привести к троекратному перерасходу памяти. Но этого мало, да и не тормозило бы. А вот если в коде используется «оптимизация» (автор вероятно хотел «сэкономить» память), перед добавлением каждого элемента вызывается reserve(size()+1), то получим как раз указанное поведение. Мало того, что оно тормозит на любой платформе, постоянно переаллоцируя и копируя память, так ещё и на одних оно нагружает менеджер кучи дефрагментацией, а на других — валит с перерасходом фрагментированной неиспользуемой памяти.
Так и есть . Хотя, причина была не в желании съэкономить память, а в написании exception-safe кода, и reserve(size() + 1) был завуалирован в reserve(size() + numberOfRows), где numberOfRows всегда равнялось 1.
. Хотя, причина была не в желании съэкономить память, а в написании exception-safe кода, и reserve(size() + 1) был завуалирован в reserve(size() + numberOfRows), где numberOfRows всегда равнялось 1.
