Удаление больших хеш-карт с миллионами строк в одном потоке влияет на производительность в другом потоке

Question

Итак, у меня есть эта программа на C ++, которая в основном анализирует файлы гигантских наборов данных и загружает содержимое в hashmap в памяти ( эта часть регулируется в главном потоке , поэтому она никогда не изо всех сил старается заняться гигантский кусок времени). И когда это будет сделано, я щелкнул указателем на новую ячейку памяти и вызвал delete на старой. Помимо этого, программа выполняет сопоставление входящих запросов, просматривая содержимое в карте памяти (в основном потоке). Предположим, что эти гигантские карты заключены в класс Evaluator:

Evaluator* oldEvaluator = mEvaluator;
Evaluator* newEvaluator = parseDataSet();
mEvaluator = newEvaluator;
delete oldEvaluator;

//And then on request processing:
mEvaluator.lookup(request)

Карта может содержать миллионы строковых объектов в виде ключей . Это обычные строки, которые могут быть атрибутами запроса, такими как ip, UserAgent и т. Д. c, но каждая из них является строковым объектом, вставленным в STL unordered_map.

Набор данных периодически обновляется, но большую часть времени программа просто выполняйте сопоставление атрибута запроса с набором данных в памяти, и это нормально и эффективно, без ошибок, за исключением случаев, когда происходит массовое потребление нового набора данных. Альтернативный способ использования этого большого набора данных состоит в том, чтобы использовать потоковую передачу , но это относительно долгосрочные решения.

Раньше это была однопоточная программа, использующая модель, управляемую событиями, но каждый раз полная новый набор помещается и вызывается уничтожение, удаление всего этого заняло слишком много времени и, следовательно, блокирует обработку запроса.

Поэтому я поместил удаление такой карты в отдельный поток . Проблема в том, что теперь удаление и обработка запросов, по-видимому, происходят одновременно. Я вижу очень заметное замедление c в потоке обработки запросов.

Конечно, на хосте выполняются другие процессы, и я ожидаю, что 2 потока, чтобы конкурировать за циклы процессора. Но я не ожидал увидеть замедление drasti c при потоке соответствия запроса. В среднем запрос должен обрабатываться на уровне 500 мкс, но во время работы потока удаления он обрабатывался всего за 5 мс. Иногда процессор прерывает соответствующий поток (потому что он занимал слишком много времени), он может go длиться 50 мс, или 120 мс, и т.д. c. В крайних случаях запрос может быть обработан на все 1000 мс, то есть примерно на то время, которое удаление всей структуры данных занимает другой поток.

Каков наилучший способ узнать причину такого root помедленнее? Это больше узкое место пропускной способности процессора или памяти ? Я представлял себе, что если поместить его в отдельный поток, мне все равно, насколько медленным он будет, потому что он должен удалять строковые объекты один за другим, поэтому я не ожидал, что это повлияет на другой поток ...

РЕДАКТИРОВАТЬ : Благодаря паре комментариев / ответов, кажется, уже указываются несколько возможных причин:

1. Фрагментация памяти . Потому что менее часто посещаемая строка хранится в более дорогих местах памяти (так что отсутствует кеш), или потому что она хранится в unordered_map со многими указателями, или потому что система выполняет сжатие памяти, удаляя дыры повсюду? Но почему именно это влияет на медлительность в другом потоке?
2. В одном комментарии упоминается, что это конфликт кучи из-за поточно-безопасной блокировки ? Таким образом, вся куча для этой программы блокируется, потому что один поток занят удалением дыр, которые мешают другому получить доступ к памяти кучи? Просто для пояснения, программа намеренно никогда не распределяет материал и не освобождает другие одновременно, и у нее есть только 2 потока, один из которых предназначен только для удаления.

Так что же мне тогда делать? Я пробовал Jemalloc, но не уверен, что я использую его полностью правильно - кажется, включение -ljemalloc в строку компоновщика просто волшебным образом заменяет mallo c в lib c? Я пытался, без разницы в производительности, но я мог использовать его неправильно. Моя программа не выполняет никаких явных значений mallo c, все заранее new с неизвестным размером и подключена вместе с указателями и картами STL.

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

