[prog.c++] Необычные вещи из многопоточности, которыми довелось позаниматься за последнее время

Зафиксирую в склерознике то, что довелось недавно делать. На случай, если когда-нибудь представится возможность рассказать поподробнее.

---

Специализированный mutex, который в сложившейся терминологии C++ной библиотеки можно было бы назвать как recursive_shared_timed_mutex.

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

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

Реализация самая простая, без наворотов, на базе обычных C++ных mutex и condition_variable. В принципе, если текущая версия окажется слишком тормознутой, то можно будет упороться и наколхозить тоже самое на atomic-ах. Но пока в этом надобности не возникло.

---

Две специальные, заточенные под предметную область версионированные структуры данных.

В моем представлении версионированные структуры -- это такие, в которых каждый пользователь видит свою независимую версию этой самой структуры.

Чтобы было понятнее, давайте вообразим себе std::map<int, std::string>, с которым несколько нитей работают одновременно. Первая нить читает значения по ключам 0, 1, 2, 3, 4, 5, вторая нить читает значения по ключам 4, 5, 6, 7, 8, а третья нить изменяет значение для ключа 0, удаляет значение для ключа 5 и добавляет значения с ключами 9, 10 и 11.

Так вот фокус в том, что пока первая и вторая нить держат у себя "старую" ссылку на этот map, они не видят изменения, которые вносит третья нить. Происходит это потому, что первая и вторая нить работают с исходной версией map, а третья нить, как только начинает модификации, получает свою персональную новую версию, о которой первые две нити не знают.

Такой механизм работы означает, что третья нить не может просто так сохранить свои изменения. Требуется специальная операция commit, после успешного выполнения которой версия от нити №3 сможет заменить собой основную версию map.

При этом нити №1 и №2 все равно не будут видеть новую версию, поскольку они работают с map через "старую" ссылку. Чтобы перейти на актуальное содержимое map им нужно обновить эту ссылку у себя, т.е. явным образом обратиться к map с просьбой дать ссылку на последнюю актуальную версию.

Может оказаться так, что кроме нити №3 модификации в map сейчас вносит и нить №4. И свой commit четвертая нить может выполнить еще до того, как третья нить завершит свои модификации. В этом случае при commit-е нить №3 обнаружит, что актуальный map уже совсем другой.

Это все сильно напоминает работу с ветками в VCS: ты отпочковался от master-а (или trunk-а), сделал изменения в своей ветке, хочешь влить в master, а master-то уже ушел вперед. И нужно делать слияние (merging). Иногда оно происходит автоматически и безболезненно, а иногда приходится разбираться с конфликтами.

Так же и в версионированных контейнерах -- иногда нужно разбираться с конфликтами. И я не зря сказал выше, что контейнеры делались под специфику прикладной задачи. Эта специфика как раз и определяла, каким образом возникающие конфликты должны разруливаться в автоматическом режиме.

Один тип контейнера был вариацией на тему дерева поиска, но не простого, а чего-то больше похожего на префиксное дерево.

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

[prog.c++] Простой способ ускорить поиск в map/unordered_map в случае "тяжелых" ключей

Все знают про наличие в std::map/unordered_map методов find. Но, наверное, не все знают, что у этого find-а есть несколько вариантов. Кроме старого и привычного:

iterator find( const Key& key );

В std::map начиная с C++14 есть еще и:

template< class K > iterator find( const K& x );

А в std::unordered_map второй вариант find-а был добавлен в C++20.

Что же следует из того, что в find можно передать не Key, которым мы параметризовали свой map/unordered_map, а какой-то другой тип?

Следует то, что мы можем сделать поиск в map/unordered_map более эффективным если тип Key дорог в конструировании, например, когда внутри Key есть std::string-и или другие типы, динамически выделяющие и освобождающие память.

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

using full_key_t = std::pair<std::size_t, std::string>;

Соответственно, поиск выполнялся как-то так:

const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(full_key_t{id, description}); it != _map.end()) {   ... }

Проблема в том, что экземпляр full_key_t нужно полностью сконструировать. А значит нужно сделать полную копию description и поместить эту копию в новый объект full_key_t. Что недешево. И, что особенно обидно, объект full_key_t разрушается сразу после завершения поиска. Т.е. мы создаем временный ключ, тратим на это время, а затем тупо выбрасываем временный ключ за ненадобностью.

К счастью, упомянутые выше "новые" варианты find-а позволяют нам избежать создания "тяжелых" экземпляров full_key_t. Теперь в C++ можно делать вот так:

