Есть ли выигрыш в HeapAlloc(HEAP_NO_SERIALIZE)?

У меня был давний интерес, как сделать одну хитрую вещицу. Есть код работающий с объектами, и эти объекты могут быть разбиты на группы для параллельной обработки в параллельных потоках. Сами объекты могут использовать динамическую память. Задача выглядит примерно так: можно ли им работать в хипах, независимых друг от друга и не входить в взаимные блокировки при запросе и освобождении памяти.

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

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

std::vector.push_back()

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

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

Для частного хипа был интерес использовать функции

HeapCreate
HeapAlloc
HeapFree
HeapDestroy

с опцией HEAP_NO_SERIALIZE, чтобы потоки не входили в взаимные блокировки.

const DWORD heap_options = HEAP_NO_SERIALIZE;

Для объекта реальной аллокации сделаем объект обращения к частному хипу

struct CustomHeap
{
  HANDLE hHeap;

  CustomHeap()
  {
    hHeap = HeapCreate(heap_options, 8 * 1024, 0);
  };
  ~CustomHeap()
  {
    HeapDestroy(hHeap);
  };
};

Для того, чтобы такой объект мог существовать в потоке и контейнерный аллокатор мог получить этот текущий потоковый объект, используем TLS.

static DWORD tls_index = 0;

Аллокатор имеет прототип

template <class T> struct HeapAllocator

и должен объявить свои внутренние typedef такого набора:

typedef T value_type;
typedef unsigned int size_type;
typedef int difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
template<typename T2> struct rebind { typedef HeapAllocator<T2> other; };
unsigned max_size() const { return 1024 * 1024; };

В нем помним физический аллокатор, с которым работаем

CustomHeap* pCustomHeap;

Объявляем пакет конструкторов и деструктор

HeapAllocator()
{
  pCustomHeap = (CustomHeap*)TlsGetValue( tls_index);
};
HeapAllocator(const HeapAllocator& src)
{
  pCustomHeap = src.pCustomHeap;
};
HeapAllocator(CustomHeap& _pCustomHeap)
{
  pCustomHeap = &_pCustomHeap;
};
~HeapAllocator()
{
};

Сам аллокатор не удаляет физический аллокатор, а лишь ссылается на постоянно живущий (на объект CustomHeap).

Аллокатору надо объявить функции предопределенного прототипа, который и используют контейнеры STL:

T* allocate(size_t size)
{
  size *= sizeof(T);
  return (T*)HeapAlloc(pCustomHeap->hHeap, heap_options, size);
};
template <typename U> T * allocate(const size_t n, const U * /* const hint */) const 
{ 
  return allocate(n); 
};
void deallocate(void* p, size_t size)
{
  HeapFree(pCustomHeap->hHeap, heap_options, p);
};

Здесь немножко скользкое место - в параметрах allocate и deallocate значение size задает не количество байт, а количество объектов, каждый из которых размером sizeof(T). Они совпадают лишь для однобайтовых объектов (char, unsigned char).

И нужно определить правило помещения создаваемого объекта в выделяемой памяти. Мы просто используем совпадение адресов выделенной памяти с началом объекта, хотя вообще говоря это и необязательно. Но есть специфика контейнеров, которые полагают совпадение адресов, например std::vector размещает объекты по адресам действительно последовательно. Просто добавляем минимально необходимый интерфейс:

void construct(void* p, const T& val)
{ 
  new(p) T (val); 
};
void destroy(T* p)
{
  p->~T();
};

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

Для работы контейнеров STL дополнительно требуется определить операторы сравнения - являются ли два объекта аллокатора одним и тем же по смыслу его работы.

template<class T, class U> 
bool operator==(const HeapAllocator<T>& lhs, const HeapAllocator<U>& rhs)
{ 
  return lhs.pCustomHeap == rhs.pCustomHeap; 
}

template<class T, class U> 
bool operator!=(const HeapAllocator<T>& lhs, const HeapAllocator<U>& rhs)
{ 
  return lhs.pCustomHeap != rhs.pCustomHeap; 
}

Чтобы немножко упростить код для себя определим

typedef std::basic_string<char, 
  std::char_traits<char>, HeapAllocator<char>> string3_t;
typedef std::vector<string3_t, HeapAllocator<string3_t>> strings3_t;

Здесь класс std::char_traits задает правило округления запрашиваемого размера памяти для строки, чтобы можно было запросить чуть больше и в случае переприсваивания на значения в тех же пределах обойтись без дополнительной аллокации, а использовать тот же выделенный буфер.

