C++ template аллокатора с потокобезопасным циклическим буфером

[@fougasse]

Overhead меряли? Что с другими архитектурами?

[@DimaBond174]

Эксперименты показали, что malloc работает не так уж медленно:
Windows x64:

Linux x64:

Всех быстрее однопоточный MemPool (это тот же FastMemPool в котором убрал atomic операции). В многопоточной работе FastMemPool позволил добиться кратного роста производительности + в нём же ещё есть фишки для контроля выхода за пределы аллокации… некая польза есть…
Сам тест тут test_overhead.cpp

[@DimaBond174]

«Что с другими архитектурами?» — у меня была возможность на ARM померить:


Исходник теста тут: FastMemPool on Android

[@seregazh]

Если я не ошибаюсь, то стандарт не регламентирует реализацию std::atomic.
В случае если CPU не предоставляет специальных атомарных инструкций, то std::atomic может быть реализован при помощи std::mutex.
Так что технически Ваша реализация может на 99% lock-free, но не на 100%.

[@NN1]

Для гарантии можно использовать static_assert на std::atomic::is_always_lock_free.
https://en.cppreference.com/w/cpp/atomic/atomic/is_always_lock_free

[@snikulov]

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

[@Tyiler]

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

const size_t BUFF_SZ = 10000;
vector<byte> buffer(BUFF_SZ);    
size_t bufCPos = 0;                       // в каждом потоке свой буфер, поэтому без atomic

byte* popMem(size_t frameSz){
  if (bufCPos + frameSz > BUFF_SZ){
    return nullptr;                       // памяти не хватает - пропускаем кадр
  }
  bufCPos += frameSz;
  return buffer.data() + (bufCPos - frameSz);
}

void pushMem(size_t frameSz){
  bufCPos -= frameSz;
}

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

[@DimaBond174]

камера отдаёт кадры в своём потоке, кадры аллоцированны в потоке камеры из буфера камеры который тормозит камеру от того чтобы съесть всю RAM на компьютере — как потокам_обработчикам вернуть память кадров обратно в буфер камеры после того как они закончат обработку?

[@Tyiler]

Как то так бы делал:
Память пусть в потоке камеры остается.
Камера в своем потоке циклически записывает кадры в свой буфер (состоит из структур типа — {frame, flag}) и пишет флаг для каждой позиции — «кадр обновлен».
В рабочем потоке (одном из) бежать по буферу камеры, искать обновленный кадр, его брать себе — копируя в свою память, флаг менять — «кадр взят в работу».
Камера может обновить кадр, только если в этой позиции стоит флаг «взят в работу». Если нет таких, то есть все потоки заняты, то пропускает этот кадр.

[@northzen]

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

[@DimaBond174]

опыт показывает что идеального освещения не бывает — для каждого вида детектора приходится колдовать с освещением… мультистерео — это для съёмки спецэффектов в кино?

[@northzen]

Но ведь освещение проще поставить, если уж собираются данные с помощью лазерного сканера?
Мультистерео — восстановление картинки с нескольких камер.
Например, по двум изображеням восстановить карту глубины и по ней Z-координату, например. Можно использовать и 3 картинки с разных камер, а можно и еще больше.
Можно и одну камеру, а сдвигать только лист. Тем самым можно получить объемное изображение листа. Но точность будет относительная.

Кстати, а можно примеры изображений листа и той модели, что получаете по итогу?

[@DimaBond174]

Получаем карту из uint16_t где каждое значение коррелирует с высотой = карта высот. Визуализировать можно по разному — основная сложность в том что градаций серого/цвета на экране всего 256 => либо идёшь окном визуализации по диапазону высот, либо всё ужимаешь в 256 делением теряя детали. Для Детектора это не имеет значения так как он работает с raw uint16_t (т.е. какая картинка в RGB\BGR ему не важно). Видим все изломы/вмятины/неровности поверхности — это и является результатом детекции. Конкурентные иностранные подобные решения работают с очень небольшой площадью и стоят очень дорого.

[@northzen]

А можете скинуть пару картинок с обычной камеры при статичном свете без отражений? Я как раз интересуюсь стерео и 3D реконструкцией. Интересно было бы посмотреть, как отработают те методы, что я знаю.

[@DimaBond174]

Не думаю чтобы Заказчик это одобрил… и это не результат труда в домашних хобби-проектах (как то FastMemPool). На публику выношу только то что я в свободное от основной работы делаю дома… Из хобби нести на работу можно, а с работы в хобби уже воровство…

[@svr_91]

В этом куске кода

