Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 42
Интересно было бы сравнить MassAllocator с boost::pool и Loki::SmallObjAllocator.
А запросто. Я просто скопипастил пример для new/delete и заменил их (надеюсь, что правильно)
А вот результаты:
Allocation and deallocation 40000000 objects took 5.572+0.05 = 5.622sec
boost::pool-based allocation and deallocation 40000000 objects took 2.14+0.73 = 2.87sec
Насколько я понял, boost::fast_pool_allocator использует обычную синхронизацию через boost::mutex.
Да, компилировал для x86-32.
// auto obj = new ObjectA();
auto obj = boost::fast_pool_allocator<ObjectA>::allocate();
...
// delete *jj;
boost::fast_pool_allocator<ObjectA>::deallocate(*jj);
А вот результаты:
Allocation and deallocation 40000000 objects took 5.572+0.05 = 5.622sec
boost::pool-based allocation and deallocation 40000000 objects took 2.14+0.73 = 2.87sec
Насколько я понял, boost::fast_pool_allocator использует обычную синхронизацию через boost::mutex.
Да, компилировал для x86-32.
Анализатор показывает, что по большей части потоки ждут захвата мьютекса (это я про boost::pool). А вот если понизить число потоков, скажем до двух (пропорционально увеличив число объектов) то у меня оно даже слегка быстрей работает.
Не знаю конкретики задачи, но возможно стоит рассмотреть вариант, когда пулом управляет один поток, а все остальные только обсчитывают данные — так можно избавиться от синхронизации пула вообще.
Не знаю конкретики задачи, но возможно стоит рассмотреть вариант, когда пулом управляет один поток, а все остальные только обсчитывают данные — так можно избавиться от синхронизации пула вообще.
boost::object_pool делает в точности что нужно, но есть ньюансы… Он не многопоточен!
void func()
{
boost::object_pool<X> p;
for (int i = 0; i < 10000; ++i)
{
X * const t = p.malloc();
... // Do something with t; don't take the time to free() it.
}
} // on function exit, p is destroyed, and all destructors for the X objects are called.
Loki::SmallObjAllocator не подходит идеологически — это аллокатор для классов типа std::list, std::map.
Эмм, а что мешает сделать thread-local pool allocator для каждого потока? Чтобы никакой общей синхронизации не было?
Мне требовалось чтобы объекты выделялись последовательно, без пропусков, каждому присваивался индекс, и этот индекс можно было использовать для быстрого обращения к самому объекту.
Индексы в последствии использовались для сериализации, по этому их монотонность была очень важна. Для первоначального варианта, где объекты выделялись через new, потом приходилось делать проход по все объектам и назначать индексы.
А, так это легко сделать, просто маркируя размеры пулов.
Т.е. «виртуальный индекс» объекта номер ObjectNum в пуле номер N равен Thread0_PoolSize + Thread1_PoolSize +… Thread<N-1>_PoolSize + ObjectNum.
Если эти виртуальные индексы нужны только на момент сериализации (и в этот момент мы уже ничего больше не аллоцируем), то все ок будет.
Т.е. «виртуальный индекс» объекта номер ObjectNum в пуле номер N равен Thread0_PoolSize + Thread1_PoolSize +… Thread<N-1>_PoolSize + ObjectNum.
Если эти виртуальные индексы нужны только на момент сериализации (и в этот момент мы уже ничего больше не аллоцируем), то все ок будет.
А оно действительно надо? Последовательно и без пропусков? Просто я знаю волшебный метод быстрого обращения к самому объекту безо всяких специальных индексов. Указатель называется. :) Если пулы фиксированные и влезают в 4GB, то можно хранить сжатый 32-битный указатель (ptr — base), как это делает, например java. Если размер объектов кратен 8, то и до 32 гигов можно пул держать (сдвиг на 3), если кратен 16 — то до 64 гигов и т.д.
Для этого требуется чтобы все объекты находились в ожном непрерывном блоке памяти.
Сколько объектов будет получено не известно на начало работы, может тысяча, а может и сто миллионов. Можно было конечно делать VirtualAlloc с флагом MEM_RESERVE для самого большого возможного количества объектов, а потом получать физическую память по необходимости, но проект кросс-платформенный и не хотелось завязываться на архитектуру.
Сколько объектов будет получено не известно на начало работы, может тысяча, а может и сто миллионов. Можно было конечно делать VirtualAlloc с флагом MEM_RESERVE для самого большого возможного количества объектов, а потом получать физическую память по необходимости, но проект кросс-платформенный и не хотелось завязываться на архитектуру.
В POSIX тоже есть резервирование памяти. см. mmap. А для производительности придется так или иначе завязываться на архитектуру.
Подскажите пожалуйста, как именно можно использовать mmap для этих целей. Я в мануалах нашел только резервирование своп пространства и, соответственно, флаг MAP_NORESERVE, но он не относится к теме.
mmap не позволяет зарезевировать в памяти регион например на 4 гигабайта, а потом по частям отображать его на физическую память. Поправьте меня, если я не прав.
Если автор не против, предлагаю сравнить с решением на языках с автоматической сборкой мусора.
Конечно не против!
при таких объемах в .Net любая оплошность дает вагон и маленький состав тележек проблем:
— реализовали данные как класс = получили страшную нагрузку на GC и лаг при сборке (даже в серверном режиме, с blocking GC и такими объемами будет совсем грустно);
— сделали struct, но унаследовали от интерфейса = заимели головную боль с боксингом;
— использовали struct, но забыли ref при передаче данных в другую функцию и получили копирование на ровном месте;
— использовали string или любой массив в структуре и получили миллионы объектов (= субъектов для сборки);
Я уж не говорю о хранении пула таких данных, который иначе как в Linked Arrays не сделать (либо таки одним массивом в NNN элементов).
в Java структур нет вообще, потому сборка мусора для каждого объекта неизбежна, а значит надо руками подстраивать параметры сборщика (недавно была статья на эту тему).
В целом, нет ничего невозможного, не раз уже решались такие задачи для managed языков, но разумно было бы выбрать именно C++, чтобы держать руку на пульсе, а не надеяться на благосклонность сборщика мусора и 100% отсутствие ошибок.
— реализовали данные как класс = получили страшную нагрузку на GC и лаг при сборке (даже в серверном режиме, с blocking GC и такими объемами будет совсем грустно);
— сделали struct, но унаследовали от интерфейса = заимели головную боль с боксингом;
— использовали struct, но забыли ref при передаче данных в другую функцию и получили копирование на ровном месте;
— использовали string или любой массив в структуре и получили миллионы объектов (= субъектов для сборки);
Я уж не говорю о хранении пула таких данных, который иначе как в Linked Arrays не сделать (либо таки одним массивом в NNN элементов).
в Java структур нет вообще, потому сборка мусора для каждого объекта неизбежна, а значит надо руками подстраивать параметры сборщика (недавно была статья на эту тему).
В целом, нет ничего невозможного, не раз уже решались такие задачи для managed языков, но разумно было бы выбрать именно C++, чтобы держать руку на пульсе, а не надеяться на благосклонность сборщика мусора и 100% отсутствие ошибок.
В принципе так и есть:
github.com/DarthVictor/JavaTests/blob/master/MassAllocationTest.java
Для java -Xms3g -Xmx3g -server при 20млн. результат 234ms на создание и 7ms на удаление на итерацию.
Но стоит увеличить до 40млн и GC начинает запускаться во время аллокации и вешает программу секунд на 5-10.
Как ему это запретить — непонятно.
github.com/DarthVictor/JavaTests/blob/master/MassAllocationTest.java
Для java -Xms3g -Xmx3g -server при 20млн. результат 234ms на создание и 7ms на удаление на итерацию.
Но стоит увеличить до 40млн и GC начинает запускаться во время аллокации и вешает программу секунд на 5-10.
Как ему это запретить — непонятно.
Настройками java — включить GC1 и огарничить время, на которое GC имеет право останавливать процесс. Плюс увеличить объём пула памяти.
Что-то вроде:
-XX:+UseG1GC
-XX:MaxGCPauseMillis=50
-Xms512m
Что-то вроде:
-XX:+UseG1GC
-XX:MaxGCPauseMillis=50
-Xms512m
Попробовал GC1, разницы, особой не почувствовал, в данном тесте он только медленнее на массивах в 20млн. и также тормозит на массивах > 20млн.
На ограничение времени сборщику мусора вообще плевать, если он запустился до окончания аллокации, то это стабильно фриз на машине секунд на 10-30. Пул памяти я и так ставил 3гига, как стартовый так и максимальный.
С такими ограничениями Java подходит только как ориентир для тестов C++.
Ну либо как-то, еще модифицировать GC, хотя насколько знаю нельзя напрямую запретить его автоматический запуск.
На ограничение времени сборщику мусора вообще плевать, если он запустился до окончания аллокации, то это стабильно фриз на машине секунд на 10-30. Пул памяти я и так ставил 3гига, как стартовый так и максимальный.
С такими ограничениями Java подходит только как ориентир для тестов C++.
Ну либо как-то, еще модифицировать GC, хотя насколько знаю нельзя напрямую запретить его автоматический запуск.
Во-первых, при ожидании имеет смысл не yield сразу вызывать, а раз от 5..30 цикл с проверкой прокрутить, так как современных процессорах велика вероятность, что другой поток исполняется на отдельном ядре. А Yield очень тяжёлая и длительная операция. Процентов 15% можно прироста скорости получить.
Про переполнение счётчика тоже не понял. Если после инкремента выясняется, что блок закончился, то нужно выделять новый внутри классической критической секции (с повторной проверкой внутри критической секции). А если есть вероятность, что переполнится 32-бит счётчик (что невероятно, так как нужно иметь порядка 2^32 потоков), то нужно ещё раз проверять счётчик на переполнение ДО инкремента.
Зачем делать unoin для доступа к половинкам 64-битных чисел не ясно — это категорически вредно с точки зрения стандарта и идеологии c++ — всё держится на компиляторо- и платфо-зависимых допущениях. При настоящих atomicInc это всё излишне и избыточно.
Про переполнение счётчика тоже не понял. Если после инкремента выясняется, что блок закончился, то нужно выделять новый внутри классической критической секции (с повторной проверкой внутри критической секции). А если есть вероятность, что переполнится 32-бит счётчик (что невероятно, так как нужно иметь порядка 2^32 потоков), то нужно ещё раз проверять счётчик на переполнение ДО инкремента.
Зачем делать unoin для доступа к половинкам 64-битных чисел не ясно — это категорически вредно с точки зрения стандарта и идеологии c++ — всё держится на компиляторо- и платфо-зависимых допущениях. При настоящих atomicInc это всё излишне и избыточно.
Сначала было так:
Потом я начал искать способы оптимизации и вариант с union дал небольшой прирост. А вообще да, union — хак.
auto index = curAtomicIndex_++;
uint32_t blocksCount = index >> 32;
uint32_t lastIndexInBlock = index & 0xffffffff;
Потом я начал искать способы оптимизации и вариант с union дал небольшой прирост. А вообще да, union — хак.
Про переполнение счётчика тоже не понял. Если после инкремента выясняется, что блок закончился, то нужно выделять новый внутри классической критической секции (с повторной проверкой внутри критической секции). А если есть вероятность, что переполнится 32-бит счётчик (что невероятно, так как нужно иметь порядка 2^32 потоков), то нужно ещё раз проверять счётчик на переполнение ДО инкремента.
Критических секций не хотелось по причинам:
1 хотелось обойтись без критических секций :-)
2 войти в критическую секцию первым мог как поток, первым наткнувшийся на нехватку места, так и остальные. Пришлось бы усложнять логику, на решение кто же выделяет следующий блок, хотя по чесному конечно ничего сложного в этом нет
3 переполнение может произойти потому что потоки не останавливаются, а непрерывано запрашивают через атомарную переменную новый индекс, и как только он станет валидным с радостью выделяют элемент
Я всё же не понимаю зачем long переменная? Атомарность в данном случае никто не обещает — зависит от выравнивания памяти, архитектуры и настроек компилятора. с некоторой натяжкой на современных компиляторах архитектурах атомарность чтения/записи только 32-бита даёт. Что-то вроде:
volatile unsigned int atomic;
…
unsigned int tmp=atmoic; // Вот тут будет атомарность на всех современных архитектурах и компиляторах.
А 64-бита компилятор может смело разбить на два 32-битых чтения/записи. К тому же оно у Вас не volatile — так что он его и оптимизировать/кэшировать/хоть по-байтно читать может.
volatile unsigned int atomic;
…
unsigned int tmp=atmoic; // Вот тут будет атомарность на всех современных архитектурах и компиляторах.
А 64-бита компилятор может смело разбить на два 32-битых чтения/записи. К тому же оно у Вас не volatile — так что он его и оптимизировать/кэшировать/хоть по-байтно читать может.
index = curAtomicIndex_++;
volatile в данном случае для index здесь не нужен, index локальная переменная и не может быть изменнена внешним кодом.
Для х64 curAtomicIndex_++ транслируется в InterlockedExchangeAdd64, который ассемблируется в команду
lock xadd QWORD PTR [rcx+32], r8.
Для х86 атомарность реализуется сложнее, но тем не меннее
index = curAtomicIndex_++;
volatile нужен не для index, а для curAtomicIndex_. И не volatile, а использование atomic типа.
Ну за счет чего оно будет работать атомарно? Компилятор имеет право даже в память её обратно не писать. Может загрузить на регистр и там её модифицировать. У каждого процесса свой регистр.
в любом случае работает атомарно.
Ну за счет чего оно будет работать атомарно? Компилятор имеет право даже в память её обратно не писать. Может загрузить на регистр и там её модифицировать. У каждого процесса свой регистр.
Нашел код на гитхабе. Там curAtomicIndex_ объявлен как std::atomic<uint64_t>. Тогда да, атомарно на любой архитектуре.
атомарное чтение/запись, а не атомарный инкремент. Без этого вообще нельзя между потоками обмениваться — во-первых компилятор может обнаружить, что в текущей задаче значение никогда не пишется и закешировать его, во-вторых, на некоторых архитектурах запись в такие переменные осуществляется особым образом, а в-третьих большинство (все?) современные компиляторы исполняются чтение/запись volatile-базовых типов атомарно (иначе просто невозможно было бы писать драйвера устройств — запись/чтение регистров по определению должны быть атомарны).
В статье упустил момент, что curAtomicIndex_ объявлен как std::atomic<uint64_t>.
Его инкримент будет атомарен, за этим следит компилятор. Для х64 транслируется в
Для х86 код сложнее, но сводится к атомарному cmpxchg8b
Его инкримент будет атомарен, за этим следит компилятор. Для х64 транслируется в
lock xadd QWORD PTR [rcx+32], r8.
Для х86 код сложнее, но сводится к атомарному cmpxchg8b
$again$158:
; 2424 : again:
; 2425 : mov ecx, edx;
mov ecx, edx
; 2426 : mov ebx, eax;
mov ebx, eax
; 2427 : add ebx, dword ptr _Value;
add ebx, DWORD PTR $T7[ebp]
; 2428 : adc ecx, dword ptr _Value[4];
adc ecx, DWORD PTR $T7[ebp+4]
; 2429 : lock cmpxchg8b [esi];
lock cmpxchg8b QWORD PTR [esi]
; 2430 : jnz again;
jne SHORT $again$158
2 войти в критическую секцию первым мог как поток, первым наткнувшийся на нехватку места, так и остальные. Пришлось бы усложнять логику, на решение кто же выделяет следующий блок, хотя по чесному конечно ничего сложного в этом нет
А вроде в критическую секцию потоки по одному заходят?
А вроде в критическую секцию потоки по одному заходят?
Во-первых, при ожидании имеет смысл не yield сразу вызывать, а раз от 5..30 цикл с проверкой прокрутить, так как современных процессорах велика вероятность, что другой поток исполняется на отдельном ядре. А Yield очень тяжёлая и длительная операция. Процентов 15% можно прироста скорости получить.
Делал и вообще без yield и с ним. Разницы в скоросте не заметил. Решил оставить вариант с yield, так как с ним ведем себя дружественнее по отношению к другим потокам, которые тоже хотят работать. Циклов ожидания в обоих случаях получалось в районе нескольких тысяч, с yield немного меньше.
Мне интересно, сколько в будет холостых циклов while(true) {… } в случае большой нагрузке, как указано в одном из комментов выше, будет использован lock, что приведет к блокировке шины, операция сама по себе не сильно шустрая, да еще и другим мешается. Когда я делал свой lock-free аллокатор, который за раз должен был выделять несколько блоков (у меня использовался стек по 2 InterlockedCompareAndExchange, в моем случае в deque хранились все свободные блоки памяти, которые можно было отдать), так в этом случае на большое кол-во блоков начинало работать не очень быстро, в моем случае критическая секция на spin-lock (1 lock операция на блокировку и всё, далее всё обычными) показала себя заметно лучше. Да и реализация была заметно проще.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Одним махом 100 миллионов убивахом. Или lock-free распределитель памяти