1. Как я могу точно определить причину вышеуказанных 2 проблем с памятью (какие-либо инструменты / метрики?)
2. Что я могу сделать, чтобы исправить это, не меняя модель потребления в потоковом режиме? Предполагая, что причинами root были вышеуказанные 2, кажется, что я должен сделать одну или обе вещи: 1) выделить все мои карты STL вместе с объектами из одного пула? Как я могу это сделать? 2) уменьшить конфликт кучи (я не знаю, решит ли Jemalloc что-либо из этого в моем случае)

Answer 1

Возможно, стоит сохранить только одну std::string для всех ваших данных и использовать std::string_view на карте. Это устраняет конфликты мьютексов, поскольку требуется только одно выделение памяти. string_view имеет тривиальный деструктор, поэтому вам не нужен поток для этого.

Я успешно использовал эту технику раньше, чтобы ускорить программу на 2500%, но это также потому, что эта техника уменьшила общее использование памяти.

Answer 2

Было бы замечательно, если бы вы воссоздали проблему, с которой вы столкнулись с MVCE , и показали это: вы знаете, часто проблема, о которой вы думаете, является вашей проблемой ... это не проблема.

Как я могу точно определить причину вышеуказанных проблем с памятью (какие-либо инструменты / метрики?)

Учитывая приведенную здесь информацию, я бы предложил использовать профилировщик - gprof (компилировать с -g -pg), являющийся базовым c. Если у вас есть компилятор Intel, вы можете использовать vtune.

Существует бесплатная версия vtune , но я лично использовал только коммерческую версию.

Кроме того, вы можете вставить тайминги в свой код: из текстового описания , не ясно, сопоставимо ли время заполнения карты со временем, необходимым для ее удаления, или оно постоянно увеличивается при параллельном запуске. Я бы начал с того, если. Обратите внимание, что текущая версия mallo c () значительно оптимизирована для параллелизма (это Linux? - добавьте тег к вопросу, пожалуйста).

Конечно, когда вы стираете карту, миллионы free() звонят по номеру std::~string() - но вы должны быть уверены, что это проблема или нет: вы можете использовать лучший подход (многие упомянутый в ответах / комментариях) или пользовательский распределитель, поддерживаемый огромным блоком памяти, который вы создаете / уничтожаете как единое целое.

Если вы предоставите MVCE в качестве отправной точки, я или другие смогут prov ie последовательный ответ (это еще не ответ - но слишком длинный, чтобы быть комментарием)

Просто чтобы прояснить, программа намеренно никогда не распределяет вещи и одновременно освобождает других и имеет только 2 потока, один из которых предназначен только для удаления.

Имейте в виду, что для каждой строки на карте требуется один (или больше) new и один delete (на основе malloc() и free() соответственно), являющиеся строками либо в ключах, либо в значениях.

Что у вас есть в «значениях» карты?

Поскольку у вас есть map<string,<set<int>>, у вас есть много выделений: каждый раз, когда вы выполняете map[string].insert(val) нового ключа, Ваш код неявно вызывает malloc() как для строки, так и для набора. Даже если ключ уже находится на карте, для нового int в наборе требуется выделить новый узел в наборе.

Таким образом, при построении структуры у вас действительно много выделений: ваша память очень фрагментирована. с одной стороны, и ваш код выглядит действительно «интенсивно малло c», что в принципе может привести к тому, что вызовы памяти будут голодать.

многопоточные выделения памяти / освобождения памяти

Одна особенность современной памяти Подсистемы, это то, что они оптимизированы для многоядерных систем: когда один поток выделяет память на одно ядро, это не глобальная блокировка, а локальная или локальная для ядра блокировка для локального пула потоков.

Это означает, что когда одному потоку нужно освободить память, выделенную другому, включается нелокальная (более медленная) блокировка.

