Выделение выровненных блоков динамической памяти

Проблема: стандартные средства выделения блоков динамической памяти в C99 и C++14, будь то malloc и free или new и delete гарантируют выравнивание выделенных блоков, достаточное только для базовых примитивных типов (alignof(max_align_t)). Для типов данных, имеющих более жёсткие ограничения по выравниванию, например, данные SSE (16 байт) и AVX (32 байта), либо в случае когда требуется выравнивать блоки по строкам кэша или страницам памяти, нет готового стандартного способа получить корректно выровненную память. Только в стандарте C11 появилась функция aligned_alloc, которая позволяет явно указать желаемое выравнивание (число, которому должен быть кратен адрес блока). Возвращённый этой функцией указатель можно передать затем free (для освобождения) или realloc (для изменения размера блока, realloc не гарантирует сохранения выравнивания!), так же, как если бы блок был выделен вызовом malloc. К сожалению, данная функция пока не вошла в стандарт C++, из-за чего могут возникнуть проблемы с компиляцией C++ кода, использующего эту функцию.

Описанная проблема стоит давно, часто поднималась, например, на StackOverflow: раз, два. Тем более, что в C++11 были добавлены средства управления выравниванием при статическом выделении памяти (см. alignas, align, aligned_storage). Однако, почему-то динамическое выделение памяти обошли вниманием, что, конечно, является существенным недостатком для языков системного программирования. Просто удивительно, что в C это было закрыто только в 2011 году. Для решения данной проблемы с недавних пор также создана библиотека Boost.Align.

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

Итак, обычный выбор заключается в использовании вариантов, предлагаемых конкретными платформами (обычно Windows и POSIX), плюс, возможно, универсальный неоптимальный вариант на основе стандартных функций управления динамической памятью. Рассмотрим эти три варианта (следуя также информации из ответов на StackOverflow).

В случае платформы POSIX (_POSIX_VERSION >= 200112L) имеем функцию posix_memalign, результат которой можно освобождать с помощью стандартной функции free.

// POSIX version
#include <stdlib.h>
// возвращает код ошибки, 0 -- успех
// адрес выделенного блока записывается по указателю memptr
int posix_memalign(void **memptr, size_t alignment, size_t size);

В случае использования Windows (точнее, Microsoft Visual C++ runtime) имеем пару функций _aligned_alloc и _aligned_free (есть также _aligned_realloc и т.д.).

// MSVC version
#include <malloc.h>
void* _aligned_malloc(size_t size, size_t alignment);
void _aligned_free(void*)

Документация к компилятору Intel предлагает аналогичные функции с другими названиями.

// ICC version
#include <malloc.h>
void* _mm_malloc(size_t size, size_t alignment);
void _mm_free(void*)

Более того, в MSVC (malloc.h) _mm_malloc и _mm_free определены как макросы, раскрывающиеся в _aligned_alloc и _aligned_free, что позволяет использовать первые вместо последних и на MSVC и на ICC. То же самое касается MinGW и сборки TDM-GCC для Windows.

Если варианты, приведённые выше, не подходят, то можно выделить блок размера (запрошенный размер + размер указателя + выравнивание — min(гарантированное выравнивание, размер указателя)), выбрать в нём наименьший выровненный адрес (адрес результата) и записать адрес блока в указатель прямо перед адресом результата, чтобы затем извлечь его при удалении блока. Недостаток данного метода заключается в перерасходе памяти, который может превышать 100% в неудачных случаях (т.е. более чем двойной расход). Кроме того, может замусориваться кэш (обращение к предыдущей строке или странице для сохранения указателя на реальный блок).

// Generic version
#include <cstdlib>
#include <cstdint>
#include <cassert>

void* aligned_alloc(size_t size, size_t alignment)
{
  using namespace std;
  if (alignment < alignof(max_align_t))
  {
    // Проверим, что alignment -- степень двойки.
    const bool good_al = (alignment & (alignment - 1)) == 0;
    assert(good_al);
    if (!good_al)
      return nullptr;
    // Заменим alignment минимальным доступным значением.
    alignment = alignof(max_align_t);
  }
  else
  {
    // Проверим, что alignment / alignof(max_align_t) -- степень двойки.
    const auto ptr_al = alignment / alignof(max_align_t);
    const bool good_al = (ptr_al & (ptr_al - 1)) == 0;
    assert(good_al);
    if (!good_al) // Bad alignment value.
      return nullptr;
  }

  static const auto excess_bytes = 
    sizeof(void*) < alignof(max_align_t)? sizeof(void*): alignof(max_align_t);
  auto block = (char*)malloc((size + sizeof(void*)) + (alignment - excess_bytes));
  if (!block) // No memory allocated.
    return nullptr;

  // Вычислим смещение адреса относительно выделенного блока.
  const auto block_repr = reinterpret_cast<uintptr_t>(block);
  const auto block_offs = (alignment - (sizeof(void*) + block_repr)) & (alignment - 1);
  // Вычислим результирующий указатель.
  const auto result = block + sizeof(void*) + block_offs;
  // Сохраним адрес исходного блока.
  *(void**)(result - sizeof(void*)) = block;
  return result;
}

void aligned_free(void *ptr)
{
  using namespace std;
  if (ptr)
    free(*((void**)ptr - 1));
}

Откровенно говоря, у меня есть подозрение, что _aligned_malloc и _mm_malloc реализованы примерно так же, и их использование влечёт те же недостатки.

Проведены тесты (generic version и платформенной): MSVC2013.4 x64 (Windows), tdm-gcc 5.1 x64 (Windows), g++ 4.8.3 x64 (Linux) — многократное повторное выделение-удаление, заполнение. Код: Bitbucket.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: