Могу ли я выделить память быстрее, используя несколько потоков?

Question

Если я создаю цикл, который резервирует целочисленные массивы 1 КБ, int [1024], и я хочу, чтобы он выделил 10000 массивов, могу ли я сделать это быстрее, запустив выделение памяти из нескольких потоков?

Я хочуих должно быть в куче.

Давайте предположим, что у меня есть многоядерный процессор для работы.

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

Зависит ли ответ от ОС?пожалуйста, скажите мне, как это работает на разных платформах, если так.

Редактировать:

Цикл выделения целочисленных массивов был просто упрощенным примером.Не говорите мне, как я могу это улучшить.

Answer 1

Это зависит от многих вещей, но в первую очередь:

• ОС
• Реализация malloc вы используете

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

Теперь реализация по умолчанию malloc в целом консервативна, ибудет просто иметь гигантский замок вокруг всего этого.Это означает, что запросы обрабатываются последовательно, и единственное, что делает выделение из нескольких потоков вместо одного, это замедляет все это.

Существуют более умные схемы распределения, обычно основанные на пулах, и они могут бытьв других реализациях malloc: tcmalloc (от Google) и jemalloc (используется Facebook) - две такие реализации, предназначенные для высокопроизводительной работы в многопоточных приложениях.

Серебряной пули неттем не менее, в какой-то момент ОС должна выполнить виртуальный <=> реальный перевод, который требует некоторой формы блокировки.

Лучше всего распределить по аренам:

• Распределить большиекуски (арены) сразу
• Разделите их на массивы соответствующего размера

Нет необходимости распараллеливать распределение арены, и вам лучше попроситьсамые большие арены, которые вы можете (имейте в виду, что запросы на выделение слишком большого количества могут потерпеть неудачу), тогда вы можете распараллелитьsplit.

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

Answer 2

Я думаю, что, возможно, вам нужно скорректировать свои ожидания от многопоточности.

Основным преимуществом многопоточности является то, что вы можете выполнять задачи асинхронно, то есть в parallel. В вашем случае, когда вашему главному потоку требуется больше памяти, не имеет значения, выделена ли она другим потоком - вам все равно нужно остановиться и дождаться завершения выделения, поэтому здесь есть no parallelism. Кроме того, существует поток служебных данных, сигнализирующих потоку о завершении, а другой ожидает завершения, что может привести к снижению производительности. Кроме того, если вы запускаете поток каждый раз, когда вам нужно распределение, это накладные расходы huge. Если нет, вам нужен какой-то механизм для передачи запроса на выделение и ответа между потоками, своего рода очередь задач, которая опять-таки является дополнительной нагрузкой без усиления.

Другой подход может заключаться в том, что поток распределения выполняется вперед и pre-allocates памяти, которая вам нужна will. Это может дать вам реальную выгоду, но если вы делаете предварительное распределение, вы можете сделать это в основном потоке, что будет проще. Например. выделите 10M за один снимок (или 10 раз по 1M, или столько смежной памяти, сколько сможете) и получите массив из 10 000 указателей, указывающих на него с 1024 смещениями, представляющими ваши массивы Если вам не нужно освобождать их независимо друг от друга, это кажется намного проще и может быть даже более эффективным, чем использование многопоточности.

Answer 3

Ответ зависит от подпрограммы выделения памяти, которая является комбинацией уровня библиотеки C ++ operator new, возможно, обернутого вокруг libC malloc(), который, в свою очередь, иногда вызывает функцию ОС, такую ​​как sbreak().Характеристики реализации и производительности всего этого не определены и могут варьироваться в зависимости от версии компилятора, с флагами компилятора, разными версиями ОС, разными ОС и т. Д. Если профилирование показывает, что оно медленнее, то это нижняя строка.Вы можете попытаться изменить количество потоков, но, вероятно, происходит то, что все потоки пытаются получить одну и ту же блокировку, чтобы изменить кучу ... накладные расходы, связанные с высказыванием «хорошо, поток Х получает следующий шаг вперед»и "нить Х здесь, я закончил" - просто трата времени.Другая среда C ++ может в конечном итоге использовать атомарные операции, чтобы избежать блокировки, которая может или не может оказаться быстрее ... нет общего правила.

Если вы хотите выполнить быстрее, рассмотрите возможность выделения одного массива из 10000 * 1024 дюймов,затем используя различные его части (например, [0]..[1023], [1024]..[2047] ...).

Answer 4

Что касается glibc, он имеет арену (см. здесь ), который имеет блокировку на арену.

Вы также можете рассмотреть tcmalloc от google (расшифровывается как Thread-Caching malloc), который показывает 30% повышение производительности для многопоточных приложений.Мы используем это в нашем проекте.В режиме отладки он даже может обнаружить некоторое неправильное использование памяти (например, новое / свободное несоответствие)

Answer 5

Если массивы принадлежат друг другу и будут освобождены только как единое целое, вы можете просто выделить массив из 10000 * 1024 дюймов, а затем сделать так, чтобы ваши отдельные массивы указывали на него.Просто помните, что вы не можете delete маленькие массивы, только целые.

int *all_arrays = new int[1024 * 10000];
int *small_array123 = all_arrays + 1024 * 123;

Таким образом, у вас есть маленькие массивы, когда вы заменяете 123 числом от 0 до 9999.

Answer 6

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

Как правило, у вас будет две версии среды выполнения: многопоточная версия и однопоточная версия.

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

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

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

Answer 7

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

Answer 8

Насколько я знаю, все ОС имеют неявную блокировку мьютекса внутри системного вызова динамического размещения (malloc ...).Если вы подумаете об этом, если вы не заблокируете это действие, вы можете столкнуться с ужасными проблемами.

Вы можете использовать многопоточные строительные блоки API-потоков http://threadingbuildingblocks.org/, которые имеют многопоточный дружественный масштабируемый распределитель.

Но я думаю, что лучшей идеей должно быть выделение всей памяти один раз (должно работать довольно быстро) и разделение ее на свои собственные.Я думаю, что tbb allocator делает что-то подобное.

Сделайте что-то вроде

new int [1024 * 10000] и затем назначьте части 1024ints вашему массиву указателей или тому, что вы когда-либо используете.

Ты понимаешь?