Для каждого потока создаем структуру

struct ThreadData3
{
  size_t thread_number;
  CustomHeap ch;
  HeapAllocator<string3_t> ha;
  strings3_t strings;
  ThreadData3() : ha(ch), strings(ha) {};
};

Собственно сама потоковая функция обработки простая, имитирует проверку массива данных и формирует результат в виде контейнера строк.

const size_t thread_count = 20;
const size_t total_check_count = 1000000;

unsigned Function3(void* pThreadArg)
{
  ThreadData3* pThreadData = (ThreadData3*)pThreadArg;
  TlsSetValue( tls_index, &pThreadData->ch);
  HeapAllocator<char> cha(pThreadData->ch);
  for(size_t i = pThreadData->thread_number; i < total_check_count; i += thread_count)
  {
    char buffer[128];
    sprintf(buffer, "result of %d%%2 is %s", i, i % 2 ? "true" : "false");
    string3_t val(cha);
    val = buffer;
    pThreadData->strings.push_back(val);
  }
  return 0;
};

Первым делом она прописывает используемые частные потоковые данные в TLS, чтобы могли работать автоматически создаваемые объекты аллокаторов, имеющие конструктор по умолчанию.

Остальной код просто типовой для работы с объектами STL. Единственное что требуется - почаще определять для объектов string3_t ссылку на аллокатор, иначе будет часто создаваться дежурный объект.

Перед запуском потоков создаем слот для TLS:

tls_index = TlsAlloc();

к которому будут обращаться потоки для взятия собственных объектов.

Потоки создаются просто:

ThreadData3 threads[thread_count];
HANDLE hThread[thread_count];
for(size_t i = 0; i < thread_count; i++)
{
  threads[i].thread_number = i;
  unsigned threadID;
  hThread[i] = (HANDLE)_beginthreadex(NULL, 0, 
    Function3, threads + i, 0, &threadID);
}
WaitForMultipleObjects(thread_count, hThread, TRUE, INFINITE);

В целом результат как-бы есть, контейнеры работают корректно, все объекты групп создаются в частных хипах и код полностью распараллелен без использования синхронизаторов. Но цель так и осталась недостигнутой потому, что оказалось что собственно сам код HeapAlloc / HeapFree работает медленнее чем стандартный malloc / free / new / delete даже с использованием опции HEAP_NO_SERIALIZE.

Впрочем, если в полученном аллокаторе вместо HeapAlloc использовать стандартный malloc, то использование такого аллокатора получается чуть более легковесным чем использование стандартного аллокатора STL, который шаблоны подставляют по умолчанию.

Цель как-бы до конца не достигнута, реально заметного ускорения от использования HeapAlloc + HEAP_NO_SERIALIZE получить не удалось, но код работы с кастомным аллокатором и вообще сама эта работа могут быть интересными другим, поэму и выложил в блог.

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

Ну и собственно сам полный код теста для тех, кто хочет видеть все:

#include "stdafx.h"
#include 
#include 

#include <vector>

const size_t total_check_count = 1000000;

void Function1(void)
{
  std::vector<std::string> strings;
  for(size_t i = 0; i < total_check_count; i++)
  {
    char buffer[128];
    sprintf(buffer, "result of %d%%2 is %s", i, i % 2 ? "true" : "false");
    std::string val = buffer;
    strings.push_back(val);
  }
  return;
};

typedef std::string string2_t;
typedef std::vector<string2_t> strings2_t;

struct ThreadData2
{
  strings2_t strings;
  size_t thread_number;
};

const size_t thread_count = 20;

unsigned Function2(void* pThreadArg)
{
  ThreadData2* pThreadData = (ThreadData2*)pThreadArg;
  for(size_t i = pThreadData->thread_number; 
    i < total_check_count; i += thread_count)
  {
    char buffer[128];
    sprintf(buffer, "result of %d%%2 is %s", i, i % 2 ? "true" : "false");
    string2_t val = buffer;
    pThreadData->strings.push_back(val);
  }
  return 0;
};

const DWORD heap_options = HEAP_NO_SERIALIZE;

struct CustomHeap
{
  HANDLE hHeap;

  CustomHeap()
  {
    hHeap = HeapCreate(heap_options, 8 * 1024, 0);
  };
  ~CustomHeap()
  {
    HeapDestroy(hHeap);
  };
};