using light_key_t = std::pair<std::size_t, const std::string*>; ... const auto id = get_id(...); const std::string & description = get_description(...); if(const auto it = _map.find(light_key_t{id, &description}); it != _map.end()) {   ... }

Однако, чтобы это работало, нужно сделать несколько дополнительных телодвижений. Давайте рассмотрим их на примере std::unordered_map.

Первое, что нам потребуется -- это такой тип хэш-функции, который будет применим как к full_key_t, так и к light_key_t. Поскольку обычно хэш для unordered_map -- это структура со специально написанным operator(), то мы можем просто сделать несколько перегрузок operator():

struct special_hash_t {    using is_transparent = void;    std::size_t    operator()(const full_key_t & k) const noexcept    {       return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 +             std::hash<std::string>{}(second_key_part(k));    }    std::size_t    operator()(const light_key_t & k) const noexcept    {       return std::hash<std::size_t>{}(k.first) + 0x9e3779b9 +             std::hash<std::string>{}(second_key_part(k));    } };

Где second_part_key -- это вспомогательные функции вида:

[[nodiscard]] const std::string & second_key_part(const full_key_t & k) noexcept {    return k.second; } [[nodiscard]] const std::string & second_key_part(const light_key_t & k) noexcept {    return *(k.second); }

Внутри special_hash_t можно было обойтись и без них, но вот на следующем шаге они нам сильно помогут.

А следующим шагом будет определение собственного компаратора, который может сравнивать full_key_t и light_key_t на равенство. Этот компаратор мы подсунем std::unordered_map в качестве параметра шаблона KeyEqual. Для нашего примера компаратор может выглядеть так:

struct special_equal_to_t {    using is_transparent = void;    template<typename K1, typename K2>    bool    operator()(const K1 & k1, const K2 & k2) const noexcept    {       return (k1.first == k2.first) &&             (second_key_part(k1) == second_key_part(k2));    } };

За счет того, что в special_equal_to_t у нас operator() -- это шаблон метода, то он может принимать разные сочетания: как full_key_t с light_key_t, так и light_key_t с full_key_t. Здесь функции second_key_part помогают избежать дублирования кода.

Ключевой момент в этом всем -- это наличие определения is_transparent в special_key_t и special_equal_to_t. Без такого вложенного типа вся обсуждаемая машинерия с "новыми" find работать не будет. Причем, если забыть определить is_transparent, то компилятор может выдать такую простыню невнятных сообщений об ошибках, что причина проблемы будет совершенно непонятна (тут, конечно же от степени вменяемости компилятора зависит).

Далее остается просто определить тип нужного нам unordered_map:

using values_map_t = std::unordered_map<       full_key_t,       your_value_type,       special_hash_t,       special_equal_to_t>;

Какой же выигрыш дает этот трюк и дает ли вообще?

Если строковые ключи поиска короткие, т.е. срабатывает small string optimization (SSO), то практически не дает. Но вот если строчки достаточно длинные, чтобы SSO остался не у дел, то разница почти в два раза по моим замерам.

Под катом полнофункциональная программка, которая демонстрирует данный подход. Так вот, на i7-8550U с VC++ из VisualStudio 17.4.0 она выдает, например, следующие результаты:

*** find_by_full_key: 1512721us ***
values found: 10000000
*** find_by_light_key: 844164us ***
values found: 10000000

Тогда как MinGW 13.2.0 на той же машине показывает время чуть получше и все равно с почти что двухкратным разрывом:

*** find_by_full_key: 1137556us ***
values found: 10000000
*** find_by_light_key: 557952us ***
values found: 10000000

Так что трюк вполне себе рабочий. Но есть с ним две небольшие проблемки:

• про него легко забыть, особенно когда голова забита решением прикладных проблем, а глаз уже "замылился";
• нужно помнить про вложенный тип is_transparent, без него не работает, а компилятор своими сообщениями может только запутать.

Собственно, данный пост возник для того, чтобы зафиксировать этот трюк в склерознике (в особенности его часть про is_transparent).

[prog.c++] Настройка библиотеки под нужды пользователя чисто C++ными средствами

Подсмотрел вот в этом блог-посте - A New Approach to Build-Time Library Configuration - интересный трюк, который захотелось утащить к себе в склерозник на всякий случай.

Допустим, что мы сделали библиотеку. И допустим, что мы хотим дать пользователю как-то кастомизировать поведение библиотеки под себя во время компиляции.

