Производительность Malloc в многопоточной среде

Я экспериментировал с картой openmp и обнаружил некоторые нечетные результаты. Я не уверен, что знаю, как объяснить.

Моя цель - создать эту огромную матрицу, а затем заполнить ее значениями. Я сделал некоторые части своего кода как параллельные петли, чтобы получить производительность из моей многопоточной среды. Я запускаю это на машине с двумя четырехъядерными процессорами xeon, поэтому я могу безопасно разместить до 8 параллельных потоков.

Все работает так, как ожидалось, но по какой-то причине цикл for, фактически выделяющий строки моей матрицы, имеет нечетную максимальную производительность при работе только с тремя потоками. Оттуда добавление нескольких потоков просто заставляет мой цикл занимать больше времени. С 8 потоками, занимающими фактически больше времени, которое понадобится только одному.

Это мой параллельный цикл:

 int width = 11;
 int height = 39916800;
 vector<vector<int> > matrix;
 matrix.resize(height);    
 #pragma omp parallel shared(matrix,width,height) private(i) num_threads(3)
 {
   #pragma omp for schedule(dynamic,chunk)
   for(i = 0; i < height; i++){
     matrix[i].resize(width);
   }
 } /* End of parallel block */

Это заставило меня задуматься: существует ли известная проблема с производительностью при вызове malloc (как я полагаю, это метод изменения размера класса векторного шаблона на самом деле) в многопоточной среде? Я нашел несколько статей, говорящих о потерях производительности при освобождении пространства кучи в мутированной среде, но ничего конкретного о распределении нового пространства, как в этом случае.

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

Оба раза, когда измеряется с помощью функции gettimeofday и, похоже, возвращают очень похожие и точные результаты в разных экземплярах исполнения. Итак, у кого есть хорошее объяснение?

Ответ 1

Вы правы относительно vector:: resize(), внутренне вызывающего malloc. Реализация-miseoc довольно сложна. Я вижу несколько мест, где malloc может привести к конфликту в многопоточной среде.

malloc, вероятно, сохраняет глобальную структуру данных в пользовательском пространстве для управления адресным пространством кучи пользователя. Эта глобальная структура данных должна быть защищена от одновременного доступа и модификации. У некоторых распределителей есть оптимизация, чтобы уменьшить количество обращений к этой глобальной структуре данных... Я не знаю, как далеко продвинулся Ubuntu.
malloc выделяет адресное пространство. Поэтому, когда вы на самом деле начинаете касаться выделенной памяти, вы будете проходить через "ошибку софт-страницы", которая является ошибкой страницы, которая позволяет ядру ОС выделять оперативную память для выделенного адресного пространства. Это может быть дорогостоящим из-за поездки в ядро и потребует, чтобы ядро взяло некоторые глобальные блокировки для доступа к своим собственным глобальным структурам данных ресурсов RAM.
пользовательский пространственный распределитель, вероятно, удерживает некоторое выделенное пространство для выдачи новых распределений. Однако, как только эти выделения будут исчерпаны, распределителю необходимо будет вернуться к ядру и выделить еще некоторое адресное пространство из ядра. Это также дорого и потребует поездки в ядро, а ядро, использующее некоторые глобальные блокировки, для доступа к своим структурам, связанным с глобальным адресным пространством.

Внизу, эти взаимодействия могут быть довольно сложными. Если вы столкнетесь с этими узкими местами, я бы предположил, что вы просто "предварительно распределите" свою память. Это будет связано с распределением его и последующим касанием всего этого (все из одного потока), чтобы вы могли использовать эту память позже из всех своих потоков, не запускаясь в конфликте блокировок на уровне пользователя или ядра.

Ответ 2

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

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

Типичные реализации malloc, входящие в состав gcc и других компиляторов, используют общую глобальную блокировку и достаточно хорошо работают по потокам, если давление распределения памяти относительно невелико. Однако выше определенного уровня распределения потоки начнут сериализоваться при блокировке, вы получите чрезмерное переключение контекста и кеширование, а производительность ухудшится. Ваша программа является примером чего-то тяжелого распределения, с alloc + dealloc во внутреннем цикле.

Я удивлен, что компилятор, совместимый с OpenMP, не имеет лучшей реализации malloc с резьбой? Они, безусловно, существуют - посмотрите на этот вопрос для списка.

Ответ 3

Технически STL vector использует std::allocator, который в итоге вызывает new. new, в свою очередь, вызывает libc malloc (для вашей системы Linux).

Эта реализация malloc довольно эффективна как универсальный распределитель, является потокобезопасной, однако она не масштабируема (GNU libc malloc происходит от Doug Lea dlmalloc). Существует множество распределителей и документов, которые улучшают dlmalloc для обеспечения масштабируемого распределения.

Я бы посоветовал вам взглянуть на Hoard от доктора Эмери Бергера, tcmalloc от Google и Intel Threading Building Blocks масштабируемый распределитель.