О проекте

Простой (но очень эффективный) многопоточный аллокатор памяти, основанный на списках освобожденных блоков.
Лучше всего подходит для приложений, выделяющих много мелких (<256 байт) блоков памяти (что обычно происходит при активном использовании stl-контейнеров), и из множества одновременно работающих параллельных потоков.

Основные характеристики

• O(1) стоимость операций выделения/освобождения блоков памяти (для блоков размером <56KB)
• Низкая фрагментация
• Практически без накладных расходов для маленьких блоков (т.к. в блоках не хранится никакого заголовка или указателя, а используется один общий заголовок размером 64 байт для всех блоков внутри 64KБ чанка)
• Высокая производительность и очень хорошая масштабируемость (практически нет блокировок, в среднем не более одной спин-блокировки на 256 операций выделения/освобождения памяти, даже в случае, когда все блоки, выделенные в одном потоке, освобождаются в другом)

Введение

Практически каждый С++ программист слышал про возможность замены аллокаторов в stl-контейнерах, но практически никогда ей не пользовался. :)
И я также, как и многие, считаю, что данная возможность является практически непригодной в реальных крупных проектах, особенно когда при использовании сторонних С++ библиотек вдруг обнаруживается, что контейнеры с различными аллокаторами просто не совместимы друг с другом.
В конце концов, для чего вообще может понадобиться переопределять стандартный аллокатор памяти в контейнерах?
Я вообще не думаю, что контроль за выделением памяти должен быть на уровне контейнера - скорее на уровне размера блоков, которые выделяет этот контейнер (напр. все узлы map<int,int> выделять из единого пула). Или на уровне пары (размер, поток). Таким образом, основное преимущество специальных аллокаторов получается в том случае, когда они выделяют блоки одинакового размера (это касается аллокаторов на основе связанного списка освобожденных блоков, т.к. основанные на пулах специальные аллокаторы (когда освобождение делается сразу всех выделенных блоков за одну операцию) использовать сложнее в общем случае, и не всегда удобно). В противном случае, память, выделенная специальным аллокатором, не будет совместно использоваться (напр. когда используются различные контейнеры, но размер выделяемых блоков одинаковый), что приведёт к избыточному расходованию памяти, а также при использовании специализированных аллокаторов могут быть какие-то нюансы, связанные с многопоточностью. В конечном счете получается, что специализированные аллокаторы создают больше проблем, чем решают.
В итоге, я подумал, что если бы выбор соответствующего пула от размера блока можно было бы перенести на время компиляции, тогда единый на всё приложение глобальный аллокатор памяти смог бы полностью избавить от необходимости в специальных аллокаторах! Идея выглядит практически нереальной, но всё-таки я решил попробовать реализовать её.

Основные принципы проектирования

1. Встраивание функций и расчеты во время компиляции.

Код функций выделения памяти должен быть настолько мал, чтобы компилятор мог встроить его в место вызова (и чтобы это не приводило к значительному росту общего объема исполняемого файла). Дополнительно, это позволит часть вычислений произвести во время компиляции, если размер выделяемого блока известен заранее, как часто и бывает в С++ коде. А именно на основе размера выделяемого блока определяется к какой группе объектов он относится. Чтобы это было возможно, расчёты на основе размера должны быть достаточно просты и опираться только на встроенные функции компилятора (никаких asm-вставок или вызовов внешних функций), а также не должно быть обращений к рассчитанным данным в памяти, а только к константам. В конце концов, исходный код необходимо компилировать с включенной оптимизацией компоновщика (LTO - опция /GL для MSVC, -flto для GCC/Clang и -ipo для ICC), чтобы все обращения к оператору new встроились в место вызова. В качестве примера, ниже приводится результат компиляции выражения "new std::array<int, 10>":

NOINLINE void *test_function()
{
    return new std::array<int, 10>;
}

void *operator new(size_t size) { return ltalloc<true>(size); }
void *operator new(size_t size, const std::nothrow_t&) { return ltalloc<false>(size); }