static DWORD tls_index = 0;

template <class T> struct HeapAllocator
{
  typedef T value_type;
  typedef unsigned int size_type;
  typedef int difference_type;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef T& reference;
  typedef const T& const_reference;
  typedef T value_type;
  template<typename T2> 
    struct rebind { typedef HeapAllocator<T2> other; };
  unsigned max_size() const { return 1024 * 1024; };

  CustomHeap* pCustomHeap;

  HeapAllocator()
  {
    pCustomHeap = (CustomHeap*)TlsGetValue( tls_index);
  };
  HeapAllocator(const HeapAllocator& src)
  {
    pCustomHeap = src.pCustomHeap;
  };
  HeapAllocator(CustomHeap& _pCustomHeap)
  {
    pCustomHeap = &_pCustomHeap;
  };
  ~HeapAllocator()
  {
  };

  T* allocate(size_t size)
  {
    // size is number of objects with sizeof(T)
    size *= sizeof(T);
    return (T*)HeapAlloc(pCustomHeap->hHeap, heap_options, size);
  };
  template <typename U> T * allocate(const size_t n, 
    const U * /* const hint */) const 
  { 
    return allocate(n); 
  };
  void deallocate(void* p, size_t size)
  {
    // size is number of objects with sizeof(T)
    HeapFree(pCustomHeap->hHeap, heap_options, p);
  };
  void construct(void* p, const T& val)
  { 
    new(p) T (val); 
  };
  void destroy(T* p)
  {
    p->~T();
  };
};

template<class T, class U> 
bool operator==(const HeapAllocator<T>& lhs, const HeapAllocator<U>& rhs)
{ 
  return lhs.pCustomHeap == rhs.pCustomHeap; 
}

template<class T, class U> 
bool operator!=(const HeapAllocator<T>& lhs, const HeapAllocator<U>& rhs)
{ 
  return lhs.pCustomHeap != rhs.pCustomHeap; 
}

typedef std::basic_string<char, std::char_traits<char>, 
  HeapAllocator<char>> string3_t;
typedef std::vector<string3_t, HeapAllocator<string3_t>> strings3_t;

struct ThreadData3
{
  size_t thread_number;
  CustomHeap ch;
  HeapAllocator<string3_t> ha;
  strings3_t strings;
  ThreadData3() : ha(ch), strings(ha) {};
};

unsigned Function3(void* pThreadArg)
{
  ThreadData3* pThreadData = (ThreadData3*)pThreadArg;
  TlsSetValue( tls_index, &pThreadData->ch);
  HeapAllocator<char> cha(pThreadData->ch);
  for(size_t i = pThreadData->thread_number; 
    i < total_check_count; i += thread_count)
  {
    char buffer[128];
    sprintf(buffer, "result of %d%%2 is %s", i, i % 2 ? "true" : "false");
    string3_t val(cha);
    val = buffer;
    pThreadData->strings.push_back(val);
  }
  return 0;
};

int _tmain(int argc, _TCHAR* argv[])
{
  tls_index = TlsAlloc();
  DWORD start, end;

  printf("start 1\n");
  start = GetTickCount();
  Function1();
  end = GetTickCount();
  printf("end 1, time = %d\n", end - start);

  printf("start 2\n");
  start = GetTickCount();
  {
    ThreadData2 threads[thread_count];
    HANDLE hThread[thread_count];
    for(size_t i = 0; i < thread_count; i++)
    {
      threads[i].thread_number = i;
      unsigned threadID;
      hThread[i] = (HANDLE)_beginthreadex(NULL, 0, 
        Function2, threads + i, 0, &threadID);
    }
    WaitForMultipleObjects(thread_count, hThread, TRUE, INFINITE);
  }
  end = GetTickCount();
  printf("end 2, time = %d\n", end - start);

  printf("start 3\n");
  start = GetTickCount();
  {
    ThreadData3 threads[thread_count];
    HANDLE hThread[thread_count];
    for(size_t i = 0; i < thread_count; i++)
    {
      threads[i].thread_number = i;
      unsigned threadID;
      hThread[i] = (HANDLE)_beginthreadex(NULL, 0, 
        Function3, threads + i, 0, &threadID);
    }
    WaitForMultipleObjects(thread_count, hThread, TRUE, INFINITE);
  }
  end = GetTickCount();
  printf("end 3, time = %d\n", end - start);

  return 0;
}