Это означает, что наилучшим подходом является то, что каждый поток выделяет / освобождает собственную память Сказав, что в принципе вы можете оптимизировать много вашего кода с помощью структур данных, которые требуют меньшего количества malloc / free взаимодействий, ваш код будет более локальным по отношению к распределению памяти, если вы позволите каждому потоку:

• получить один блок данных
• построить map<string,<set<int>>
• освободить его

И у вас есть два потока, которые неоднократно выполняют эту задачу .

ПРИМЕЧАНИЕ. Для обработки параллельных вычислителей требуется оперативная память, но уже сейчас вы используете два из них, одновременно загруженных по схеме двойной буферизации (одно заполнение, одно очищение). Вы уверены, что ваша система не перезагружается из-за нехватки ОЗУ?

Кроме того, этот подход является масштабируемым: вы можете использовать столько потоков, сколько захотите. В вашем подходе вы были ограничены двумя потоками - один строил структуру, а другой разрушал ее.

Оптимизация

Без MVCE трудно давать указания. Только идеи, которые вы только знаете, можно ли применить в настоящее время:

• заменить набор отсортированным вектором, зарезервированным во время создания
• заменить ключи карты плоским вектором с равным интервалом , отсортированные строки
• хранят ключи строк последовательно в плоском векторе, добавляют хэши, чтобы отслеживать ключи карты. Добавьте карту ha sh, чтобы отслеживать порядок строк в векторе.

Answer 3

Вы можете попробовать использовать std::vector для хранения памяти. std::vector элементы хранятся непрерывно, так что это уменьшит пропадание кэша (см. Что такое "дружественный к кэшу" код? )

Таким образом, у вас будет map<???,size_t> вместо map<???,std::string> у вас будет еще одно перенаправление для получения вашей строки (что означает дополнительные затраты времени выполнения), но оно позволит вам выполнять итерации по всем строкам с меньшим отсутствием кэша.

Answer 4

Итак, благодаря всем приведенным ответам и комментариям, я не смог выбрать лучшее из-за того, что сама проблема была расплывчатой, и ни один единственный ответ не охватил все. Но я многому научился из этих ответов и, следовательно, проголосовал за большинство из них. Вот что я обнаружил после различных экспериментов: основные проблемы:

1. Причина, по которой медленная операция с потоком удаления влияет на другую. Учитывая, что он не выполняет malloc / deallo c одновременно в обоих потоках, не должно быть никаких разногласий в куче, а также общего ЦП или доступной памяти в узком месте, единственное правдоподобное объяснение осталось исчерпание пропускной способности памяти, Я нашел этот ответ на другой пост говорит: it's generally possible for a single core to saturate the memory bus if memory access is all it does. Все, что делает мой поток удаления, - это пересекает гигантскую карту и удаляет каждый элемент в ней, поэтому вполне возможно, что она насыщает шину памяти, так что другой поток, который делает и доступ к памяти, и другие вычисления резко замедляются. Далее я сосредоточусь на различных причинах, по которым это удаление может быть медленным

2. Карта гигантская , с миллионами элементов и сотнями мегабайт в размерах. Удаление каждого из них требует доступа к ним в первую очередь, и очевидно, что очень немногие могут поместиться в кэш L1 / L2 / L3. Так что тонна кеша пропускается и извлекается из ОЗУ .

3. Поскольку пара ответов / комментариев, упомянутых здесь, я храню std::string объектов на карте. Каждый выделен со своим собственным пространством и должен быть выбран и удален один за другим. Рекомендации от MSalters значительно улучшают производительность, сохраняя string_view в карте , сохраняя при этом фактический байтовый контент каждой строки в заранее выделенном блоке смежных блоков памяти. Теперь удаление миллиона объектов на карте становится почти тривиальным уничтожением string_view объектов, которые являются просто указателями, а уничтожение всего содержимого строки - уничтожением этого предварительно выделенного блока.

