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

Question

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

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

Все работает как положено, но по какой-то причине цикл for, фактически выделяющий строки моей матрицы, имеет странную пиковую производительность при работе только с 3 потоками. С этого момента добавление еще нескольких потоков просто увеличивает продолжительность цикла. С 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 (что, я полагаю, является тем, что фактически вызывает метод resize класса векторного шаблона) в многопоточной среде? Я нашел несколько статей, в которых говорится о потере производительности при освобождении пространства кучи в многопоточном окружении, но ничего конкретного о выделении нового пространства, как в этом случае, нет.

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

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

Answer 1

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

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

2. malloc выделяет адресное пространство.Поэтому, когда вы действительно начинаете касаться выделенной памяти, вы проходите через «программную ошибку страницы», которая является ошибкой страницы, которая позволяет ядру ОС выделять резервную память для выделенного адресного пространства.Это может быть дорого из-за отключения ядра и потребовать от ядра некоторых глобальных блокировок для доступа к его собственным структурам данных глобальных ресурсов ОЗУ.

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

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

Answer 2

Распределители памяти - определенно возможный конфликт для нескольких потоков.

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

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

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

Answer 3

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

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

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