template <bool throw_> static void *ltalloc(size_t size)
{
    unsigned int sizeClass = get_size_class(size); //рассчитывается на этапе компиляции
    ThreadCache *tc = &threadCache[sizeClass];
    FreeBlock *fb = tc->freeList;
    if (likely(fb))
    {
        tc->freeList = fb->next;
        tc->counter++;
        return fb;
    }
    else
        return fetch_from_central_cache<throw_>(size, tc, sizeClass);
}

mov         eax,dword ptr fs:[0000002Ch]
mov         edx,dword ptr [eax]
add         edx,128h ;296=sizeClass*sizeof(tc[0])
mov         eax,dword ptr [edx]
test        eax,eax
je          L1 ; вероятность перехода около 1%
mov         ecx,dword ptr [eax]
inc         dword ptr [edx+8]
mov         dword ptr [edx],ecx
ret

 L1:
 push        18h ; =24 (size class)
 mov         ecx,28h ; =40 (bytes size)
 call        fetch_from_central_cache<1> (0851380h)
 add         esp,4
 ret
 

mov    rdx,0xffffffffffffe7a0
mov    rax,QWORD PTR fs:[rdx+0x240]
test   rax,rax
je     L1 ; вероятность перехода ~1%
mov    rcx,QWORD PTR [rax]
add    DWORD PTR fs:[rdx+0x250],0x1
mov    QWORD PTR fs:[rdx+0x240],rcx
ret

 L1:    
 add    rdx,QWORD PTR fs:0x0
 mov    edi,0x28 ; =40 (bytes size)
 lea    rsi,[rdx+0x240]
 mov    edx,0x18 ; =24 (size class)
 jmp    <_Z24fetch_from_central_cache...>
 

NOINLINE void *create_list_of_arrays()
{
    struct node
    {
        node *next;
        std::array<int, 9> arr;
    } *p = NULL;

    for (int i=0; i<1000; i++)
    {
        node *n = new node;
        n->next = p;
        p = n;
    }

    return p;
}

 mov         eax,dword ptr fs:[0000002Ch] 
 push        ebx
 push        esi
 mov         esi,dword ptr [eax] 
 push        edi
 xor         edi,edi
 add         esi,128h
 mov         ebx,3E8h    ; =1000       

L2:
mov         eax,dword ptr [esi]
test        eax,eax
je          L1 ; вероятность ~1%
mov         ecx,dword ptr [eax]
inc         dword ptr [esi+8]
mov         dword ptr [esi],ecx
dec         ebx                  ; i++
mov         dword ptr [eax],edi  ; n->next = p;
mov         edi,eax              ; p = n;
jne         L2                   ; if (i<1000) goto L2

 pop         edi
 pop         esi
 pop         ebx
 ret
 L1:
 ...

 ...    

L2:
mov    r12,rax                      ; p = n;
mov    rax,QWORD PTR fs:[rbx+0x258]
test   rax,rax
je     L1 ; вероятность ~1%
mov    rdx,QWORD PTR [rax]
add    DWORD PTR fs:[rbx+0x268],0x1
mov    QWORD PTR fs:[rbx+0x258],rdx
L3:
sub    ebp,0x1                      ; i++
mov    QWORD PTR [rax],r12          ; n->next = p;
jne    L2                           ; if (i<1000) goto L2

 add    rsp,0x8
 pop    rbx
 pop    rbp
 pop    r12 
 pop    r13 
 ret    
 L1:
 mov    edx,0x19
 mov    rsi,r13 
 mov    edi,0x30
 call   <_Z24fetch_from_central_cache...>
 jmp    L3   

В этом случае компилятор соптимизировал выражение "new node;" в цикле до 6 ассемблерных инструкций!
Я думаю, что по производительности результат компиляции этого кода вполне может быть сопоставим с хорошим специализированным аллокатором, основанным на пулах.
(Но, хотя встраивание и даёт некоторые преимущества, оно не является абсолютно необходимым, и даже обычный не встроенный вызов функции ltalloc сработает очень быстро.)

2. Многопоточность и масштабируемость.