4. Я не упомянул в некоторых других частях программы, что я также храню другие объекты C ++ в других картах. И они также проблематичны c. Подобное «выравнивание» таких объектов C ++ необходимо, хотя и сложнее обойтись без готовых классов, таких как string_view. Идея в том, что если мы сможем хранить столько примитивных типов и указателей, сколько сможем , и помещать весь контент (большинство из них можно будет сводить к строкам) в смежные байтовые буферы. Цель состоит в том, чтобы все разрушить тривиально .

5. Наконец, оказывается, что сам контейнер с картами может быть довольно дорогостоящим для уничтожения, особенно когда он большой. Для основанных на узлах контейнеров std прохождение и удаление каждого дескриптора узла требует времени. Я обнаружил, что альтернативные реализации по-настоящему плоского хэш-карты сделают удаление намного быстрее . Примеры такой карты включают Abseil flat_hash_map и flat_hash_map * этого блоггера . Обратите внимание, что они оба настоящие hash_maps, хотя они плоские. flat_map Boost также можно удалить очень быстро, но это не настоящий hashMap, он поддерживается строго упорядоченным вектором, что делает вставку (когда мой ввод не упорядочен) чрезвычайно медленной.

Answer 5

это будет длинный ответ, потому что ваш вопрос очень сложный.

Процедура чтения

Когда вы читаете что-то, вы начинаете выделять память в своем приложении. Теперь это нормально в нормальном случае, когда вам не нужна производительность, там, где начинаются проблемы.

Карты STL являются красно-черными деревьями, поэтому они имеют много указателей, что означает, что каждый элемент выделяется / выделяется индивидуально, это создает ситуацию, когда пространство вашей памяти очень фрагментировано, и системе трудно освободить элементы эффективно. Причина: система должна следовать указателям.

Соответствующий контейнер

Карта STL объяснила: Почему std :: map реализован как красно-черный tree?

Вот базовая c дискуссия о поведении управления памятью карты. https://bytes.com/topic/c/answers/763319-stl-map-memory-management

Согласно вашему описанию, вы читаете массивный файл, который затем последовательно передаете кому-либо. Мой вопрос здесь заключается в том, могут ли данные храниться в виде STL-пары в непрерывной памяти, поскольку вы говорите, что должны их передавать?

Вам нужно искать там элементы? Если да, тогда вы должны выяснить, как часто или с какой периодичностью этот ответ скажет вам, является ли карта STL хорошим контейнером, поскольку она эффективна в поисковой деятельности.

Теперь в этой ссылке есть некоторые тесты о ссылочных контейнерах и контейнерах https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Идея состоит в том, что вы используете соответствующий контейнер, чтобы иметь правильное поведение при управлении памятью.

Есть ли какое-либо преимущество использования map for unordered_map в случае тривиальных ключей? Вот альтернатива вашей карте, которая может быть дешевым быстрым взломом, пока вы не разработаете более точное решение.

Управление памятью

Мой вопрос в вашей проблеме: можете ли вы очистить и повторно использовать свой контейнер? Так как освобождение контейнеров - дело дорогое.

Вы можете использовать кольцевой буфер карт STL, где: один читается -> один готов -> один написан Это было бы очень эффективно и могло бы дать вам преимущество, поскольку вы не должны освободить любые буферы, просто очистить после использования.

Редактировать: Вот ответ о фрагментации памяти, которая происходит во время частых удалений в контейнере. Что такое фрагментация памяти?

Ваша проблема в том, что вы используете строки, они могут расширять память, но под ними находятся mallocs из char. Теперь я не буду удалять вещи, а отмечать их неиспользованными или что-то еще.

Одна маленькая вещь, которая может помочь, если вы используете функцию резервного копирования строк при создании строк. Затем вы можете сказать 128, что означает 128 байт и потребляет немного памяти, но облегчит обработку фрагментации и упростит поведение перераспределения строки.

Теперь это также может быть совершенно бесполезным. Вам нужно профилировать свое приложение, чтобы увидеть, что происходит лучше всего, если вы находитесь на Linux.