Например, допустим, что мы используем в библиотеке какие-то временные вектора на стеке (скажем std::array<unsigned char, N>) и пользователь должен уметь управлять значением N. Чтобы он мог увеличить N когда это нужно или уменьшить N когда не нужно.

Традиционно в C++ для этих целей используют унаследованный из чистого Си подход с определением символов (они же define-ы). Например, определяют MY_LIB_DEFAULT_N через ключики компиляции. Что-то вроде:

g++ -D MY_LIB_DEFAULT_N=10240 ...

А в коде библиотеки мы делаем что-то вроде:

#if !defined(MY_LIB_DEFAULT_N)   #define MY_LIB_DEFAULT_N 4096 #endif namespace my_lib { constexpr tmp_array_size = MY_LIB_DEFAULT_N; ... void some_func() {   std::array<unsigned char, tmp_array_size> tmp_array;   ... } } /* namespace my_lib */

Когда таких ручек для тонкой настройки много, все они собираются в некий user-config.h, который должен быть предоставлен пользователем библиотеки (а дефолтная версия user-config.h может генерироваться при установке библиотеки). Получается что-то вроде:

#define MY_LIB_DEFAULT_N 10240 #define MY_LIB_LOGGING_POLICY 0 #define MY_LIB_TRACING_MODE 3 ...

В самой же библиотеке мы имеем специальный заголовочный файл impl/config.h, который будет иметь вид:

// Подключаем то, что выставил пользователь. #include "user-config.h" // А потом разбираемся с тем, что пользователь выставил или не выставил. #if !defined(MY_LIB_DEFAULT_N)   #define MY_LIB_DEFAULT_N 4096 #endif #if !defined(MY_LIB_LOGGING_POLICY)   #define MY_LIB_LOGGING_POLICY 2 #endif #if !defined(MY_LIB_TRACING_MODE)   #define MY_LIB_TRACING_MODE 10 #endif ... // Далее преобразуем define-ы в типизированные константы.

Для проверки наличия файла user-config.h, как показано в упомянутом выше блог-посте, можно использовать __has_include:

// Подключаем то, что выставил пользователь. #if __has_include("user-config.h"   #include "user-config.h" #endif // А потом разбираемся с тем, что пользователь выставил или не выставил. #if !defined(MY_LIB_DEFAULT_N)   #define MY_LIB_DEFAULT_N 4096 #endif #if !defined(MY_LIB_LOGGING_POLICY)   #define MY_LIB_LOGGING_POLICY 2 #endif #if !defined(MY_LIB_TRACING_MODE)   #define MY_LIB_TRACING_MODE 10 #endif ... // Далее преобразуем define-ы в типизированные константы.

Но это Си-ное наследие. А ведь можно использовать и чисто C++ные механизмы.

Так, в нашем impl/config.h может быть:

namespace my_lib { ... namespace config_defaults {   constexpr std::size_t tmp_array_size = 4096;   constexpr logging_policy_t logging_policy = logging_policy_t::minimal;   constexpr tracing_mode_t tracing_mode = tracing_mode_t::runtime_control;   ... } /* namespace config_defaults */ using namespace config_defaults; // А вот и трюк. } /* namespace my_lib */ // Подключаем то, что выставил пользователь. #if __has_include("user-config.h"   #include "user-config.h" #endif

Теперь пользователь в своем user-config.h может написать, например, так:

namespace my_lib { constexpr std::size_t tmp_array_size = 10240; constexpr logging_policy_t logging_policy = logging_policy_t::detailed; constexpr tracing_mode_t tracing_mode = tracing_mode_t::off;   ... } /* namespace my_lib */

И эти значения будут иметь больший приоритет, чем те, которые были определены в нашем my_lib::config_defaults, а затем введены в область видимости my_lib через using namespace.

---

Любопытно, что что-то похожее мы использовали в RESTinio для упрощения настройки свойств сервера (пример). Но у нас нужно было наследоваться от trait-класса. А тут без наследования, что для каких-то случаев гораздо удобнее.

[soft.tools] FAR Manager и BOM-маркер в начале каждого нового текстового файла

Много-много лет пользуюсь FAR-ом но с таким приколом столкнулся впервые...

В конце 2024-го года обзавелся новым рабочим Windows-ноутбуком, но из-за болезни очень мало им пользовался. Теперь по мере возврата в нормальный режим сижу за ним все больше и больше. Установленным там с нуля FAR для меня основной инструмент по работе с файлами.

И вот внезапно © выяснилось, что при создании нового текстового файла по Shift-F4 в кодировке utf-8 FAR автоматически вставляет в начало файла BOM-маркер из трех байт. Которые, мягко говоря, уже давным давно никому никуда не упали (особенно когда приходится таскать файлы из Windows в Linux и обратно).

После чего облазил все диалоги с настройками в FAR-е, но не увидел способа "фичу" отключить.

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

• в командной строке FAR-а нужно ввести far:config и нажать Enter;
• в открывшемся списке параметров конфигурации нужно найти BOM (через CTRL+ALT+F);
• заменить true на false.

Очень выручил этот рецепт, поэтому решил утащить его к себе в склерозник.

[prog.c++] Впечатления от Google-овского sparsetable

Давеча довелось применить sparsetable из Google-овского sparsehash для представления разреженного вектора значений. Разреженный вектор в моем случае -- это вектор с обычной индексацией от 0 до N, где части элементов нет физически. Обращения к элементам идут именно по целочисленным индексам (к тому же индексы в моём случае были представлены std::uint32_t).

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

Тогда как sparsetable показал себя здесь очень и очень хорошо.

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

При том, что класс sparsetable отлично зарекомендовал себя именно как специализированная структура данных, не могу не отметить несколько неприятных особенностей реализации sparsetable, обусловленных как старым C++ стандартом, в рамках которого написан sparsetable (а это C++03), так и подходом к разработке софта в Google.

Зафиксирую здесь те из них, которые я нахожу принципиально важными. Очень надеюсь, что найду время и силы сделать форк реализации sparsetable, в котором постараюсь от этих проблем избавится. Но, к сожалению, не уверен получится ли.

Итак, поехали.

Поскольку sparsetable написан для C++03, то он не поддерживает move semantic. Вообще. Причем как для самого sparsetable -- там нет ни конструктора, ни оператора перемещения, хотя swap для sparsetable есть. Но, самое плохое, sparsetable не поддерживает movable-only типы, вроде std::unique_ptr. Т.е. из коробки не получится хранить в sparsetable экземпляры std::unique_ptr 🙁

Еще sparsetable не поддерживает strong exception safety. Там прямо в комментариях в коде написано, что следовало бы реализовать обработку ситуации, когда конструктор копирования для помещаемого в контейнер объекта бросает исключение. Если такое произойдет, то контейнер останется в хз каком состоянии.

И с exception safety там есть еще один прикольный момент: дело в том, что sparsetable выполняет переаллокацию памяти даже при удалении элемента. Т.е. да, вы вызываете erase, внутри erase sparsetable решает заменить блок из которого элемент изъят блоком меньшего размера, для чего обращается к аллокатору... А аллокатор, в принципе, может бросить исключение. Т.е. из erase может вылететь bad_alloc 🙁 Что неприятно, т.к. время от времени я пишу код, в котором для выполнения отката ранее внесенных изменений при исключении делаются erase для возврата модифицированных контейнеров к исходному виду. Представьте себе что в блоке catch или даже в деструкторе объекта вы вызываете erase для sparsetable, а он бросает bad_alloc 🥴

Ну и работа с памятью там имеет одну важную особенность. По умолчанию sparsetable использует собственный аллокатор под названием libc_allocator_with_realloc. Этот аллокатор, как следует из его названия, полагается на Си-шный realloc при переаллокации блоков данных. Но вот если std::realloc возвращает NULL, то sparsetable просто... прерывает работу программы через вызов std::exit. Понятно, что это особенности Google-овского софта, под нужды которого sparsetable и писался, но блин, представьте себе, что у вас сервер, который держит в ОП информацию о десятках тысяч текущий сессий. И вдруг весь этот сервер одномоментно падает из-за того, что при обработке запроса в рамках одной из сессий не удалось переаллоцировать блок в одном sparsetable. Как-то печально, как по мне 🙁

Плюс к тому исходный sparsetable содержит методы для какой-то странной сериализации/десериализации. Полагаю, что в Google от sparsetable это требовалось. Но зачем это всем остальным -- хз.

И совсем отдельная история -- это отношение sparsetable к несуществующим элементам. Так, константная версия operator[] возвращает константную ссылку. В том числе и на несуществующие элементы! Если значения по индексу i нет, то operator[] вернет константную ссылку на статический объект типа T. Что, помимо прочего, означает, что тип T должен быть default-constructible.

Из-за того, что sparsetable выдает несуществующие элементы за существующие, но с общим дефолтным значением, проистекает и то, что у sparsetable есть два типа итераторов. Обычный итератор, который возвращается посредством begin/end, и который итерируется, в том числе, и по несуществующим элементам. И специальный nonempty-итератор + специальные методы nonempty_begin/nonempty_end, которые следует использовать, если хочется пробежаться только по существующим элементам.

Могу предположить, что подобные заморочки с имитацией несуществующих элементов через общее дефолтное значение были полезны для реализации хэш-таблиц на базе sparsetable. Но если использовать sparsetable отдельно, то выглядит это несколько странно (мягко говоря 🤨)

---

В общем, под нужды заказчика sparsetable из sparsehash был вытащен, избавлен от части ненужного хлама, слегка доработан напильником для устранения проблем с компиляцией под C++20 и использования std::allocator. Но до глубокой модернизации sparsetable руки так и не дошли. Однако желание сделать это осталось. Буду надеятся, что это получится сделать.

---

Если кто-то из читателей никогда не слышал про sparsetable, то впечатление можно составить вот из этого описания: Implementation of sparse_hash_map, dense_hash_map, and sparsetable. Там первая часть как раз sparsetable и посвящена. Описание лаконичное, но толковое.

[prog.data.structures] В склерозник: ссылки на тему prefix/radix tree

Довелось недавно столкнуться с темой prefix/radix деревьев. По ходу изучения нашел несколько ссылок, которые для меня оказались полезными, поэтому зафиксирую их в склерозник, чтобы было проще найти в будущем.

Даю только ссылки, без пространных пояснений, уж извините меня за халтуру, но так проще.

Adaptive Radix Tree. Собственно, основная PDF-ка, с которой и следует начинать.

HAT-trie, a cache-conscious trie. Обзор сразу нескольких подходов к реализации префиксных деревьев и хеш-таблицы с переходом к рассказу об их комбинации HAT-trie. Плюс реализация этой идеи на C++.

Crit-bit trees и qp tries and crit-bit tries. Еще несколько вариаций на тему префиксных деревьев.

Akamai Radix Tree. Реализация на C++ radix tree от Akamai. Очень интересно если хочется посмотреть, как это дело можно реализовать. Хотя оформлена библиотека (в плане описания, документации, примеров и комментариев в коде), как по мне, бестолково. Поэтому разбираться не просто + реализация на многоэтажных шаблонах, так что требуется хорошее знание C++.

Compressing dictionaries with a DAWG и Directed Acyclic Word Graphs. Пара статей вокруг идей о том, как можно сократить объем данных в префиксном дереве.

Ну и вот эта ссылка регулярно всплывала, хотя напрямую к теме, вроде бы, не относится: Implementation of sparse_hash_map, dense_hash_map, and sparsetable.

От себя добавлю, что для сценария, в котором мне потребовалось что-то вроде prefix/radix дерево, "классический" вариант префиксного дерева вел к слишком большому расходу памяти. И, как я понял, это характерно для подобного рода деревьев, поэтому как раз и есть статьи о том, как уменьшить объем данных.

[prog.c++] Интересное чтиво про strict aliasing rule...

...лежит здесь: What is the Strict Aliasing Rule and Why do we care?

Документ далеко не новый, но если вы не в теме, то он будет, безусловно, полезен.

Из того, что стало откровением и открытием лично для меня (применительно к C++):

• в C++ содержимое другого объекта можно просматривать путем каста к char, unsigned char или std::byte. Т.е., грубо говоря, вы всегда можете сделать reinterpret_cast<char *>(other_pointer). Но это не распространяется на signed char. И отдельная история с std::int8_t/uint8_t: эти типы могут быть простыми синонимами для char и unsigned char, а могут быть и отдельными, самостоятельными типами (в таком случае на них правило char/unsigned char/std::byte не распространяется);

• оказывается, современные компиляторы могут понять, что делает std::memcpy и избавиться от реального вызова std::memcpy. Например, вот такой корректный способ получить float из int-а (при условии их одинаковых размеров):