Для обеспечения высокой эффективности при работе множества параллельных потоков используется подход, аналогичный используемому в TCMalloc (я не использовал код TCMalloc, а только лишь основную идею).
Т.е., есть отдельный кэш на каждый поток, и все операции выделения памяти (кроме больших блоков >56Кб) в первую очередь пытаются получить свободный блок из этого кэша, организованного в виде простого односвязного списка освобожденных блоков на каждый диапазон размеров блоков (size class).
Если список оказался пустым, тогда из центрального списка (общего для всех потоков) выбирается сразу группа блоков (256 или меньше), помещается в локальный список потока, и один блок из этого списка возвращается приложению. Когда блок памяти освобождается, он, наоборот, добавляется сначала в список локальных блоков текущего потока, и в случае достижения определённого кол-ва блоков в этом списке (256 или менее, зависит от размера блока), весь список перемещается в центральный кэш для возможности последующего использования другими потоками.
Этот простой механизм может обеспечить достаточную масштабируемость (т.е. с достаточно небольшим числом состязаний) теоретически даже на 128-ядерной SMP-системе, если операции выделения/освобождения памяти будут разделены хотя бы 100 тактами другой полезной работы (примерно столько требуется на одну операцию перемещения группы блоков в центральный кэш или обратно). И такой подход особенно эффективен для паттерна "поставщик-потребитель", когда вся память, выделяемая в одном потоке, затем освобождается в другом.

3. Компактность размещения блоков.

В то время как многие аллокаторы хранят дополнительный указатель в начале каждого выделенного блока (т.о., напр. выделение 16 байт (или даже 13) фактически потребует 32 байта из-за требования выравнивания на 16 байт), в ltalloc хранится лишь небольшой (64 байт) общий заголовок на чанк (по умолчанию 64Кб), а все выделенные блоки хранятся непрерывно внутри чанка без каких-либо метаданных между ними, что гораздо более эффективно для маленьких блоков.
Тогда, если нет указателя в начале блока, должен быть другой способ для нахождения метаданных от данного блока. В некоторых аллокаторах для решения этой задачи используется граница sbrk, но минусы такого подхода в том, что приходится эмулировать sbrk на некоторых системах, а также в том, что память, выделенную таким способом, невозможно эффективно отдать системе после освобождения части блоков. Поэтому, я решил использовать другой подход: все большие блоки памяти (получаемые системным вызовом напрямую) всегда выровнены на размер чанка, т.о. все блоки внутри любого чанка будут не выровнены в отличие от больших блоков, и принадлежность любого блока чанку можно определить простым if (uintptr_t(p)&(CHUNK_SIZE-1)), а сам указатель на заголовок чанка легко получить через выражение (uintptr_t)p & ~(CHUNK_SIZE-1). (Подобный подход используется в jemalloc.)
Наконец, для разбивки размеров блоков на классы (size-classes) используется простой и быстрый алгоритм с округлением размера до "субстепени" двойки (2ⁿ, 1.25*2ⁿ, 1.5*2ⁿ и 1.75*2ⁿ по умолчанию, но гранулярность можно настроить, в т.ч. свести все размеры только к степеням двойки) - получается 51 класс размеров блоков до 56Кб, и накладные расходы по объему памяти (внутренняя фрагментация) не более 25%, в среднем 12%.
В качестве приятного бесплатного бонуса такой подход даёт "идеальное выравнивание" всех возвращаемых адресов блоков памяти (подробнее см. ниже).

Вопросы

1. Аллокатор ltalloc быстрее других аллокаторов памяти общего назначения?

Да, конечно! Зачем же ещё было писать свой аллокатор памяти. :)
Ну а если серьёзно, то вот сравнительная таблица производительности, основанная на простом тесте, выделяющем и освобождающем блоки памяти фиксированного размера из параллельно работающих потоков.
(Результат каждого теста указан в количестве миллионов пар операций (выделение+освобождение блока памяти размером 128 байт) в секунду на отдельный поток, т.е. для получения общего кол-ва операций необходимо умножить результат на кол-во потоков.)

Результаты 2x Xeon E5620/Debian в виде диаграммы:

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

2. За счет чего ltalloc так быстро работает?

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

1. if (size == 0) return NULL (или size = 1)
2. if (!initialized) initialize_allocator()
3. if (size < some_threshold) (для проверки что блок достаточно маленького размера)
4. if (freeList) {result = freeList, freeList = freeList->next}
5. if (result == NULL) throw std::bad_alloc() (в реализации оператора new)

