Алгоритм представляет собой вариацию последовательной подгонки с использованием отдельно связанного списка буферов свободной памяти. Алгоритм основан на статье о совместно используемой памяти под названием«Обмен общей памятью». Алгоритм выглядит следующим образом:

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

simple_seq_fit memory layout:
    main      extra  allocated  free_block_1     allocated   free_block_2    allocated   free_block_3
    header    header  block       ctrl     usr     block      ctrl     usr     block      ctrl     usr
   _________  _____  _________  _______________  _________  _______________  _________  _______________
  |         ||     ||         ||         |     ||         ||         |     ||         ||         |     |
  |free|ctrl||extra||         ||next|size| mem ||         ||next|size| mem ||         ||next|size| mem |
  |_________||_____||_________||_________|_____||_________||_________|_____||_________||_________|_____|
      |                         | |                         |  |                       | |
      |_>_>_>_>_>_>_>_>_>_>_>_>_| |_>_>_>_>_>_>_>_>_>_>_>_>_|  |_>_>_>_>_>_>_>_>_>_>_>_| |
                                |                                                        |
                                |_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<_<__|

Когда пользователь запрашивает N байтов памяти, распределитель пересекает список бесплатных блоков в поисках достаточно большого блока. Если «мем» часть блока имеет тот же размер, что и запрошенная память, мы стираем блок из списка и возвращаем указатель на «мем» часть блока. Если размер детали «мем» больше необходимого, мы разделим блок на два блока, один из которых запрашивается, а другой с оставшимся размером. Теперь мы берем блок с точным размером, стираем его из списка и передаем пользователю.

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

Для облегчения реализации размер блока свободной памяти измеряется в кратных байтах «basic_size». Основным размером будет размер блока управления, выровненного с машиной наиболее ограничительного выравнивания.

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

В большинстве 32 систем с 8-байтовым выравниванием «basic_size» составляет 8 байт. Это означает, что запрос на выделение 1 байт приводит к созданию 16-байтового блока, где 8 байт доступны пользователю. Выделение 8 байтов приводит к тому же 16-байтному блоку.

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

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

rbtree_best_fit memory layout:
   main            allocated block   free block                        allocated block  free block
   header
  _______________  _______________  _________________________________  _______________  _________________________________
 |               ||         |     ||         |                 |     ||         |     ||         |                 |     |
 |  main header  ||next|prev| mem ||next|prev|left|right|parent| mem ||next|prev| mem ||next|prev|left|right|parent| mem |
 |_______________||_________|_____||_________|_________________|_____||_________|_____||_________|_________________|_____|

Этот алгоритм распределения довольно быстрый и хорошо масштабируется с большими сегментами общей памяти и большим количеством выделений. Для формирования блока необходим минимальный размер памяти: сумма двойного списка и данные управления красно-черным деревом. Размер блока измеряется в кратных значениях наиболее ограничительного выравнивания.

В большинстве 32 систем с 8-байтовым выравниванием минимальный размер блока составляет 24 байта. При выделении блока контрольные данные, связанные с красным черным деревом, перезаписываются пользователем (потому что это необходимо только для свободных блоков).

В этих системах запрос на выделение байта 1 означает, что:

Для действительно небольших распределений (8 байт) этот алгоритм тратит больше памяти, чем простой последовательный алгоритм (8 байт больше). Для выделений размером более 8 байт накладные расходы на память точно такие же. Это алгоритм распределения по умолчанию вBoost.Interprocess.Управляемые сегменты памяти.