if (deallocated  == (Leaf_Size_Bytes - available))
      {  // everything that was allocated is now returned, we will try, carefully, reset the Leaf
        if (leaf_array[head->leaf_id].available.compare_exchange_strong(available,  Leaf_Size_Bytes))
        {
          leaf_array[head->leaf_id].deallocated  -=  deallocated;
        }
      }

Что будет, если после compare_exchange_strong поток «зависнет» (планировщик потоков ос например отдаст ядро комуто другому) и в этот момент другие потоки продолжат пользоваться этим листом, забирая и возвращая куски памяти?

[@DimaBond174]

Ничего страшного:

// тут все синхронизировались и узнают что было вычитание:
      const int  deallocated  =  leaf_array[head->leaf_id].deallocated.fetch_add(real_size, std::memory_order_acq_rel)  +  real_size;
      int  available  =  leaf_array[head->leaf_id].available.load(std::memory_order_acquire);
      if (deallocated  == (Leaf_Size_Bytes - available))
      {  // everything that was allocated is now returned, we will try, carefully, reset the Leaf
        if (leaf_array[head->leaf_id].available.compare_exchange_strong(available,  Leaf_Size_Bytes))
        {
// Это самая жёсткая синхронизация потому как "The default behavior of all atomic operations in the library provides for sequentially consistent ordering":
          leaf_array[head->leaf_id].deallocated  -=  deallocated;
        }
      }

все возможности для неадекватного поведения закрыты согласно en.cppreference.com/w/cpp/atomic/memory_order

[@svr_91]

Нет, дело не в memory order, а в простой логике.
Например (это только один из примеров, думаю можно найти больше)
1) Мы дошли до последней строчки этого кода, не успев ее выполнить и «зависли»
2) При этом available у нас уже сброшено в Leaf_size
3) Какойто поток приходит, видит что в available чтото есть, берет память и отдает.
4) Потом опять берет много-много (всю память) и всю ее отдает обратно. В результате available == 0, а в deallocated 2 * Leaf_Size_Bytes, мы не проходим проверку if (deallocated == (Leaf_Size_Bytes — available)) и выходим из этого куска кода
5) Просыпается наш зависший поток, и производит уменьшение. В результате deallocated == Leaf_Size_Bytes
6) Никто не может взять новый кусок памяти, так как available == 0
7) Никто не может войти в этот кусок кода, так как для того чтобы сюда войти, нужно выполнить освобождение, а освобождать нечего, так как никто ничего не может взять

[@DimaBond174]

Вот я и пишу, что ничего страшного: никто не начал работать с деаллоцированными страницами — просто из пула выбыл один лист. Кроме этого вероятность описанной Вами драмы крайне мала:
Кто-то должен суметь успеть между compare_exchange_strong и следующей операцией sequentially consistent ordering(которая всех тормозит и выравнивает) сделать следующее:
1) Получить кусок памяти и зафиксироваться в available сделав минимум 2 atomic операции
2) Не совершая никакой полезной работы сразу пойти возвращать полученную память (добавление вызова в call stack, проверки аллокации всякой математикой)
3) Сделать ещё 2 atomic вызова получив текущие deallocated и available,
и при этом обогнать того кто ещё до пп1) стоит всё ждёт со своим sequentially consistent ordering (на deallocated -= deallocated; )

Конечно в бесконечной вселенной на бесконечном отрезке времени любую ненулевую вероятность если умножить на бесконечность — то мы получим гарантированное событие, но на этой же бесконечности ещё столько других багов — что потеря одного листа памяти из пула это самое безобидное что может произойти в этой жизни…

[@Roden37101]

...
template<class T, class FAllocator = FastMemPoolNull >
struct FastMemPoolAllocator : public std::allocator<T>  
...
std::unordered_map<int,  int>  umap2(1024, std::hash<int>(), std::equal_to<int>(),  FastMemPoolAllocator<std::pair<const int,  int>>());

так лучше не делать, в c++17 не просто так задеприкейтили половину функций в std::allocator
в конструкторе unordered_map происхоит усечение до std::allocator, в котором нет ни одной виртуальной функции
см.
en.cppreference.com/w/cpp/memory/allocator_traits
если уж хочется от чего-то унаследоваться см.
en.cppreference.com/w/cpp/memory/memory_resource
en.cppreference.com/w/cpp/memory/polymorphic_allocator

[@DimaBond174]

Спасибо за комментарий.
Шаблоны в работе использую достаточно редко, когда реально какой-то код типовой… пробелы есть.
Почитал про std::pmr::polymorphic_allocator, кажется штука полезная если есть проблемы с сопоставлением типов разных контейнеров…

Можете привести пример из жизни — как (и какие) изменения в шаблоне FastMemPoolAllocator
могли бы решить решить какую-то реальную задачу?