[prog.c++] Тему с самодельными spinlock-ами закрываю. Не осилил

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

Поэтому эксперименты с реализацией spinlock-ов на чистом C++11 без привлечения внешних библиотек заканчиваю. Все, что удалось сделать, находиться вот в этой ветке Svn-репозитория. Лицензия у этого кода BSD-шная. Если кто-то хочет поковырять палочкой кучку -- you are welcome :) В принципе, я не против развить это во что-то нормальное, но только если этим будет заниматься кто-то с лучшим, чем у меня, пониманием предметной области. Меня хватит разве что на написание кода, дилетантские вопросы и провинциальную критику ;)

Что сейчас есть в spinlockspp? Есть самый простой спинлок, под названием trivial-lock, работающий на основе механизма test-test-and-set.

Есть очень тривиальная, но весьма медленная, реализация ticket-lock-а. В ней два атомарных счетчика. В то время как классическая реализация ticket-lock-а использует union, в котором лежат, скажем, одна 32-битовая переменная и структура из двух 16-битовых. Либо же просто одна 32-х битовая переменная, но для операции unlock задействуются только 16 бит из нее (т.е. применяется атомарный инкремент как будто к независимой 16-битовой переменной). Оказалось, что стандартными средствами С++11 этот фокус просто так не проделать. Поскольку std::atomic_fetch_add принимает в качестве аргумента не адрес ячейки памяти, а указатель на объект std::atomic. Тогда как C-шная функция atomic_fetch_add получает именно что адрес. И в C-шную fetch_add засунуть адрес части счетчика из ticket-lock-а несколько проще, чем в C++ (а в C++ прибегать к грязным хакам стремно, если честно). Чтобы задействовать C-шную fetch_add в C++ном коде, нужно, чтобы компилятор поддерживал и C++11, и C11. Но тот же Visual C++ 2013, например, не поддерживает C11. Поэтому ticket-lock такой примитивный.

Зато ticket-lock, в отличии от trivial-lock, является "честным".

Есть очень шустрая, но "нечестная" реализая RW-lock-а под названием dvyukov_rw_lock, разработанная Димой Вьюковым для проекта LLVM.

Отдельный вопрос -- это организация паузы в спинлоках, для случая, когда установить блокировку не удалось. Этот вопрос решается backoff-ами. Каждый спинлок реализуется шаблонным классом, параметризуемым конкретным типом backoff-а. В spinlockspp есть два платформенно независимых типа backoff-а. Это yield_backoff, который вызывает std::thread::yield(). И simple_inc_backoff_t, который использует простой цикл с инкрементом целочисленной переменной. Верхняя граница этого цикла постоянно увеличивается, так что при каждом новом ожидании пауза удлиняется.

Есть еще платформенно зависимый backoff под названием cpu_pause_backoff_t. Который использует инструкцию PAUSE для процессора. Правда, поскольку C++ не имеет стандартных средств выдачи таких инструкций, пришлось мудрить с #if/#else/#endif. С помощью онлайн компиляторов удалось получить вот такую штуку. Вроде под Visual C++/GCC/Clang/ICC должно работать. Понятное дело, что при переходе на другую платформу или другой компилятор, нужно будет делать новую реализацию SPINLOCKSPP_CPU_PAUSE.

Собственно, откуда пошли spinlock-и. От желания отказаться от использования ACE Framework и перейти только на стандартную библиотеку C++11. Но нужны были RW-мутексы, которых в C++11 нет. Зато есть средства работы с atomic-ами, поэтому появилась мысль наваять замену ACE_RW_Thread_Mutex на C++ных atomic-ах. В простой форме это было сделано и использовано.

А вот попытка сделать что-то более солидное закончилось пониманием, что одними только средствами C++11 обойтись не получится. А именно в этом и был интерес: оставаться только в рамках стандартной библиотеки и не адаптировать свой код под каждую платформу.

Но одним только C++11 не обойтись. Нужно глубоко погружаться в детали платформы и компилятора. Для этого нужно иметь соответствующую квалификацию. Либо желание и время ее приобрести. Чего в моем случае нет. Посему работы прекращаю.

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

Ну а если спинлоки таки нужны, то лучше не делать их самому. А поискать что-нибудь готовое. Насколько много такого готового -- фиг знает. Для чистого C мне понравился код библиотеки Concurrency Kit. Есть ли что-то подобное для C++, да еще не под GPL лицензией -- это вопрос. Мне ничего на глаза не попалось. Разве что в составе каких-то больших библиотек/проектов (как с тем же rw_spinlock-ом от Димы Вьюкова).

[prog] Пара ссылок на материалы, посвещеные примитивам синхронизации