Но в случае вызова оператора new, перегруженного через ltalloc, в среднем будет всего лишь одна условная инструкция - на основе п.4 (которая к тому же не приведёт к переходу в 99% случаев), в то время как остальные проверки будут делаться только по мере необходимости в редких случаях.

rmem

3. Как часто аллокатор возвращает память системе автоматически?

Ну в общем-то, никогда не возвращает (не считая больших блоков, запрашиваемых напрямую у системы).
Но всегда есть возможность сделать это вручную вызовом функции ltalloc_squeeze(), который можно делать в любое время (в т.ч. в отдельном потоке), и который практически не оказывает никакого влияния на производительность операций выделения/освобождения памяти в других потоках (кроме, очевидно, необходимости повторного получения памяти у системы при новых аллокациях). Кроме того, эта функция освобождает столько кэшированной аллокатором памяти сколько возможно - не только в "конце выделенной области" (как реализовано в malloc_trim и некоторых других аллокаторах).
Я не хотел делать эту процедуру автоматической, т.к. она сильно завязана на паттерн выделения памяти приложением (например., можно представить серверное приложение, которое периодически (раз в минуту напр.) должно обрабатывать какой-то тяжелый запрос, настолько быстро насколько возможно, и после обработки все выделенные блоки освобождаются - и если автоматически возвращать всю эту память системе в этом случае, то может несколько снизиться производительность обработки последующих запросов, т.к. это каждый раз будет требовать выделения памяти у системы). Кроме того, я очень не люблю всякие настраиваемые параметры пороговых значений, т.к. их обычно трудно настроить оптимально для большинства случаев использования, и в каких-то ситуациях производительность непременно будет значительно проседать. К тому же, автоматическое освобождение потребует дополнительных проверок в базовых функциях выделения/освобождения памяти (хотя и не обязательно на каждый вызов, но тем не менее когда-то они должны отрабатывать), и что более важно, такая процедура достаточно затратная, т.е. предпочтительно всё-таки вызывать ltalloc_squeeze асинхронно. В общем, поэтому я решил оставить только ручной вариант запуска процедуры возврата системе памяти от освобожденных блоков. Эту процедуру можно вызывать в наиболее подходящие моменты в зависимости от приложения (например, во время неактивности пользователя, либо сразу после закрытия вложенного окна/вкладки и т.д.).
Но если всё-таки хочется, чтобы очистка работала автоматически, то можно просто запустить отдельный поток, который будет периодически вызывать ltalloc_squeeze(0). Вот вариант реализации в одну строку на С++11:

std::thread([] {for (;;ltalloc_squeeze(0)) std::this_thread::sleep_for(std::chrono::seconds(3));}).detach();

4. Почему аллокатор не предоставляет никакой статистики по выделенным блокам памяти?

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

#ifdef ENABLE_ADDITIONAL_MEMORY_INFO
#include "some_malloc.cxx"
#else
#include "ltalloc.cc"
#endif

5. Почему нет отдельной функции аналога aligned_alloc для выделения выровненных блоков памяти?

Просто потому, что она не нужна! :)
Дело в том, что одной из особенностей аллокатора является то, что возвращаемые адреса блоков всегда "идеально выравнены" в соответствии с запрашиваемым размером, т.е. выравнивание составляет не менее pow(2, CountTrailingZeroBits(size)) байт. Напр., 4-хбайтные блоки всегда выровнены на 4 байта, 24-хбайтные - на 8 байт, 1024-хбайтные - на 1024, 1280 - на 256 и т.д.
(Учтите, что в C/C++ размер структуры всегда кратен размеру её наибольшего базового элемента, т.е. sizeof(struct {__m128 a; char s[4];}) = 32, а не 20 (16+4) ! Т.о., для любой возможной структуры S оператор "new S" всегда возвращает указатель, выровненный соответствующим образом.)
Т.о., если вам требуется выделить область памяти, выровненную на 4Кб, тогда просто подкорректируйте необходимый размер как (size+4095)&~4095 перед вызовом ltalloc (или new char). (К слову, в функцию aligned_alloc согласно стандарту С11 значение размера нужно передавать уже кратным параметру выравнивания, т.о. ltalloc() можно безопасно вызывать прямо вместо aligned_alloc(), т.е. даже без указания значения выравнивания, т.к. оно не требуется.)
Но, если честно, "идеальное выравнение" работает не для любых размеров блоков, а только не превышающих размер чанка (который равен 64Кб по умолчанию, т.е. в общем-то, это ограничение не должно быть проблемой). Адреса блоков большего размера выравнены только на размер чанка, и не более.
Вот полный список всех диапазонов размеров блоков и соответствующего им выравнивания:

Блоки размером более 57344 байт выделяются напрямую у системы (фактически выделяемая память кратна размеру страницы (4Кб), но расход виртуальной памяти кратен 65536 байт).

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

Фактически, это не даст значительного повышения производительности для практических задач, т.к. простые тесты показывают, что выделение даже 64Кб напрямую через VirtualAlloc или mmap быстрее (в 2-15 раз в зависимости от системы), чем простое зануление выделенного блока памяти через memset (кроме первого раза, который занимает в 4-10 раз больше из-за необходимости размещения страниц в физической памяти системой при первом доступе к страницам). Но очевидно, для бОльших размеров накладные расходы на системный вызов и переход в ядро будут ещё менее заметны. Однако, если для вашего приложения это имеет значение, то просто увеличьте значение параметра CHUNK_SIZE до желаемого уровня (однако хочу заметить, что в реальных приложениях рост требуемых объемов памяти идёт больше на уровне количества выделяемых блоков, а не их размера (напр., был 1 млн. записей - стало 2 млн., аналогично при добавлении в структуру новых объектов типа std::string и пр.; в то время как напр. средняя длина самих строчек увеличивается значительно реже), т.о. текущие значения параметров можно считать одинаково подходящими как для пользовательских приложений, так и для серверных).

Использование

Для подключения ltalloc к вашему C++ приложению достаточно просто добавить файл ltalloc.cc к списку исходных файлов проекта. В нём переопределяются глобальные операторы new и delete, что является полностью совместимым с С++ стандартом решением для замены практически всех аллокаций памяти в С++ приложениях (т.к. stl контейнеры по умолчанию используют глобальный оператор new). Но если этот способ не подходит для вашего приложения, то есть и другие варианты подключения. Фактически, исходный файл ltalloc.cc написан на C (и переопределение операторов new/delete отключается автоматически, если идентификатор __cplusplus не опередён), и т.о. он может быть скомпилирован как С, так и С++ компилятором.

GNU/Linux

1. gcc /path/to/ltalloc.cc ...
2. gcc ... /path/to/libltalloc.a
3. LD_PRELOAD=/path/to/libltalloc.so <appname> [<args...>]

Для использования вариантов 2 и 3 необходимо построить libltalloc:

hg clone https://code.google.com/p/ltalloc/
cd ltalloc/gnu.make.lib
make
(после этого файлы libltalloc.a и libltalloc.so будут созданы в текущей директории)

И при использовании этих вариантов (2 или 3) все вызовы malloc/free (а также calloc, posix_memalign и т.д.) будут проходить через ltalloc.
Также необходимо заметить, что при использовании опций -flto и -O3 с вариантом 2 компилятор GCC не будет встраивать вызовы функций malloc/free, если не добавить также опции -fno-builtin-malloc и -fno-builtin-free (однако, это лишь незначительное замечание по производительности, и совсем не обязательно для корректной работы).

Windows

К сожалению, под Windows не существует простого способа переопределения всех вызовов crt-функций malloc/free, и на данный момент есть только один простой способ замены практически всех аллокаций памяти в С++ приложениях - через перегрузку глобальных операторов new/delete (для этого, просто добавьте файл ltalloc.cc в ваш проект).

ltalloc был успешно собран компиляторами MSVC 2008/2010/2012, GCC 4.*, Intel Compiler 13, Clang 3.*, впрочем его исходный код очень простой, и может быть с лёгкостью портирован для компиляции любым другим компилятором C или C++ с поддержкой thread-local переменных. (Замечание: в некоторых сборках MinGW есть проблема с emutls и порядком вызова деструктора потока (все thread-local переменные удаляются до его вызова), и завершение любого потока может приводить к крашу.)