  int src = ...;
  float dst;
  std::memcpy(&dst, &src, sizeof(src));

  в случае умного компилятора будет просто помещать в dst нужно значение без вызова memcpy;

• не знал раньше про common initial sequence. А это, как выяснилось, может стать архиважной штукой при работе с union:

  struct A { char type; ... };
  struct B { char type; ... };
  struct C { char type; ... };
  union U { A a; B b; C c; };
  
  U u;
  u.a = ...;
  if(u.b.type == ...) // (1)
  {...}

  Обращение к u.b в точке (1) легально не смотря на то, что U::b -- это неактивный в данный момент элемент union-а.

[linux] Если вам потребовался ArchLinux в Docker с пакетом из AUR...

...то вот эти ссылки могут оказаться полезны. По крайней мере мне помогли.

Arch_User_Repository. Официальная информация о том, что такое AUR и как ставить пакеты из AUR. Имеет смысл просмотреть хотя бы по диагонали, чтобы понимать, что к чему и почему.

Testing our package build in the Docker world. В принципе, основная статья, в которой вроде бы все собрано воедино в нормальном, лаконичном и более менее понятном виде.

Testing an Arch Linux package in Gitlab CI. Статья не совсем про Docker, но мне она оказалась наиболее полезна, т.к. там расписывается что и зачем делается.

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

ЗЫ. Т.к. после экспериментов с Docker-ом остается куча всяких устаревших (и не очень) образов, то найти простые способы поудалять лишние Docker-овские images и containers можно здесь: How To Remove Docker Images, Containers, and Volumes. Например:

$ docker image prune
$ docker rmi $(docker images -a -q)
$ docker rm $(docker ps -a -f status=exited -q)
$ docker stop $(docker ps -a -q)
$ docker rm $(docker ps -a -q)

[prog.c++] В склерозник: легковесная C++11 библиотека для работы с разделяемой памятью

На reddit-е увидел анонс header-only библиотеки mio, предоставляющей средства работы с memory-mapped-file IO. Решил зафиксировать ссылку на нее в склерозник, ибо несколько месяцев назад изучал, что из готового для этих целей есть в мире C++. И получалось, что самое толковое было только в Boost-е. Но Boost -- это достаточно тяжелая зависимость. А здесь легковесная кросс-платформенная библиотека без внешних зависимостей вообще. Под MIT-лицензией.

[prog.crypto] Склерозник: godzilla crypto tutorial

Когда-то давным-давно, когда пришлось познакомиться с SSL и основами криптографии, наткнулся на интересный ресурс: домашнюю страничку Питера Гатманна (Peter Gutmann).

Помимо прочего он написал и выложил в сеть большой набор PDF-ок со слайдами на тему информационной безопасности и криптографии: godzilla crypto tutorial. Помнится, я почерпнул оттуда много полезного. Так что с удовольствием рекомендую.

Кроме того, Питер разработчик большой C++ной библиотеки cryptlib. Сам я ее не применял, но в свое время смотрел. Мне она тогда понравилась больше, чем OpenSSL. (Интересующиеся так же могут глянуть на Crypto++ и Botan).

PS. Давно уже не занимался ничем, связанным с криптографией. А тут вдруг случайно наткнулся на собственный текст с упоминанием этих ресурсов и решил занести их в склерозник, на всякий случай.

[life.sport] Склерозник: сетки турниров “двойное, тройное и т.д. дыхание”

На случай, если кому-нибудь понадобится проводить спортивные турниры по системе “двойное дыхание” вот интересный сайтик: http://www.tournamentdesign.org/

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

PS. На случай, если кто-то, как я совсем недавно, не знает, что такое “двойное дыхание” или “минуска”, или “двушка”. Это такая система игры на выбывание, при которой участник покидает турнир не после одного поражения, как в простой олимпийской системе “игры на вылет” (плей-офф), а после двух. Т.е. ведется как бы два параллельных плей-оффа – верхняя сетка виннеров (т.е. игроков, которые пока не проиграли ни одной игры) и нижняя сетка лузеров (т.е. игроков, которые проиграли одну игру). Проигравшие в сетке виннеров продолжают турнир в сетке лузеров. Проигравшие в сетке лузеров выбывают окончательно.
Подробнее в Wikipedia на русском и на английском.

[prog] Склерозник: подсчет числа единичных битов в N-битовой последовательности

Никогда раньше не приходилось с такой задачкой сталкиваться, поэтому при встрече соответствующих материалов просто пропускал их. А теперь потребовалось и пришлось делать поиск по Интернету. В результате поверхностного поиска нашлось вот что:

Hamming weight из Wikipedia.

Fast Bit Counting (форматирование в примерах кода “поплыло”, но при желании разобраться можно).

Bit Twiddling Hacks (пожалуй, самое внушающее собрание).

PS. Поскольку мне эффективность в данном случае не сильно нужна, то я, пожалуй, обойдусь простым использованием std::bitset::count(), хоть стандарт и не оговаривает требований по эффективности ее реализации.