Очень интересная статья "Spinlocks and Read-Write Locks" на сайте locklessinc.com. Обсуждается несколько вариантов spinlock-ов и read-write spinlock-ов, с кодом, результатами замеров и последовательным изложением достоинств и недостатков каждого метода.

Большая подборка разнообразных ссылок: Reader/Writer Locking and Beyond. Подборка от 2009-го года, поэтому какие-то ссылки уже наверняка "протухли", но тем не менее, общее их количество внушаить.

PS. Подмывает взяться за реализацию ticketlock (mutex-like spinlock) и rwticket (read-write spinlock) из первой статьи. Дабы включить эти реализации в cppinlocks/cppspins. Но есть ощущение, что рискую ввязаться совсем не в свое дело...

[prog.c++] Макросы зло, но иногда...

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

Первый фокус подсмотрел в библиотеке Catch. Эта header-only библиотека предлагает еще один подход к реализации unit-тестирования в C++. Оформленный с помощью Catch код теста очень сильно напоминает то, что в свое время я делал на Ruby с Ruby-новыми блоками кода. Вот пример из туториала Catch-а:

[prog.c++.sobjectizer] Етить-колотить, а ведь ровно год прошел!

Ровно год назад у меня в блоге появилась заметка о SObjectizer-5.1.2. Сейчас перечитываешь, и не верится, что уже год прошел.

Оглядываясь назад можно сказать, что мое недолгое возвращение в Интервэйл сильно и, к сожалению, отрицательно сказалось на развитии SObjectizer-а. Фактически, произошла остановка работы почти на четыре месяца, с января по апрель. Да и затем погружение в разработку для меня было медленным и болезненным. Особенно после всего того управленческого звиздеца, в который довелось окунуться. Но вроде как время действительно лечит, ща уже сильно полегче, так что работа над SObjectizer-ом идет уже в нормальном режиме.

Из того, что озвучивалось в планах год назад не срослось только с демо-проектом. Это пока terra incognita. Впрочем, со временем здесь мы тоже обязательно продвинемся вперед, если, конечно, не придется отвлекаться на что-то еще.

В остальном сделать удалось немало. После 5.1.2 были версии 5.2 (включая так же 5.2.1, 5.2.2 и 5.2.3), 5.3 и 5.4, удалось сделать ознакомительную документацию. Сейчас идет активная работа над версией 5.5.

Так что интересно будет оглянуться назад еще через год :)

Пользуясь случаем хочу поблагодарить всех причастных к разработке SObjectizer-а! Спасибо!

[prog.question] Хорошее ли это название для C++ библиотеки: cppinlocks?

Возвращаясь к недавней теме. Нужно решить одну из самых сложных проблем в программировании: выбрать хорошее название для идентификатора :) В данном случае название самого верхнего пространства имен для маленького проекта, в котором будут собраны самодельные реализации спинлоков (с использованием только средств из стандартной библиотеки C++11).

Пока лучшее, что удалось придумать -- это cppinlocks.

Другой вариант, который, правда, нравится меньше, cppspins.

В общем, очень нужна помощь общественности :)

Upd. По итогам прений ;) библиотека пока живет под именем spinlockspp.

PS. Сейчас код spinlock-ов лежит внутри кода SObjectizer. Нужно выделить его в отдельный подпроект. Но не столько для того, чтобы развивать дальше (я так понял, что в случае spinlock-ов каждый сам себе велосипедит, кто во что горазд). А для того, чтобы тесты spinlock-ов не приходилось гонять при полном билде SObjectizer. Ну и чтобы можно было где-то отдельно разместить бенчмарки. Кстати говоря, кто-нибудь может указать на готовые бенчмарки для примитивов синхронизации, которые можно заточить под себя?

PPS. Много положительных эмоций получил от обсуждения темы нужности такой библиотеки на LOR-е. Узнал про себя много интересного, анонимные тимлиды-эксперты жгут напалмом :) Полезный сухой остаток: указали на мой просчет в реализации простого спинлока. Вместо более эффективного алгоритма test-test-and-set у меня был задействован test-and-set. Тут явное следствие моей некомпетентности. Скопипастил кусок из документации к std::atomic_flag. Хотя на алгоритм ttas, как выяснилось, мне в свое время указывали. Но почему-то я не переделал реализацию spinlock_t на более оптимальную. Переделаю уже в cppinlocks.

[prog.c++] Версия 1.0.0 библиотеки timertt

