Комментарии 16
Lock-free структурами данных я заинтересовался именно благодаря борьбе с мьютексами.
Вместо реализации схемы на мьютексах проще сравнить, например, std::map/std::queue под мьютексом с lock-free аналогом. Сразу скажу, результат будет неоднозначный: можно получить как проседание, так и взлет производительности. Все зависит от железа и задачи. Общее наблюдение — чем «сервернее» железо, тем хуже мьютексы и лучше lock-free.
Мысль интересная, только времени, боюсь, на это уйдет много, а результат неясен.
Дело в том, что для разных схем SMR часто приходится писать разные специализации контейнеров. Для HP-like схем — HP, HRC, PTB, — мне удалось свести реализацию контейнеров к одной, а вот для RCU пришлось писать отдельные специализации template.
Боюсь, для гипотетического cds::gc::MTX вылезет ещё одна специализация.
ИМХО, мы увидим, насколько быстрее/медленнее HP по сравнению с MTX, но ничего не сможем сказать о контейнере. А ведь в программе нам важен именно контейнер, а не костыль к нему в виде схемы управления памятью (SMR — именно костыль).
В функции Scan() вместо free(dlist[i]); вызывать деструктор (pDisposer()) и сохранять указатель на выделенную память в некий ограниченный массив freelist[] локальный для каждого потока.
А при необходимости выделении памяти для нового элемента брать из freelist указатель на свободную память и использовать placement new для размещения в ней нового объекта, и только если freelist пуст, то использовать обычный new.
const int F = 100;
int fcount = 0;
void* freelist[F]; // per-thread array
void Scan() {
// ...
if ( binary_search(dlist[i], plist))
new_dlist[new_dcount++] = dlist[i];
else if(fcount < F) {
freelist[fcount++] = dlist[i]; // вместо free(dlist[i]);
pDisposer( dlist[i] ); // p->~T();
}
else
free(dlist[i]);
// ...
}
Для создания объекта:
T *p;
if(fcount > 0)
p = new(--fcount) T();
else
p = new T();
Даже если стандартные new/delete в компиляторе/рантайме имеют локальный для каждого потока пулы предвыделенной памяти и быстро находят в них свободное место нужно размера, то используя свои пулы:
— вы сможете вручную контролировать их размер
— не тратить пулы под объекты другого типа/размера
— за 1 сравнение находить свободную область нужного размера, если она есть
Прибавит это производительности при большом количестве удалений/вставок?
Вообще, я считаю, что эксперименты с аллокаторами полезны для собственного развития, но в 90% случаев бесполезны для дела. Хороший аллокатор — это хардкор, основанный на знании тонкостей конкретной операционки.
Я смотрел ваш доклад на конференции, и Вы там говорили, что epochs как-то связаны с RCU. Можно с помощью RCU реализовать то, о чем я говорю, или Вы что-то другое имели в виду?
Epoch-based reclamation (EBR), по большому счету, не связана с RCU. Классический RCU — это отдельная парадигма построения конкурентных контейнеров, вообще говоря, блокируемая. То, что я называю RCU (точнее, user-space RCU, uRCU), появилось как объединение lock-free подхода (под lock-free я здесь понимаю широкое толкование — атомарные операции и прочий изврат) и метода определения RCU quiescent state, то есть момента, когда данные можно безопасно физически освободить. Результирующая схема, как она вырисовывалась в libcds, концептуально похожа на EBR.
У hazard pointer в такой реализации есть один изъян.
Если один из удаляемых элементов сам содержит коллекцию объектов, который нужно удалять через retire — ну вот мы на 3-й стадии вызвали "удалятор" основного объекта. Он вызвал retire для ребёнка — а мы же в функции scan, где оказались как раз потому, что список заполнен! И вот тут мы либо рекуррентно зациклимся, либо будет исключение.
Я в итоге создаю новый, пустой список и меняю с рабочим местами. Дальше в локальном списке делаю всё, что нужно для scan, при этом если окончательное удаление порождает новые элементы в retired, они идут в этот новый, изначально пустой список. Если вдруг и он переполнится (ну, допустим каждый объект порождает сотню других в этот список) — оно вполне рекурсивно разруливается само. А по окончании можно меньший из получившихся влить в больший и всё, задача решена.
Да, согласен.
Иерархические hazard pointer'ы практически не поддерживаются, так как от строгой древовидной иерархии очень просто случайно перейти к циклическому графу, в котором уже никакие ухищрения не помогут (или помогут путем усложнения схемы HP и накладывания каких-то дополнительных требований на данные).
Внедрить иерархический HP, описываемый Вами, в принципе можно: сейчас есть classic_scan и inplace_scan, на выбор. Можно добавить hierarchical_scan, учитывающий Ваш случай и первым делом копирующий массив retired в локальный массив (видимо, new'ed, что в мире lock-free считается дурным тоном). Ну и раз уж у нас появится new, то достаточно move (подмена массивов, так как retired фактически thread local data) вместо copy полного массива.
Ну как "чисто случайно"… Если retire по сути заменяет собой delete (т.е. всё равно удали, но как-нибудь потом), то циклический граф это в любом случае ошибка, и скорее всего фатальная, и её нужно фиксить где-то в самом алгоритме. Подстилать соломки, чтобы допустить корректное разруливание double-free — вроде не очень идея. По мне, так лучше сразу падать, и чем раньше, тем лучше (будет больше актуального контекста). В общем, если возникают циклический граф — "на этом наши полномочия всё, исчерпаны". Содержимое retired-списков среди всех потоков не должно совпадать ни одним элементом, можно прямо sanitizer такой приделать, чтоб сохранить время пользователю.
Но помимо "академических библиотечных алгоритмов" хазарды полезны и в прикладных задачах, более приземлённых. Что практически решал — мониторинг процесса. Он там что-то у себя внутри делает; текущее состояние расшаривает, и вся цель — доступ к этому расшаренному. Без ограничений "никаких new" и т.д. Т.е. нет изначально lock-free алгоритма, есть обычная задача, вполне однопоточная, но процесс которой просто хочется показать наружу, и желательно с минимальным оверхедом. И тут сразу пучок вариантов. Можно писать лог (на диск, в память — неважно). Можно в циклический буфер, чтоб не пухнуть. Но недостаток — данные нужно как-то "причесать", сериализовать. Если ссылки на какие-то внутренние объекты — надо, по идее, разыменовать. Или их тоже заставить знать, что за ними следят, чтоб тоже логгировались. В итоге оверхед есть, даже если реально никто не мониторит; задача не решена. Можно окружить мьютексами — и угу, даже если никто не следит, начать "проходить через рамку" в пустом аэропорту. Тоже не очень решение для просто мониторинга. Можно приделать рефкаунт, и даже атомик — и тоже весь мир встаёт подождать, пока мы его изменим и дадим всем знать, что "счётчик теперь такой-то". И вот тут как раз всплывают хазарды. У них единственный оверхед — в том, что переменная, где стейт — не в регистре, а атомик. Т.е. должна быть в памяти, volatile. В принципе, это тоже оверхед — но, пожалуй, минимальный по сравнению с другими. Процесс "публикует" свой стейт, просто расшаривая его через atomic. Ну и делает немного RCU — дописать к строчке в стейте слово = старую отбросить, дополненную опубликовать. Всё остальное — не его забота. А наблюдатель, в свою очередь, уже защищается хазардами, и через них получает, по сути, не самый актуальный стейт, а тот, что "заморожен" в хазарде, и на самом деле может быть уже retired.
Тут нет проблемы с циклическими графами, задача чисто прикладная. И заодно всплывают разные оптимизации, типа — если данные очень большие, то можно попробовать вызвать "мини-scan" для этого поинтера прямо сейчас; миллисекунда процессорного времени дешевле, чем гиг занятой памяти прямо сейчас (если повезёт).
Lock-free структуры данных. Внутри. Схемы управления памятью