Более быстрый алгоритм выделения и освобождения памяти, чем при использовании метода нескольких списков

Question

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

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

Для удаления критического сечения мы назначаем свободный список для каждого потока, т. Е. Локальное хранилище потока .Тем не менее, поток T1 всегда блокирует память, а поток T2 всегда освобождает их, поэтому свободный список в потоке T2 всегда увеличивается, в то время как свободный список не дает никаких преимуществ.

Несмотря на узкое место в критическом разделе, мы принимаемСнова критический раздел, с другим методом.Мы готовим несколько свободных списков, а также критические разделы, которые назначаются каждому свободному списку, таким образом, 0 ~ N-1 свободных списков и 0 ~ N-1 критических разделов.Мы готовим целочисленное значение с атомарным управлением, которое изменяется на 0, 1, 2, ... N-1, затем на 0, 1, 2, ... снова.Для каждого выделения и освобождения мы получаем целочисленное значение X, затем изменяем его, получаем доступ к X-му критическому разделу, а затем к X-му свободному списку.Однако это намного медленнее, чем в предыдущем методе (с использованием локального хранилища потоков).Атомарная операция довольно медленная, так как есть больше потоков.

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

Вместо целочисленного значения мы использовали идентификатор потока с хэшированием в диапазоне (0 ~ N-1), затем производительность стала лучше,

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

Answer 1

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

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

Допустим, у вас есть T потоков, все они резервируют и освобождают память. Основная цель - скорость, поэтому я постараюсь не использовать ни TLS, ни критические блокировки, ни атомарные операции.

Если (повторите: если, если, если), приложение может соответствовать нескольким разным размерам блоков памяти (не случайным размерам, чтобы избежать фрагментации и ненужных дыр), тогда начните запрашивать у ОС количество таких дискретных блоков .

Например, у вас есть массив n1 блоков каждого размера size1, массив n2 блоков каждого размера size2, массив n3 ... и так далее. Каждый массив является двумерным, второе поле просто хранит флаг для используемого / свободного блока. Если ваши массивы очень велики, то лучше использовать выделенный массив для флагов (поскольку непрерывное использование памяти всегда быстрее).

Теперь кто-то просит блок памяти размером sB. Специализированная функция (или объект или что-то еще) ищет массив блоков размером больше или равным sB, а затем выбирает блок, просматривая флаг used / free. Непосредственно перед завершением этой задачи правильный флаг блока устанавливается на «используется».

Когда два или более потоков запрашивают блоки одинакового размера, флаг может быть поврежден. Использование TLS решит эту проблему, а также критическую блокировку. Я думаю, вы можете установить флаг bool в начале поиска в flags-array, который заставит другие потоки ждать, пока флаг не изменится, что происходит только после изменения флага блока. С псевдокодом:

MemoryGetter(sB)
{
    //select which array depending of 'sB'
    for (i=0, i < numOfarrays, i++)
        if (sizeOfArr(i) >= sB)
           arrMatch = i
           break //exit for

    //wait if other thread wants a block from the same arrMatch array
    while ( searching(arrMatch) == true )
        ; //wait
    //blocks other threads wanting a block from the same arrMatch array
    searching(arrMatch) = true

    //Get the first free block
    for (i=0, i < numOfBlocks, i++)
        if ( arrOfUsed(arrMatch, i) != true )
           selectedBlock = addressOf(....)
           //mark the block as used
           arrOfUsed(arrMatch, i) = true
           break; //exit for

     //Allow other threads
     searching(arrMatch) = false

     return selectedBlock  //NOTE: selectedBlock==NULL means no free block
}

Освободить блок проще, просто отметьте его как свободный, без проблем с параллелизмом потоков.

Работа без свободных блоков зависит от вас (подождите, используйте больший блок, попросите у ОС больше и т. Д.).

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

Если эта идея сделает ваше приложение быстрее, дайте мне знать. Что я могу сказать наверняка, так это то, что используемая память больше, чем если бы вы использовали обычный запрос ОС; но не очень, если вы выбираете «хорошие» размеры, те, которые наиболее часто используются.

Некоторые улучшения могут быть сделаны:

• Кэшировать последний освобожденный блок (по размеру), чтобы избежать поиска.
• Начните с небольшого количества блоков и попросите у ОС только больше памяти при необходимости. Играть с «количеством блоков» для каждого размера в зависимости от ваше приложение. Найдите оптимальный случай.