Теоретические изыскания, начатые в двух заметках про таймеры (#1, #2) завершились вот таким практическим результатом -- на SourceForge выложен первый релиз библиотеки timertt.

Библиотека timertt -- это header-only библиотека, не имеющая внешних зависимостей, базирующаяся только на стандартной библиотеке C++11 (правда, нужно, чтобы там была корректная реализация std::chrono::steady_clock, иначе будут глюки при коррекции локального времени). Должна быть кросс-платформенной, т.к. никаких системно-зависимых вещей в ней нет. Я ее проверял под Visual C++ 2013 (Windows) и GCC 4.9.1 (Windows, Linux).

Лицензия: 3-х секционная BSD. Т.е. использоваться может без проблем как в открытых, так и в закрытых проектах.

Библиотека поддерживает только таймеры на основе тайм-аутов, т.е. таймеры, которые должны сработать через сколько-то миллисекунд (секунд, минут и т.д.) после момента активации таймера. wallclock-таймеры не поддерживаются.

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

Библиотека поддерживает три таймерных механизма: timer_wheel, timer_heap и timer_list, у каждого из которых есть свои преимущества и недостатки. Может поддерживаться большое количество таймеров (сотни тысяч, миллионы или даже десятки миллионов) и обеспечивается высокая скорость обработки таймеров (до нескольких миллионов в секунду, но это зависит от времени работы связанных с таймером пользовательских событий).

В коде все это выглядит приблизительно следующим образом:

#include <iostream> #include <cstdlib> #include <timertt/all.hpp> using namespace std; using namespace std::chrono; using namespace timertt; int main() {    timer_wheel_thread_t tt;    // Timer thread must be started before activation of timers.    tt.start();    // The simple single-shot timer.    tt.activate( milliseconds( 20 ),          []() { cout << "Simple one-shot" << endl; } );    // The simple periodic timer.    // Will work until timer thread finished.    tt.activate( milliseconds( 20 ), milliseconds( 20 ),          []() {             static int i = 0;             cout << "Simple periodic (" << i << ")" << endl;             ++i;          } );    // Allocation of timer and explicit activation.    auto id1 = tt.allocate();    tt.activate( id1, milliseconds( 30 ),          []() {             cout << "Preallocated single-shot timer" << endl;          } );    // Periodic timer with timer preallocation, explicit activation    // and deactivation from the timer action.    auto id2 = tt.allocate();    tt.activate( id2, milliseconds( 40 ), milliseconds( 15 ),          [id2, &tt]() {             static int i = 0;             cout << "Preallicated periodic (" << i << ")" << endl;             ++i;             if( i > 2 )                tt.deactivate( id2 );          } );    // Single-shot timer with explicit activation and deactivation    // before timer event.    auto id3 = tt.allocate();    tt.activate( id3, milliseconds( 50 ),          []() {             cerr << "This timer must not be called!" << endl;             std::abort();          } );    tt.deactivate( id3 );    // Wait for some time.    this_thread::sleep_for( milliseconds( 200 ) );    // Finish the timer thread.    tt.shutdown_and_join(); }

Библиотека разрабатывалась для замены ACE в проекте SObjectizer, поэтому все, что связано с timertt, находится на SourceForge:

• архивы с исходными текстами доступны в секции Files. Архив timertt-1.0.0-headeronly.7z содержит только основной заголовочный файл со всей функциональностью timertt. Архив timertt-1.0.0-full.7z содержит так же тесты, примеры и сгенерированный посредством Doxygen API Reference Manual;
• основная документация для проекта собрана в Wiki. На данный момент она на русском языке, поскольку так было быстрее. Но потихонечку документацию буду переводить на английский. Если кто-то вызовется помочь с переводом, буду очень признателен, т.к. у меня это займет много времени, а результат будет весьма так себе;
• исходники лежат в Subversion-репозитории на SourceForge. Релизные версии в tags/timertt, находящиеся в разработке версии в branches/timertt. В Svn на SF, а не в git-е на GitHub-е потому, что мне timertt нужна в SObjectizer-е, и в SObjectizer уже давно используется подключение зависимостей через svn:externals.

[prog.c] Может быть кому-то пригодится: Concurrency Kit

Наткнулся на днях на Concurrency Kit. Позиционируют себя как "Concurrency primitives, safe memory reclamation mechanisms and non-blocking data structures for the research, design and implementation of high performance concurrent systems." Краткий список того, что предоставляет библиотека: "atomic operations, hardware transactional memory, memory barriers, hash tables, list, ring, stack, fifo, bitmap, safe memory reclamation, scalable locks, execution barriers, asymmetric synchronization and more."

Чистый C. Похоже, что поддерживаются только Unix-ы, без Windows и Visual C++. Лицензия BSD.

Сам глубоко не смотрел, не качал, не запускал. Но в свой склерозник внес.