auto my_vector = std::vector<int, my_allocator>();

auto my_vector = std::vector<int, my_allocator>();auto my_vector2 = std::vector<int, other_allocator>();auto vec = my_vector; // okvec = my_vector2; // error

Основные компоненты std::pmr:

• std::pmr::memory_resource абстрактный класс, реализация которого в конечном счете отвечают за работу с памятью.
• Содержит следующий интерфейс:
  
  • virtual void* do_allocate(std::size_t bytes, std::size_t alignment),
  • virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment)
  • virtual bool do_is_equal(const std::pmr::memory_resource& other) const noexcept.
• std::pmr::polymorphic_allocator имплементация стандартного аллокатора, использует указатель на memory_resource для работы с памятью.
• new_delete_resource() и null_memory_resource() используются для работы с глобальной памятью
• Набор готовых пулов памяти:
  
  • synchronized_pool_resource
  • unsynchronized_pool_resource
  • monotonic_buffer_resource
• Специализации стандартных контейнеров с полиморфным аллокатором, std::pmr::vector, std::pmr::string, std::pmr::map и тд. Каждая специализация определена в том же заголовочном файле, что и соответствующий контейнер.
• Набор готовых memory_resource:
  
  • memory_resource* new_delete_resource() Свободная функция, возвращает указатель на memory_resource, который использует глобальные операторы new и delete выделения памяти.
  • memory_resource* null_memory_resource()
    Свободная функция возвращает указатель на memory_resource, который бросает исключение std::bad_alloc на каждую попытку аллокации.

• class synchronized_pool_resource : public std::pmr::memory_resource
  Потокобезопасная имплементация memory_resource общего назначения состоит из набора пулов с разными размерами блоков памяти.
  Каждый пул представляет из себя набор из кусков памяти одного размера.
• class unsynchronized_pool_resource : public std::pmr::memory_resource
  Однопоточная версия synchronized_pool_resource.
• class monotonic_buffer_resource : public std::pmr::memory_resource
  Однопоточный, быстрый, memory_resource специального назначения берет память из заранее выделенного буфера, но не освобождает его, т.е может только расти.

#include <iostream>#include <memory_resource>   // pmr core types#include <vector>        // pmr::vector#include <string>        // pmr::string int main() {char buffer[64] = {}; // a small buffer on the stackstd::fill_n(std::begin(buffer), std::size(buffer) - 1, '_');std::cout << buffer << '\n'; std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)}; std::pmr::vector<char> vec{ &pool };for (char ch = 'a'; ch <= 'z'; ++ch)    vec.push_back(ch); std::cout << buffer << '\n';}

_______________________________________________________________aababcdabcdefghabcdefghijklmnopabcdefghijklmnopqrstuvwxyz______

Хранение pmr::string

#include <iostream>#include <memory_resource>   // pmr core types#include <vector>        // pmr::vector#include <string>        // pmr::string int main() {std::cout << "sizeof(std::string): " << sizeof(std::string) << '\n';std::cout << "sizeof(std::pmr::string): " << sizeof(std::pmr::string) << '\n'; char buffer[256] = {}; // a small buffer on the stackstd::fill_n(std::begin(buffer), std::size(buffer) - 1, '_'); const auto BufferPrinter = [](std::string_view buf, std::string_view title) {    std::cout << title << ":\n";    for (auto& ch : buf) {        std::cout << (ch >= ' ' ? ch : '#');    }    std::cout << '\n';}; BufferPrinter(buffer, "zeroed buffer"); std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)};std::pmr::vector<std::pmr::string> vec{ &pool };vec.reserve(5); vec.push_back("Hello World");vec.push_back("One Two Three");BufferPrinter(std::string_view(buffer, std::size(buffer)), "after two short strings"); vec.emplace_back("This is a longer string");BufferPrinter(std::string_view(buffer, std::size(buffer)), "after longer string strings"); vec.push_back("Four Five Six");BufferPrinter(std::string_view(buffer, std::size(buffer)), "after the last string");   }

sizeof(std::string): 32sizeof(std::pmr::string): 40zeroed buffer:_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________after two short strings:#m######n#############Hello World######m#####@n#############One Two Three###_______________________________________________________________________________________________________________________________________________________________________________#after longer string strings:#m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________________________________________________________________________________________This is a longer string#_______________________________#after the last string:#m######n#############Hello World######m#####@n#############One Two Three####m######n#####################________#m######n#############Four Five Six###________________________________________This is a longer string#_______________________________#

• Размер pmr::string больше чем std::string. Связано этот с тем, что добавляется указатель на memory_resource;
• Мы резервируем вектор под 5 элементов, поэтому при добавлении 4х реаллокаций не происходит.
• Первые 2 строки достаточно короткие для блока памяти вектора, поэтому дополнительного выделения памяти не происходит.
• Третья строка более длинная и для потребовался отдельный кусок памяти внутри нашего буфера, в векторе при этом сохраняется только указатель на этот блок.
• Как можно видеть из вывода, строка This is a longer string расположена почти в самом конце буфера.
• Когда мы вставляем еще одну короткую строку, она попадает снова в блока памяти вектора

sizeof(std::string): 32sizeof(std::pmr::string): 40zeroed buffer:_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________after two short strings:###w###########Hello World########w###########One Two Three###_______________________________________________________________________________________________________________________________________________________________________________________________#new 24after longer string strings:###w###########Hello World########w###########One Two Three###0#######################_______________________________________________________________________________________________________________________________________________________________________#after the last string:###w###########Hello World########w###########One Two Three###0#######################________@##w###########Four Five Six###_______________________________________________________________________________________________________________________________#

Еще раз про расширение вектора:

void* lastAllocatedPtr = nullptr;size_t lastSize = 0; void* operator new(std::size_t size, std::align_val_t align) {#if defined(_WIN32) || defined(__CYGWIN__)auto ptr = _aligned_malloc(size, static_cast<std::size_t>(align));#elseauto ptr = aligned_alloc(static_cast<std::size_t>(align), size);#endif if (!ptr)    throw std::bad_alloc{}; std::cout << "new: " << size << ", align: "          << static_cast<std::size_t>(align)          << ", ptr: " << ptr << '\n'; lastAllocatedPtr = ptr;lastSize = size; return ptr;}

constexpr auto buf_size = 32;uint16_t buffer[buf_size] = {}; // a small buffer on the stackstd::fill_n(std::begin(buffer), std::size(buffer) - 1, 0); std::pmr::monotonic_buffer_resource pool{std::data(buffer), std::size(buffer)*sizeof(uint16_t)}; std::pmr::vector<uint16_t> vec{ &pool }; for (int i = 1; i <= 20; ++i)vec.push_back(i); for (int i = 0; i < buf_size; ++i)std::cout <<  buffer[i] << " "; std::cout << std::endl; auto* bufTemp = (uint16_t *)lastAllocatedPtr; for (unsigned i = 0; i < lastSize; ++i)std::cout << bufTemp[i] << " ";

new: 128, align: 16, ptr: 0xc73b201 1 2 1 2 3 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 65535 132 0 0 0 0 0 0 0 144 0 0 0 65 0 0 0 16080 199 0 0 16176 199 0 0 16176 199 0 0 15344 199 0 0 15472 199 0 0 15472 199 0 0 0 0 0 0 145 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• унаследоваться от std::pmr::memory_resource
• Реализовать методы:
  
  • do_allocate()
  • do_deallocate()
  • do_is_equal()
• Передать нашу реализацию memory_resource контейнерам.

Читать ещё

• Антипаттерн константа размера массива

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

При написании статьи я использовал стандарт C++17. В качестве реализаций рассматривал GCC 10.1.0 (май 2020) и LLVM/Clang 10.0.0 (март 2020). В каждой и них есть своя реализация STL, а значит и std алгоритмов.

1. Однопоточные реализации

1.1. Готовые сортировки

• std::sort(). Еще в стандарте C++98/C++03 мы видим, что сложность алгоритма примерно n*log(n) сравнений. А также есть примечание, что если важна сложность в худшем случае, то следует использовать std::stable_sort() или std::partial_sort(). Похоже, что в качестве реализации std::sort() подразумевался quicksort (в худшем случае O(n²) сравнений). Однако, начиная с C++11 мы видим, что сложность std::sort() уже O(n*log(n)) сравнений безо всяких оговорок. GCC реализует предложенную в 1997 году introsort (O(n*log(n)) сравнений, как в среднем, так и в худшем случае). Introsort сначала сортирует как quicksort, но вскоре переключается на heapsort и в самом конце сортировки, когда остаются небольшие интервалы (в случае GCC менее 16 элементов), сортирует их при помощи insertion sort. А вот LLVM реализует весьма сложный алгоритм с множеством оптимизаций в зависимости от размеров сортируемых интервалов и того, являются ли сортируемые элементы тривиально копируемыми и тривиально конструируемыми.
• std::partial_sort(). Поиск некоторого числа элементов с минимальным значением из множества элементов и их сортировка. Во всех версиях стандарта сложность примерно n*log(m) сравнений, где n количество элементов в контейнере, а m количество минимальных элементов, которое нужно найти. Задача для heapsort. Сложность в точности совпадает с этим алгоритмом. Так и реализовано в LLVM и GCC.
• std::stable_sort(). Тут немного сложнее. Во-первых, в отличии от предыдущих сортировок в стандарте отмечено, что она стабильная. Т.е. не меняет местами эквивалентные элементы при сортировке. Во-вторых, сложность ее в худшем случае n*(log(n))² сравнений и n*log(n) сравнений, если есть достаточно памяти. Т.е. имеется ввиду 2 разных алгоритма стабильной сортировки. В варианте, когда памяти много подходит стандартный merge sort. Как раз ему требуется дополнительная память для работы. Сделать merge sort без дополнительной памяти за O(n*log(n)) сравнений так же возможно. Но это сложный алгоритм и не смотря на асимптотику n*log(n) сравнений константа у него велика, и в обычных условиях он будет работать не очень быстро. Поэтому обычно используется вариант merge sort без дополнительной памяти, который имеет асимптотику n*(log(n))² сравнений. И в GCC и в LLVM реализации в целом похожи. Реализованы оба алгоритма: один работает при наличии памяти, другой когда памяти не хватает. Обе реализации, когда дело доходит до небольших интервалов, используют insertion sort. Она стабильная и не требует дополнительной памяти. Но ее сложность O (n²) сравнений, что не играет роли на маленьких интервалах.
• std::list::sort(), std::forward_list::sort(). Все перечисленные выше сортировки требуют итераторы произвольного доступа для задания сортируемого интервала. А что если требуется отсортировать контейнер, который не обеспечивает таких итераторов? Например, std::list или std::forward_list. У этих контейнеров есть специальный метод sort(). Согласно стандарту, он должен обеспечить стабильную сортировку за примерно n*log(n) сравнений, где n число элементов контейнера. В целом вполне подходит merge sort. Ее и реализуют GCC и LLVM и для std::list::sort(), и для std::forward_list::sort(). Но зачем вообще потребовались частные реализации сортировки для списков? Почему бы для std::stable_sort() просто не ослабить итераторы до однонаправленных или хотя бы двунаправленных, чтоб этот алгоритм можно было применять и к спискам? Дело в том, что в std::stable_sort() используются оптимизации, которые требуют итераторы произвольного доступа. Например, как я писал выше, когда дело доходит до сортировки не больших интервалов в std::stable_sort() разумно переключиться на insertion sort, а эта сортировка требует итераторы произвольного доступа.
• std::make_heap(), std::sort_heap(). Алгоритмы по работе с кучей (max heap), включая сортировку. std::sort_heap() это единственный способ сортировки, алгоритм для которого указан явно. Сортировка должна быть реализована, как heapsort. Так и реализовано в LLVM и GCC.

Сводная таблица

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

1.2. Составляющие алгоритмов сортировки

• std::merge(). Слияние двух сортированных интервалов. Этот алгоритм не меняет местами эквивалентные элементы, т.е. он стабильный. Количество сравнений не более, чем сумма длин сливаемых интервалов минус 1. На базе данного алгоритма очень просто реализовать merge sort. Однако напрямую этот алгоритм не используется в std::stable_sort() ни LLVM, ни в GCC. Для шага слияния в std::stable_sort() написаны отдельные реализации.
• std::inplace_merge(). Этот алгоритм также реализует слияние двух сортированных интервалов и он также стабильный. У него есть интерфейсные отличия от std::merge(), но кроме них есть еще одно, очень важное. По сути std::inplace_merge() это два алгоритма. Один вызывается при наличии достаточного количества дополнительной памяти. Его сложность, как и в случае std::merge(), не более чем сумма длин объединяемых интервалов минус 1. А другой, если дополнительной памяти нет и нужно сделать слияние "in place". Сложность этого "in place" алгоритма n*log(n) сравнений, где n сумма элементов в сливаемых интервалах. Все это очень напоминает std::stable_sort(), и это не спроста. Как кажется, авторы стандарта предполагали использование std::inplace_merge() или подобных алгоритмов в std::stable_sort(). Эту идею отражают реализации. В LLVM для реализации std::stable_sort() используется std::inplace_merge(), в GCC для реализаций std::stable_sort() и std::inplace_merge() используются некоторые общие методы.
• std::partition()/std::stable_partition(). Данные алгоритмы также можно использовать для написания сортировок. Например, для quicksort или introsort. Но ни GCC ни LLVM не использует их на прямую для реализации сортировок. Используются аналогичные им, но оптимизированные, для случая конкретной сортировки, варианты реализации.

2. Многопоточные реализации

В C++17 для многих алгоритмов появилась возможность задавать политику исполнения (ExecutionPolicy). Она обычно указывается первым параметром алгоритма. Алгоритмы сортировок не стали исключением. Политику исполнения можно задать для большинства алгоритмов рассмотренных выше. В том числе и указать, что алгоритм может выполняться в несколько потоков (std::execution::par, std::execution::par_unseq). Это значит, что именно может, а не обязан. А будет вычисляться в несколько потоков или нет зависит от целевой платформы, реализации и варианта сборки компилятора. Асимптотическая сложность также остается неизменной, однако константа может оказаться меньше за счет использования многих потоков.

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

• LLVM/Clang (Apple clang version 11.0.3 (clang-1103.0.32.62)) и MacOS 10.15.4. В этом случае заголовочный файл execution не нашелся. Т.е. политику многопоточности задать не получится;
• LLVM/Clang 10.0.0 сборка из brew. Тот же результат, что и в случае Apple clang;
• GCC 10.1.0 файл execution есть и политику задать можно. Но какая бы политика ни была задана, использоваться будет однопоточная версия. Для вызова многопоточной версии необходимо, чтобы был подключен файл tbb/tbb.h при компиляции на платформе Intel. А для этого должна быть установлена библиотека Intel Threading Building Blocks (TBB) и пути поиска заголовочных файлов были прописаны. Установлен ли TBB проверяется при помощи специальной команды в gcc: __has_include(<tbb/tbb.h>) в файле c++config.h. И если данный файл виден, то используется многопоточная версия написанная на базе Threading Building Blocks, а если нет, то последовательная. Про TBB немного подробнее ниже.
  Дополнительную информацию о поддержке компиляторам параллельных вычислений, как впрочем и другой функциональности, можно посмотреть здесь: https://en.cppreference.com/w/cpp/compiler_support

3. Intel Threading Building Blocks

Чтоб стало возможным использовать многопоточные версии разных алгоритмов, на сегодня нужно использовать дополнительные библиотеку Threading Building Blocks, разрабатываемую Intel. Это не сложно:

• Клонируем репозиторий Threading Building Blocks с https://github.com/oneapi-src/oneTBB
• Из корня запускаем make и ждем несколько минут пока компилируется TBB или make all и ждем пару часов, чтоб прошли еще и тесты
• Далее при компиляции указываем пути к includes (-I oneTBB/include) и к динамической библиотеке (у меня был такой путь -L tbb/oneTBB/build/macos_intel64_clang_cc11.0.3_os10.15.4_release -ltbb, т.к. я собирал TBB при помощи Apple clang version 11.0.3 на MacOS)

4. Эпилог

Как кажется, когда комитет C++ описывает те или иные особенности языка в стандарте, он предполагает те или иные сценарии использования и те или иные алгоритмы реализации. Часто все развивается, как предполагалось. Иногда идет своим путем. Иногда не используется вовсе. Какие бы ни были реализации тех или иных алгоритмов или структур данных сегодня, завтра это может измениться. Измениться впрочем может и стандарт. Но меняясь, стандарт почти всегда обеспечивает совместимость с ранее написанным кодом. При выпуске новых версий компиляторов, могут меняться и реализации. Но изменяясь они предполагают, что разработчики полагаются на стандарт. На мой взгляд, имеет смысл понимать, как обычно реализуются те или иные части стандартной библиотеки. Но полагаться при разработке нужно именно на ограничения заданные стандартом.

Ссылки на упомянутые алгоритмы и библиотеку:

• Quicksort
• Introsort
• Insertion Sort
• Heapsort
• Merge Sort
• Threading Building Blocks

Благодарности

Большое спасибо Ольге Serine за замечание по статье и картинку.

rotor ненавязчивый С++ акторный микрофремворк, похожий на своих старших братьев caf и sobjectizer. В новом релизе внутреннее ядро полностью было переделано с помощью механизмов плагинов, так что это затронуло жизненный цикл акторов.

Связывание акторов

Всякая система акторов базируется на взаимодействии между ними, т.е. в отправлении сообщений друг другу (а также в возможных побочных эффектах в качестве реакции на эти сообщения или в создании новых сообщений, появляющихся в качестве реакции на события внешнего мира). Однако, чтобы сообщение было доставлено целевому актору, он должен оставаться активным (1); другими словами, если актор A собирается отправить сообщение М актору B, он должен быть уверен, что актор B онлайн и не будет выключен в процессе пересылки сообщения M.

До версии v0.09 подобная гарантия была только для отношений родитель/потомок, между супервайзером и дочерним актором, т. к. для последнего выполняется гарантия того, сообщение будет доставлено до его супервайзера в силу того, что супервайзер владеет дочерним актором, и его время жизни покрывает времена жизни всех своих дочерних акторов. Начиная с версии v0.09 появилась возможность связывания двух произвольных акторов A и B, так что после подтверждения связи (link), можно быть уверенным, что все последующие сообщения будут доставлены.

Для связывания акторов можно использовать такой код:

namespace r = rotor;void some_actor_t::on_start() noexcept override {    request<payload::link_request_t>(b_address).send(timeout);}void some_actor_t::on_link_response(r::message::link_response_t &response) noexcept {    auto& ec = message.payload.ec;    if (!ec) {        // успех связывания    }}

Однако, данный код не рекомендуется использовать напрямую потому что он не очень удобен. Это становится очевидным при попытке связать актор A с двумя и более акторами, т.к. some_actor_t должен будет вести внутренний счётчик успешных связываний. В данном случае помогает система плагинов, и код будет уже выглядеть так:

namespace r = rotor;void some_actor_t::configure(r::plugin::plugin_base_t &plugin) noexcept override {    plugin.with_casted<r::plugin::link_client_plugin_t>(        [&](auto &p) {            p.link(B1_address);            p.link(B2_address);        }    );}

Это более удобно в виду того, что плагин link_client_plugin_t поставляется в базовом классе всех акторов actor_base_t. Тем не менее, это скорей всего не всё, что хотелось бы иметь, т.к. остаются не отвеченными важные вопросы: 1) Когда происходит связывание акторов (и обратный вопрос когда происходит их разъединение)? 2) Что случится, если целевой актор ("сервер") не существует или откажет в связывании? 3) Что случится если целевой актор решит выключиться, в то время как есть связанные с ним акторы-клиенты?

Чтобы ответить на этот вопрос нужно рассмотреть жизненный цикл актора.

Асинхронная инициализация и выключение актора

Упрощённо жизненный цикл актора (состояние, state) выглядит следующим образом: new (ctor) -> initializing -> initialized -> operational -> shutting down -> shut down.

Основная работа осуществляется актором, когда он находится в состоянии operational, и здесь собственно пользователь фреймворка должен решить, чем именно будет заниматься актор.

Во время фазы инициализации (I-фазы, т.е. initializing -> initialized), актор подготавливает себя для будущей работы: находит и связывается с другими акторами, устанавливает соединение с БД, получает необходимые ему ресурсы для полноценной работы. Ключевая особенность rotor'а, что I-фаза асинхронна, т. е. актор сообщает супервайзеру, когда он готов (2).

Фаза выключения (S-фаза, т.е. shutting down -> shut down ) комплиментарна I-фазе, т.е. актора просят выключится, а когда он готов, он сообщает об этом своему супервайзеру.

Несмотря на кажущуюся простоту, основная сложность лежит здесь в масштабируемости (composability) подхода, при котором акторы формируют эрланго-подобные иерархии ответственностей (см. мою статью Trees of Supervisors). Перефразируя, можно сказать, что любой актор может дать сбой во время I- или S-фазы, что может повлечь за собой безопасный и ожидаемый коллапс всей иерархии независимо от местоположения актора в ней. Конечная цель в итоге это либо вся иерархия приходит в рабочее состояние (operational), либо она в конце концов становится выключенной (shut down).

(Пояснение к картинке. Сплошная линия обозначение отношение владения, пунктирная отношения связи).

rotor уникален в этом отношении. Ничего подобного нет в caf. Может создаться ошибочное представление, что в sobjectizer'е присутствует shutdown helper, предназначение которого аналогично S-фазе выше; однако, после публичных дискуссий с автором в англоязчыной версии статьи, выяснилось, что данные вспомогательные классы нужны для "длительного" (гарантированного) выключения акторов, даже если в Environment'е был вызван метод stop. С точки зрения sobjectizer'а отложенная инициализация (и выключение), аналогичные I- и S-фазам rotor'a, могут быть смоделированы с помощью встроенного механизма поддержки состояний и это обязанность пользователя фрейворка, если такова потребность его бизнес-логики. В rotor'е же это встроено в сам фреймворк.

При использовании rotor'а было обнаружено, что во время I-фазы (S-фазы) потенциально множество ресурсов должны быть получены (освобождены) асинхронно, что обозначает, что нет единого компонента, способного решить, что текущая фаза завершена. Вместо этого это решение есть плод совместных усилий, приложенных в определённом порядке. И здесь в игру вступают плагины, представляющие из себя атомарные кусочки, каждый из которых ответственен за собственную работу по инициализации или выключению.

Что же такое плагин в контексте rotor'а? Плагин это некий аспект поведения актора, определяющий реакцию актора на некоторые сообщения или группу сообщений. Лучше пояснить на примерах. Плагин init_shutdown, ответственен за инициализацию (выключение) актора, т. е. после опроса о готовности всех плагины, генерируется ответ на запрос о готовности инициализации (выключения); или, например, плагин child_manager, доступный только для супервайзеров, и ответственный за порождение дочерних акторов и всю машинерию связанную с этим, как то генерация запросов дочерним акторам на инициализацию, выключение и т. п. Несмотря на то, что существует возможность свои плагины, на текущий момент я не вижу необходимости в этом, поэтому она остаётся недокументированной.

Таким образом, обещанные ответы, относящиеся к link_client_plugin_t:

• В: когда происходит связывание (отвязывание) актров? О: когда актор в состоянии initializing (shutting down).

  
  

• В: что случится, если целевой актор не существует или отказывает в связывании? О: т. к. это случается во время инициализации актора, то плагин обнаружит это условие и начнёт выключение актора-клиента; также, возможно, это вызовет каскадный эффект, т.е. его супервайзер тоже выключится и так далее вверх по иерархии владения.

  
  

• В: что случится, если целевой актор решит выключиться, при том, что с ним связаны активные акторы-клиенты? О: актор-сервер попросит клиентов отвязаться, и только когда все связанные клиенты подтвердят это, актор-сервер продолжит процедуру выключения (3).

  
  

Упрощённый пример

Будем предполагать, что имеется драйвер базы данных с асинхронным интерфейсом для одного из движков событий (event loop), доступных для rotor'а, а также что имеются TCP-клиенты, подключающиеся к нашему сервису. За обслуживание базы данных будет отвечать актор db_actor_t, а принимать клиентов будет acceptor_t. Начнём с первого:

namespace r = rotor;struct db_actor_t: r::actor_base_t {    struct resource {        static const constexpr r::plugin::resource_id_t db_connection = 0;    }    void configure(r::plugin::plugin_base_t &plugin) noexcept override {        plugin.with_casted<r::plugin::registry_plugin_t>([this](auto &p) {            p.register_name("service::database", this->get_address())        });        plugin.with_casted<r::plugin::resources_plugin_t>([this](auto &) {            resources->acquire(resource::db_connection);            // инициировать асинхронное соединение с базой данных        });    }    void on_db_connection_success() {        resources->release(resource::db_connection);        ...    }    void on_db_disconnected() {        resources->release(resource::db_connection);    }    void shutdown_start() noexcept override {        r::actor_base_t::shutdown_start();        resources->acquire(resource::db_connection);        // асинхронное закрытие соединения с базой данных и сброс данных    }};

Внутреннее пространство имён resource используется для идентификации соединения с БД как ресурсом. Это общепринятая практика, чтобы не использовать в коде магические цифры вроде 0. Во время конфигурации, которая является частью инициализации, когда плагин registry_plugin_t готов, он асинхронно зарегистрирует адрес актора в регистре (о нём будет рассказано позже). Затем с помощью resources_plugin_t захватывается "ресурс" подключения к БД, чтобы блокировать дальнейшую инициализацию актора и начинается соединение с БД. Когда будет подтверждено соединение с БД, ресурс будет освобождён и актор db_actor_t перейдёт в рабочее состояние. S-фаза аналогична: блокируется выключение до тех пор, пока все данные не будут сброшены в БД и пока соединение не будет закрыто; после этого процедура выключения актора завершается (4).

Код актора, который будет принимать клиентов, выглядит приблизительно так:

namespace r = rotor;struct acceptor_actor_t: r::actor_base_t {    r::address_ptr_t db_addr;    void configure(r::plugin::plugin_base_t &plugin) noexcept override {        plugin.with_casted<r::plugin::registry_plugin_t>([](auto &p) {            p.discover_name("service::database", db_addr, true).link();        });    }    void on_start() noexcept override {        r::actor_base_t::on_start();        // начать приём клиентов, например:        // asio::ip::tcp::acceptor.async_accept(...);    }    void on_new_client(client_t& client) {        // send<message::log_client_t>(db_addr, client)    }};

Основное в данном случае, это метод configure. Когда плагин registry_plugin_t готов, он будет сконфигурирован на обнаружение сервиса service::database, а когда адрес db_actor_t будет найден и сохранён в члене класса db_addr, то тогда с ним будет произведено связывание. Если же адрес актора service::database не будет обнаружен, то актор acceptor_actor_t начнёт выключаться (т. е. on_start не будет вызван). Если всё будет успешно проинициализировано, то актор начнёт принимать новых клиентов.

Собственно, сама операционная часть была опущена ради краткости, т. к. она не изменилась в новой версии rotor'а. Как обычно нужно определить полезную нагрузку (payload), сообщения, методы для работы с этими сообщениями и подписаться на них.

Скомпонуем всё вместе в файле main.cpp; будем считать, что используется boost::asio в качестве цикла событий.

namespace asio = boost::asio;namespace r = rotor;...asio::io_context io_context;auto system_context = rotor::asio::system_context_asio_t(io_context);auto strand = std::make_shared<asio::io_context::strand>(io_context);auto timeout = r::pt::milliseconds(100);auto sup = system_context->create_supervisor<r::asio::supervisor_asio_t>()               .timeout(timeout)               .strand(strand)               .create_registry()               .finish();sup->create_actor<db_actor_t>().timeout(timeout).finish();sup->create_actor<acceptor_actor_t>().timeout(timeout).finish();sup->start();io_context.run();

Как видно, в новом rotor'е активно используется шаблон builder. С помощью него создаётся корневой супервайзер sup, а уже он в свою очередь порождает 3 актора: два пользовательских (db_actor_t и acceptor_actor_t) и неявно созданный актор-регистр. Как обычно для акторных систем, все акторы слабо связаны друг с другом, т.к. они разделяют только общий интерфейс сообщений (опущено в статье).

Акторы "просто создаются" в данном месте, без знания о том, как они связаны между собой. Это следствие слабой связанности между акторами, которые с версии v0.09 стали более автономными.

Конфигурация выполнения могла бы быть полностью другой: акторы могли бы создаваться на разных потоках, на разных супервайзерах, и даже на различных движках, но их реализация оставалась бы по сути одной и той же (5). В этих случаях было бы несколько корневых супервайзеров, однако актор-регистр должен быть создан один, и его адрес разделён между всеми супервайзерами, чтобы акторы смогли найти друг друга. Для этого существует метод get_registry_address() в базовом супервайзере.

Итоги

Наиболее существенным изменением в новой версии rotor'а является разбиение на плагины его ядра. Наиболее важными для пользователя фрейморка являются плагины: link_client_plugin_t, позволяющий установить виртуальное соединение между акторами, плагин registry_plugin_t, дающий возможность регистрации и обнаружения адресов акторов по символическим именам, а также плагин resources_plugin_t, с помощью которого можно приостановить процедуру инициализации (выключения) до появления некоторого асинхронного внешнего события.

Так же присутствуют менее важные изменения в новом релизе, такие как система доступа к непубличным
свойствам и шаблон builder для интанцирования акторов.

Любая обратная связь приветствуется.

P.S. Я хотел бы поблагодарить Crazy Panda за поддержку в моих начинаниях по развитию данного проекта, а также автора sobjectizer'а за высказанные им критические замечания.

Примечания

(1) В настоящее время попытка доставки сообщения актору, супервайзер которого уже отработал и был удалён, ведёт к краху программы (UB).

(2) Если актор не подтвердит успешную инициализацию супервайзеру, сработает таймер инициализации, и супервайзер сделает запрос на выключение актора, т.е. состояние operational будет пропущено.

(3) Может возникнуть вопрос, что произойдёт, если актор не подтвердит отвязывание вовремя? Это нарушение контракта, и будет вызван метод system_context_t::on_error(const std::error_code&), который распечатает ошибку на консоль и вызовет std::terminate(). Для избегания нарушений контрактов, нужно настраивать таймеры, чтобы позволить акторам-клиентам во время отвязаться.

(4) Во время процедуры выключения плагин registry_plugin_t проинструктирует регистр, чтобы все зарегистрированные имена текущего актора были удалены из регистра.

(5) Исключение составляет, когда используются различные циклы событий. Если актор использует API цикла событий, то, очевидно, что смена цикла событий повлечёт переписывание внутренностей актора. Тем не менее, это никак не затронет использование API rotor'а.

Казалось бы, валидация данных это одна из базовых задач в программировании, которая встретится и в начале изучения языка вместе с "Hello world!", и в том или ином виде будет присутствовать в множестве зрелых проектов. Тем не менее, Google до сих пор выдает ноль релевантных результатов при попытке найти универсальную библиотеку валидации данных с открытым исходным кодом на C++.

В лучшем случае, там найдутся или инструменты проверки самого кода C++, или библиотеки валидации определенных форматов, например, таких как JSON или XML. Похоже на то, что либо разработчики для каждого случая реализуют валидацию данных вручную, либо инструменты валидации создаются под конкретный проект и плохо приспособлены для использования в качестве универсальных библиотек.

Если в комментариях кто-то сможет привести примеры открытых библиотек валидации данных на C++ помимо отдельных GUI-форм, то буду очень признателен и добавлю соответствующий список в статью.

Содержание

• Мотивация
• Возможности библиотеки
• Использование
• Текущий статус
• Примеры
  
  • Тривиальная валидация числа
  • Валидация с исключением
  • Явное применение валидатора к переменной
  • Составной валидатор
  • Проверить, что число входит в интервал, и напечатать описание ошибки
  • Составной валидатор для проверки элемента контейнера
  • Проверить элементы вложенных контейнеров
  • Провести валидацию кастомного свойства объекта
  • Пре-валидация данных перед записью
  • Один и тот же валидатор для пост-валидации и пре-валидации
  • Перевод ошибок валидации на русский язык

Мотивация

Стоить отметить, что мотивом к разработке валидатора данных для C++ послужило не столько отсутствие подобной библиотеки, сколько желание получить инструмент, при помощи которого можно было бы единообразно описывать:

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

Т.е., если с прикладной точки зрения во всех трех случаях речь идет о разных представлениях одной и той же сущности, то почему бы не сделать так, чтобы правила проверки характеристик этой сущности описывались бы одинаковым образом? И уже потом эти правила обрабатывать разными способами применительно к каждому конкретному случаю например, транслировать в строку запроса к базе данных или в проверку набора содержимого ранее заполненного объекта или в проверку отдельных переменных перед записью в объект.

В итоге, библиотека валидации разрабатывалась с учетом основного требования, чтобы было четкое разделение между:

• описанием правил валидации;
• реализацией обработчиков правил валидации;
• обработкой конкретных правил валидации конкретным обработчиком.

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

Возможности библиотеки

cpp-validator является header-only библиотекой для современного C++ с поддержкой стандартов C++14/C++17. В коде cpp-validator активно используется метапрограммирование на шаблонах и библиотека Boost.Hana.

Основные возможности библиотеки cpp-validator перечислены ниже.

• Валидация данных для различных конструкций языка:
  
  • простых переменных;
  • свойств объектов, включая:
    
    • переменные классов;
    • методы классов вида getter;
  • содержимого и свойств контейнеров;
  • иерархических типов данных, таких как вложенные объекты и контейнеры.
• Пост-валидация объектов, когда проверяется содержимое уже заполненного объекта на соответствие сразу всем правилам.
• Пре-валидация данных, когда перед записью в объект проверяются только те свойства, которые планируется изменить.
• Комбинация правил с использованием логических связок AND, OR и NOT.
• Массовая проверка элементов контейнеров с условиями ALL или ANY.
• Частично подготовленные правила валидации с отложенной подстановкой аргументов (lazy operands).
• Сравнение друг с другом разных свойств одного и того же объекта.
• Автоматическая генерация описания ошибок валидации:
  
  • широкие возможности по настройке генерации текста ошибок;
  • перевод текста ошибок на различные языки с учетом грамматических атрибутов слов, например, числа, рода и т.д.
• Расширяемость:
  
  • регистрация новых свойств объектов, доступных для валидации;
  • добавление новых операторов правил валидации;
  • добавление новых обработчиков правил валидации (адаптеров).
• Операторы, уже встроенные в библиотеку:
  
  • сравнения;
  • лексикографические, с учетом и без учета регистра;
  • существования элементов;
  • проверки вхождения в интервал или набор;
  • регулярные выражения.
• Широкая поддержка платформ и компиляторов, включая компиляторы Clang, GCC, MSVC и операционные системы Windows, Linux, macOS, iOS, Android.

Использование библиотеки

Базовая валидация данных с использованием cpp-validator выполняется в три шага:

1. сперва создается валидатор, содержащий правила валидации, описанные с использованием почти-декларативного языка;
2. затем валидатор применяется к объекту валидации;
3. в конце проверяется результат валидации, для работы с которым может использоваться либо специальный объект ошибки, либо исключение.

// определение валидатораauto container_validator=validator(   _[size](eq,1), // размер контейнера должен быть равен 1   _["field1"](exists,true), // поле "field1" должно существовать в контейнере   _["field1"](ne,"undefined") // поле "field1" должно быть не равно "undefined");// успешная валидацияstd::map<std::string,std::string> map1={{"field1","value1"}};validate(map1,container_validator);// неуспешная валидация, с объектом ошибкиerror_report err;std::map<std::string,std::string> map2={{"field2","value2"}};validate(map2,container_validator,err);if (err){    std::cerr<<err.message()<<std::endl;    /* напечатает:    field1 must exist    */}// неуспешная валидация, с исключениемtry{    std::map<std::string,std::string> map3={{"field1","undefined"}};    validate(map3,container_validator);}catch(const validation_error& ex){    std::cerr<<ex.what()<<std::endl;    /* напечатает:    field1 must be not equal to undefined    */}

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

Текущий статус библиотеки

Библиотека cpp-validator доступна на GitHub по адресу https://github.com/evgeniums/cpp-validator и готова к использованию на момент написания статьи номер стабильной версии 1.0.2. Библиотека распространяется под лицензией Boost 1.0.

Приветствуются замечания, пожелания и дополнения.

Примеры

Тривиальная валидация числа

// определение валидатораauto v=validator(gt,100); // больше чем 100// объект ошибкиerror err;// условия не выполненыvalidate(90,v,err);if (err){  // валидация неуспешна}// условия выполненыvalidate(200,v,err);if (!err){  // валидация успешна}

Валидация с исключением

// определение валидатораauto v=validator(gt,100); // больше чем 100try{    validate(200,v); // успешно    validate(90,v); // генерирует исключение}catch (const validation_error& err){    std::cerr << err.what() << std::endl;    /* напечатает:    must be greater than 100    */}

Явное применение валидатора к переменной

// определение валидатораauto v=validator(gt,100); // больше чем 100// применить валидатор к переменнымint value1=90;if (!v.apply(value1)){  // валидация неуспешна}int value2=200;if (v.apply(value2)){  // валидация успешна}

Составной валидатор

// валидатор: размер меньше 15 и значение бинарно больше или равно "sample string"auto v=validator(  length(lt,15),  value(gte,"sample string"));// явное применение валидатора к переменнымstd::string str1="sample";if (!v.apply(str1)){  // валидация неупешна потому что sample бинарно меньше, чем sample string}std::string str2="sample string+";if (v.apply(str2)){  // валидация успешна}std::string str3="too long sample string";if (!v.apply(str3)){  // валидация неуспешна, потому что длина строки больше 15 символов}

Проверить, что число входит в интервал, и напечатать описание ошибки

// валидатор: входит в интервал [95,100]auto v=validator(in,interval(95,100));// объект ошибкиerror_report err;// проверить значениеsize_t val=90;validate(val,v,err);if (err){    std::cerr << err.message() << std::endl;     /* напечатает:    must be in interval [95,100]    */}

Составной валидатор для проверки элемента контейнера

// составной валидаторauto v=validator(                _["field1"](gte,"xxxxxx")                 ^OR^                _["field1"](size(gte,100) ^OR^ value(gte,"zzzzzzzzzzzz"))            );// валидация контейнера и печать ошибкиerror_report err;std::map<std::string,std::string> test_map={{"field1","value1"}};validate(test_map,v,err);if (err){    std::cerr << err.message() << std::endl;    /* напечатает:    field1 must be greater than or equal to xxxxxx OR size of field1 must be greater than or equal to 100 OR field1 must be greater than or equal to zzzzzzzzzzzz    */}

Проверить элементы вложенных контейнеров

// составной валидатор элементов вложенных контейнеровauto v=validator(                _["field1"][1](in,range({10,20,30,40,50})),                _["field1"][2](lt,100),                _["field2"](exists,false),                _["field3"](empty(flag,true))            );// валидация вложенного контейнера и печать ошибкиerror_report err;std::map<std::string,std::map<size_t,size_t>> nested_map={            {"field1",{{1,5},{2,50}}},            {"field3",{}}        };validate(nested_map,v,err);if (err){    std::cerr << err.message() << std::endl;    /* напечатает:    element #1 of field1 must be in range [10, 20, 30, 40, 50]    */}

Провести валидацию кастомного свойства объекта

// структура с getter методомstruct Foo{    bool red_color() const    {        return true;    }};// зарегистрировать новое свойство red_colorDRACOSHA_VALIDATOR_PROPERTY_FLAG(red_color,"Must be red","Must be not red");// валидатор зарегистрированного свойства red_colorauto v=validator(    _[red_color](flag,false));// провести валидацию кастомного свойства и напечатать ошибкуerror_report err;Foo foo_instance;validate(foo_instance,v,err);if (err){    std::cerr << err.message() << std::endl;    /* напечатает:    "Must be not red"    */}

Пре-валидация данных перед записью

// структура с переменными и методом вида setterstruct Foo{    std::string bar_value;    uint32_t other_value;    size_t some_size;    void set_bar_value(std::string val)    {        bar_value=std::move(val);    }};using namespace DRACOSHA_VALIDATOR_NAMESPACE;// зарегистрировать кастомные свойстваDRACOSHA_VALIDATOR_PROPERTY(bar_value);DRACOSHA_VALIDATOR_PROPERTY(other_value);// специализация шаблона класса set_member_t для записи свойства bar_value структуры FooDRACOSHA_VALIDATOR_NAMESPACE_BEGINtemplate <>struct set_member_t<Foo,DRACOSHA_VALIDATOR_PROPERTY_TYPE(bar_value)>{    template <typename ObjectT, typename MemberT, typename ValueT>    void operator() (            ObjectT& obj,            MemberT&&,            ValueT&& val        ) const    {        obj.set_bar_value(std::forward<ValueT>(val));    }};DRACOSHA_VALIDATOR_NAMESPACE_END// валидатор с кастомными свойствамиauto v=validator(    _[bar_value](ilex_ne,"UNKNOWN"), // лексикографическое "не равно" без учета регистра    _[other_value](gte,1000) // больше или равно 1000);Foo foo_instance;error_report err;// запись валидного значение в свойство bar_value объекта foo_instanceset_validated(foo_instance,bar_value,"Hello world",v,err);if (!err){    // свойство bar_value объекта foo_instance успешно записано}// попытка записи невалидного значение в свойство bar_value объекта foo_instanceset_validated(foo_instance,bar_value,"unknown",v,err);if (err){    // запись не удалась    std::cerr << err.message() << std::endl;    /* напечатает:     bar_value must be not equal to UNKNOWN     */}

Один и тот же валидатор для пост-валидации и пре-валидации

#include <iostream>#include <dracosha/validator/validator.hpp>#include <dracosha/validator/validate.hpp>using namespace DRACOSHA_VALIDATOR_NAMESPACE;namespace validator_ns {// зарегистрировать getter свойства "x"DRACOSHA_VALIDATOR_PROPERTY(GetX);// валидатор GetXauto MyClassValidator=validator(   /*    "x" в кавычках - это имя поля, которое писать в отчете вместо GetX;   interval.open() - модификатор открытого интервала без учета граничных точек   */   _[GetX]("x")(in,interval(0,500,interval.open())) );}using namespace validator_ns;// определение тестового класса  class MyClass {  double x;public:  // Конструктор с пост-валидацией  MyClass(double _x) : x(_x) {      validate(*this,MyClassValidator);  }  // Getter  double GetX() const noexcept  {     return _x;  }  // Setter с пре-валидацией  void SetX(double _x) {    validate(_[validator_ns::GetX],_x,MyClassValidator);    x = _x;  }};int main(){// конструктор с валидным аргументомtry {    MyClass obj1{100.0}; // ok}catch (const validation_error& err){}// конструктор с невалидным аргументомtry {    MyClass obj2{1000.0}; // значение вне интервала}catch (const validation_error& err){    std::cerr << err.what() << std::endl;    /*     напечатает:     x must be in interval(0,500)    */}MyClass obj3{100.0};// запись с валидным аргументомtry {    obj3.SetX(200.0); // ok}catch (const validation_error& err){}// попытка записи с невалидным аргументомtry {    obj3.SetX(1000.0); // значение вне интервала}catch (const validation_error& err){    std::cerr << err.what() << std::endl;    /*     напечатает:     x must be in interval (0,500)    */}return 0;}

Перевод ошибок валидации на русский язык

// переводчик ключей контейнера на русский язык с учетом рода, падежа и числаphrase_translator tr;tr["password"]={                    {"пароль"},                    {"пароля",grammar_ru::roditelny_padezh}               };tr["hyperlink"]={                    {{"гиперссылка",grammar_ru::zhensky_rod}},                    {{"гиперссылки",grammar_ru::zhensky_rod},grammar_ru::roditelny_padezh}                };tr["words"]={                {{"слова",grammar_ru::mn_chislo}}            };/* финальный переводчик включает в себя встроенный переводчик на русскийvalidator_translator_ru() и переводчик tr для имен элементов*/auto tr1=extend_translator(validator_translator_ru(),tr);// контейнер для валидацииstd::map<std::string,std::string> m1={    {"password","123456"},    {"hyperlink","zzzzzzzzz"}};// адаптер с генерацией отчета об ошибке на русском языкеstd::string rep;auto ra1=make_reporting_adapter(m1,make_reporter(rep,make_formatter(tr1)));// различные валидаторы и печать ошибок на русском языкеauto v1=validator(    _["words"](exists,true) );if (!v1.apply(ra1)){    std::cerr<<rep<<std::endl;    /*    напечатает:    слова должны существовать    */}rep.clear();auto v2=validator(    _["hyperlink"](eq,"https://www.boost.org") );if (!v2.apply(ra1)){    std::cerr<<rep<<std::endl;    /*    напечатает:    гиперссылка должна быть равна https://www.boost.org    */}rep.clear();auto v3=validator(    _["password"](length(gt,7)) );if (!v3.apply(ra1)){    std::cerr<<rep<<std::endl;    /*    напечатает:    длина пароля должна быть больше 7    */}rep.clear();auto v4=validator(    _["hyperlink"](length(lte,7)) );if (!v4.apply(ra1)){    std::cerr<<rep<<std::endl;    /*    напечатает:    длина гиперссылки должна быть меньше или равна 7    */}rep.clear();

SObjectizer это небольшой фреймворк для C++, который дает возможность разработчику использовать такие подходы, как Actor Model, Communicating Sequential Processes и Publish/Subscribe.

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

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

Сегодня мы еще раз поговорим об этом. На примере уже другой задачи. Да и реализация будет отличаться, поскольку за прошедшее время SObjectizer успел обновиться сперва до версии 5.6, а затем и 5.7. И в этих версиях много отличий от версии 5.5, про которую в основном и рассказывалось в прошлом. В том числе и в механизме диспетчеров.

О решаемой задаче в двух словах

Предположим, что у нас есть агент, который ожидает два сообщения: msg_result с финальным результатом ранее начатой агентом операции и msg_status с промежуточной информацией о том, как протекает начатая операция.

Сообщения msg_status могут идти большим потоком. Например, на одно msg_result может приходиться до 1000 msg_status. И нам бы хотелось, чтобы когда в очереди уже стоит 900 сообщений msg_status новое сообщение msg_result вставало не в конец очереди, а в самое ее начало. Чтобы msg_result не ждало пока разгребутся 900 старых msg_status.

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

Как диспетчеры связаны с политикой доставки сообщений до агентов?

Диспетчер в SObjectizer-е это сущность, которая определяет где и когда агенты будут обрабатывать свои сообщения.

Допустим, у нас есть агент Bob, который подписывается на сообщение msg_result из почтового ящика mbox. Когда в mbox отсылается msg_result, то это сообщение должно встать в очередь Bob-а, откуда оно будет рано или поздно извлечено и обработано. И вот здесь уже в полный рост встают диспетчеры, поскольку у агентов нет никаких очередей, тогда как у диспетчеров есть.

Когда агент регистрируется в SObjectizer-е, то агент привязывается к какому-то диспетчеру. И в момент привязки агенту дается указатель на сущность event_queue. Это интерфейс, за которым скрыта некая машинерия по передаче сообщения, адресованного агенту, именно тому диспетчеру, к которому агент привязан.

Когда сообщение передается диспетчеру, тот формирует заявку (demand) на обработку сообщения агентом и сохраняет заявку где-то у себя (очередь заявок диспетчера называется demand_queue).

Процесс доставки сообщения до агента в SObjectizer выглядит следующим образом:

Когда сообщение отсылается в mbox, то mbox видит Bob-а в подписчиках и говорит Bob-у: вот тебе новое сообщение. Bob берет это сообщение и передает его в свой event_queue. И уже этот event_queue формирует для диспетчера заявку (demand) на обработку сообщения для агента Bob. Заявка сохраняется в demand_queue диспетчера.

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

В общем, получается, что диспетчеры и предоставляют рабочий контекст для агентов, и хранят в своих demand_queue адресованные агентам сообщения.

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

А приоритетов для сообщений в SObjectizer-5 и нет :(

Совсем.

Вот так вот.

Приоритеты для сообщений были в SObjectizer-4. Но они на практике использовались всего раз или два. Зато хлопот с их существованием и поддержкой было много.

Поэтому при разработке SObjectizer-5 от приоритетов для сообщений агента было решено отказаться. И за 10 лет развития и использования SObjectizer-5 пожалеть об этом пока что не пришлось.

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

Так как можно решить задачу с msg_result и msg_status?

Использование двух агентов с разными приоритетами и диспетчера one_thread::strictly_ordered

Самое "простое" и "искаробочное" решение.

Логика агента A размазывается на двух агентов A_result и A_status. Агенты A_result и A_status получают разные приоритеты и привязываются к одному и тому же диспетчеру типа one_thread::strictly_ordered. Агент A_result подписывается на msg_result, тогда как агент A_status подписывается на msg_status.

Общие для агентов данные выносятся в какой-то общий объект, которыми они совместно владеют. Через shared_ptr, например. Получится что-то вроде:

struct A_data { ... };class A_result final : public so_5::agent_t {   std::shared_ptr<A_data> m_data;public:   A_result(context_t ctx, std::shared_ptr<A_data> data) {...}   void so_define_agent() override {      so_subscribe(m_data->m_mbox, &A_result::on_result);   }private:   void on_result(const msg_result & msg) {...}};class A_status final : public so_5::agent_t {   std::shared_ptr<A_data> m_data;public:   A_status(context_t ctx, std::shared_ptr<A_data> data) {...}   void so_define_agent() override {      so_subscribe(m_data->m_mbox, &A_status::on_status);   }private:   void on_status(const msg_status & msg) {...}};

Разделять общие данные между агентами A_result и A_status безопасно до тех пор, пока они работают на one_thread::strictly_ordered диспетчере.

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

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

Собственный диспетчер с приоритетами для сообщений

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

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

Именно по этому пути мы и пойдем в данной статье.

Что именно мы попытаемся сделать?

Мы попытаемся посмотреть на проблему немного шире (как это и положено русским программистам, которые ищут универсальные решения там, где можно обойтись методом грубой силы).

Начнем с того, что нам нужно собственный диспетчер. Который сможет упорядочивать сообщения в своей очереди согласно их приоритетов.

И тут возникает вопрос, а как должны определяться эти приоритеты?

А это зависит от задачи.

Где-то приоритеты будут определяться типом сообщения и эти приоритеты можно зафиксировать прямо в compile-time. Скажем, приоритет у msg_result единичка, а у msg_status нолик.

Где-то приоритеты могут зависеть от типа сообщения и агента-получателя. Скажем, для агента A сообщение msg_result будет иметь приоритет 1, а сообщение msg_status 0. Тогда как для агента L оба эти сообщения будут иметь приоритет 0.

Где-то приоритеты могут зависеть только от почтового ящика, из которого они были получены. Скажем все сообщения из mbox_A должны быть приоритетнее, чем сообщения из mbox_B.

А где-то приоритеты почтовых ящиков должны быть дополнены еще и приоритетами сообщений. Т.к. msg_result из mbox_A имеет приоритет 2, msg_status из mbox_A 1, msg_result из mbox_B 1, msg_status из mbox_B 0.

Ну и другие сочетания параметров так же возможны.

Значит ли это, что под каждое такое сочетание нужно делать свой диспетчер?

Скорее всего нет.

Возможно, диспетчер должен быть один, просто он должен уметь настраиваться на любой способ вычисления приоритета сообщений. Например, пользователь параметризует диспетчер объектом priority_detector который и определяет приоритет очередного сообщения: при получении очередной заявки диспетчер дергает priority_detector и располагает заявку в очереди согласно вычисленного priority_detector-ом приоритета.

Уже хорошо.

Но можно попробовать пойти еще дальше.

Диспетчеры были придуманы для того, чтобы дать возможность разработчику распределять своих агентов по тем рабочим контекстам, которые нужны разработчику. Скажем, захотел программист, чтобы агенты Alice и Bob работали на одной общей рабочей нити, значит зачем-то ему это нужно. Не суть важно зачем: для экономии ресурсов или для того, чтобы облегчить Alice и Bob совместную работу над общими разделяемыми данным. Разработчик хочет привязать Alice и Bob к общему контексту, значит он должен суметь это сделать.

А теперь представим себе, что Alice и Bob должны работать на общем рабочем контексте, но приоритеты доставки сообщений до Alice и Bob должны вычисляться по-разному. Скажем, приоритет сообщений для Alice зависит только от их типа. Тогда как приоритет для Bob-а зависит и от типа, и от почтового ящика.

Тут можно пойти, как минимум, двумя путями.

Первый путь. Диспетчер владеет одной приоритетной очередью. А мы пишем сложный priority_detector-а, который разбирается кто получатель сообщения, Alice или Bob, затем для каждого получателя определяет приоритет по тем или иным критериям.

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

Второй путь. А что, если у каждого из агентов будет своя собственная приоритетная очередь? И в каждой очереди будет собственный priority_detector со своими правилами? Тогда мы сможем привязывать к одном диспетчеру агентов с разными политиками доставки сообщений. И в этом случае нам нужно научить диспетчера работать не с одной единственной очередью, в которую сваливается вообще все, а с набором отдельных очередей.

Мы пойдем вторым путем. Поскольку он открывает интересные возможности. Ведь если мы можем научить диспетчер обслуживать агентов с собственными очередями, то не обязательно это будут очереди с приоритетом. Например, это могут быть очереди фиксированного размера с автоматическим выбрасыванием самых старых (или самых новых) элементов при попытке добавления заявки в уже полную очередь. Или же очереди с контролем времени пребывания: скажем, если заявка простояла в очереди дольше 250ms, то она уже не актуальна и должна быть проигнорирована.

Демо проект so5_custom_queue_disps

Для иллюстрации предлагаемого решения на GitHub-е создан демо-проект so5_custom_queue_disps, который содержит исходные тексты обсуждаемого ниже диспетчера.

На данный момент в нем есть реализация только одного типа диспетчера one_thread, который привязывает всех агентов к одной единственной рабочей нити. Если данная тема кого-нибудь заинтересует, то туда же можно будет добавить и реализации thread_pool и/или adv_thread_pool диспетчеров. Для иллюстрации. Ну или для того, чтобы их можно было скопипастить, если вдруг кому-нибудь понадобятся.

Общая идея: список из непустых очередей

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

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

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

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

После чего диспетчер запускает обработку извлеченной заявки. А после завершения обработки проверяет свой список: если список не пуст, то обрабатывается следующий его элемент. Если пуст, то диспетчер засыпает.

Несколько агентов с одной очередью заявок и FIFO для агентов

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

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

И тут возможны сюрпризы с обеспечением FIFO для агентов.

Предположим, что мы используем простые очереди заявок. Без приоритетов, без ограничения на размер, без выбрасывания чего-либо. Просто очереди.

Предположим, что агенты Alice и Bob разделяют одну общую очередь. И мы отсылаем сообщение M1 агенту Alice, а затем отсылаем сообщение M2 агенту Bob. Доставка сообщений до агентов произойдет в таком же порядке: сперва M1, затем M2.

Но вот если агенты Alice и Bob имеют независимые очереди заявок, то при отсылке вначале M1 агенту Alice, а затем M2 агенту Bob, порядок доставки может быть любым. Это зависит и от наполнения очередей заявок самих агентов, и от того, где эти очереди находились в списке непустых очередей диспетчера. Так что может случится и так, что M2 будет обработано агентом Bob еще до того, как M1 дойдет до Alice.

Эту особенность нужно иметь в виду при работе с таким диспетчером.

Как описанный выше подход выглядит для пользователя на практике?

Прежде чем перейти к рассмотрению деталей реализации custom_queue_disps::one_thread-диспетчера посмотрим на то, как выглядит использование этого диспетчера в коде:

so_5::launch( [](so_5::environment_t & env) {   env.introduce_coop( [](so_5::coop_t & coop) {      // (1)      auto queue = std::make_shared<dynamic_per_agent_priorities_t>();      // (2)      auto binder = custom_queue_disps::one_thread::make_dispatcher(            coop.environment() ).binder( queue );      // (3)      auto * alice = coop.make_agent_with_binder<demo_agent_t>(            binder, "Alice" );      auto * bob = coop.make_agent_with_binder<demo_agent_t>(            binder, "Bob" );      // (4)      queue->define_priority( alice,            typeid(demo_agent_t::hello),            dynamic_per_agent_priorities_t::low );      queue->define_priority( alice,            typeid(demo_agent_t::bye),            dynamic_per_agent_priorities_t::high );      queue->define_priority( bob,            typeid(demo_agent_t::hello),            dynamic_per_agent_priorities_t::high );      queue->define_priority( bob,            typeid(demo_agent_t::bye),            dynamic_per_agent_priorities_t::low );   } );} );

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

В точке (2) мы делаем сразу два действия:

• во-первых, создаем новый экземпляр диспетчера;
• во-вторых, получаем от этого диспетчера объект disp_binder, который нам нужен чтобы привязать агентов к этому диспетчеру. Этот disp_binder знает, что агенты, которых он привязывает к диспетчеру, будут совместно использовать очередь заявок, созданную в точке (1).

В точке (3) мы создаем двух агентов, каждый из которых будет привязан к one_thread-диспетчеру, созданному в точке (2).

В точке (4) определяются приоритеты для сообщений, которые обрабатываются агентами Alice и Bob. Можно увидеть, что одним и тем же сообщениям назначаются разные приоритеты. Соответственно, даже если сообщения отсылаются агентам единовременно, обрабатываться сообщения будут в разном порядке. В соответствии со своими приоритетами. А это как раз то, что нам и нужно.

Некоторые пояснения касательно деталей реализации so5_custom_queue_disps

Базовый класс demand_queue_t и его наследники

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

Для этого предназначен интерфейс demand_queue_t.

Публичная часть demand_queue_t

Публичная часть demand_queue_t выглядит так:

      [[nodiscard]]      virtual bool      empty() const noexcept = 0;      [[nodiscard]]      virtual std::optional<so_5::execution_demand_t>      try_extract() noexcept = 0;      virtual void      push( so_5::execution_demand_t demand ) = 0;

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

Надеюсь, что смысл методов empty() и push() очевиден, поэтому на них останавливаться не буду (если что, то отвечу на вопросы в комментариях). А вот по поводу возврата std::optional из try_extract() можно сказать пару слов.

Может показаться, что если диспетчер обращается к очереди заявок только когда очередь не пуста, то достаточно иметь только один метод extract(), который возвращает первую заявку из очереди (конструктуры/операторы копирования/перемещения для execution_demand_t не бросают исключений, поэтому можно обойтись одним extract() вместо пары front()+pop()).

Но в таком случае мы теряем некоторую долю гибкости. Скажем, возможность игнорировать заявки, которые ждали в очереди слишком долго. Тогда как возврат std::optional дает нам такую возможность. Поэтому диспетчер ожидает следующего поведения от очереди заявок:

• если empty() возвращает false, то диспетчер может безопасно вызывать try_extract();
• try_extract() может вернуть пустой std::optional даже если очередь была непустой. Это всего лишь означает, что актуальной заявки для обработки на самом деле не оказалось. Поэтому диспетчер просто идет дальше.

thread-safety для demand_queue_t

Диспетчер вызывает методы empty/try_extract/push только под своим собственным mutex-ом. Поэтому, если очередь заявок модифицирует свое состояние только в этих методах, то об обеспечении thread-safety можно не беспокоится, она обеспечивается диспетчером автоматически.

Однако, если внутри empty/try_extract/push требуется доступ к информации, которая каким-то образом может модифицироваться еще какими-то методами, то тогда ответственность за обеспечение thread-safety для этой дополнительной информации ложится на разработчика очереди заявок. Пример этого мы увидим ниже, когда будем говорить о классе dynamic_per_agent_priorities_t.

Специальные приоритеты для заявок evt_start и evt_finish

Если реализация очереди заявок выполняет переупорядочивание заявок согласно приоритетам или если реализация очереди заявок выбрасывает какие-то заявки из очереди, то следует учесть факт существования двух типов заявок: evt_start и evt_finish.

Заявка evt_start ставится в очередь заявок самой первой, прямо во время привязки агента к диспетчеру. Именно благодаря этой заявке у агента вызывается виртуальный метод so_evt_start.

Заявка evt_finish является самой последней заявкой для агента. Происходит это в процессе дерегистрации агента. И evt_finish должна быть самой последней заявкой, которая для агента будет выполнена. Никакие другие заявки после обработки evt_finish для агента обрабатываться не должны.

Так вот, поскольку это архиважные заявки для жизненного цикла агента, то выбрасывать их категорически нельзя. Это должно быть учтено при реализации очереди заявок.

Если заявки упорядочиваются в очереди согласно приоритетам, то у заявки evt_start должен быть наивысший приоритет. А у заявки evt_finish самый низкий.

В SObjectizer 5.5, 5.6 и 5.7 заявки evt_start и evt_finish можно различить не по execution_demand_t::m_msg_type, как для обычных заявок. А по execution_demand_t::m_demand_handler. Ниже будет показано, как именно это происходит. Возможно, в SObjectizer-5.8 будет применен единообразный подход и все будет идентифицироваться посредством execution_demand_t::m_msg_type. Но в ближайших планах ветки 5.8 нет от слова совсем :)

Написание собственного demand_queue_t

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

Простейший случай: simple_fifo_t

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

class simple_fifo_t final : public custom_queue_disps::demand_queue_t   {      std::queue< so_5::execution_demand_t > m_queue;   public:      simple_fifo_t() = default;      [[nodiscard]]      bool      empty() const noexcept override { return m_queue.empty(); }      [[nodiscard]]      std::optional<so_5::execution_demand_t>      try_extract() noexcept override         {            std::optional<so_5::execution_demand_t> result{               std::move(m_queue.front())            };            m_queue.pop();            return result;         }      void      push( so_5::execution_demand_t demand ) override         {            m_queue.push( std::move(demand) );         }   };

Поскольку мы обеспечиваем строгий FIFO и ничего не выбрасываем, то нам здесь даже не нужно задумываться о существовании заявок evt_start/evt_finish.

Наиболее сложный случай: dynamic_per_agent_priorities_t

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

Для того, чтобы хранить описания заданных пользователем приоритетов потребуются следующие типы данных и члены класса dynamic_per_agent_priorities_t:

using type_to_prio_map_t = std::map< std::type_index, priority_t >;using agent_to_prio_map_t =            std::map< so_5::agent_t *, type_to_prio_map_t >;std::mutex m_prio_map_lock;agent_to_prio_map_t m_agent_prios;

Можно увидеть std::mutex который и будет задействован для обеспечения thread-safety при работе с m_agent_prios.

Здесь нам нужно использовать очередь с приоритетами. И, дабы воспользоваться std::priority_queue из стандартной библиотеки, мы будем хранить в очереди не so_5::execution_demand_t, а собственный класс:

struct actual_demand_t   {      so_5::execution_demand_t m_demand;      priority_t m_priority;      actual_demand_t(         so_5::execution_demand_t demand,         priority_t priority )         :  m_demand{ std::move(demand) }         ,  m_priority{ priority }         {}      [[nodiscard]]      bool      operator<( const actual_demand_t & o ) const noexcept         {            return m_priority < o.m_priority;         }   };

Далее, для реализации метода push(), в котором новая заявка должна встать в очередь согласно своему приоритету, нам потребуется определить тип заявки, кому она адресуется и какой из всего этого получается приоритет:

[[nodiscard]]priority_thandle_new_demand_priority( const so_5::execution_demand_t & d ) noexcept   {      if( so_5::agent_t::get_demand_handler_on_start_ptr()            == d.m_demand_handler )         return highest;      if( so_5::agent_t::get_demand_handler_on_finish_ptr()            == d.m_demand_handler )         {            std::lock_guard< std::mutex > lock{ m_prio_map_lock };            m_agent_prios.erase( d.m_receiver );            return lowest;         }      {         std::lock_guard< std::mutex > lock{ m_prio_map_lock };         auto it_agent = m_agent_prios.find( d.m_receiver );         if( it_agent != m_agent_prios.end() )            {               auto it_msg = it_agent->second.find( d.m_msg_type );               if( it_msg != it_agent->second.end() )                  return it_msg->second;            }      }      return normal;   }

Сперва мы проверяем, является ли заявка заявкой типа evt_start. Если да, то ей присваивается наивысший приоритет.

Далее такая же проверка делается для заявки типа evt_finish. Но если пришла заявка evt_finish, то кроме назначения ей наименьшего приоритета мы делаем дополнительное действие: удаляем информацию о приоритетах для этого агента. Т.к. эта информация больше не потребуется, других заявок уже не будет.

Также в коде метода handle_new_demand_priority() можно обратить внимание на захват mutex-а в тех местах, где нам требуется модифицировать информацию о приоритетах. Это необходимо делать, т.к. эта информация модифицируется/используется не только при работе push(), но и при работе метода define_priority() о котором диспетчер не знает.

Вот, собственно, и все особенности. Остальная часть тривиальна:

voiddefine_priority(   so_5::agent_t * receiver,   std::type_index msg_type,   priority_t priority )   {      std::lock_guard< std::mutex > lock{ m_prio_map_lock };      m_agent_prios[ receiver ][ msg_type ] = priority;   }[[nodiscard]]boolempty() const noexcept override { return m_queue.empty(); }[[nodiscard]]std::optional<so_5::execution_demand_t>try_extract() noexcept override   {      std::optional<so_5::execution_demand_t> result{         m_queue.top().m_demand      };      m_queue.pop();      return result;   }voidpush( so_5::execution_demand_t demand ) override   {      const auto prio = handle_new_demand_priority( demand );      m_queue.emplace( std::move(demand), prio );   }

Приватная часть demand_queue_t

Кроме описанной выше публичной части demand_queue_t есть еще и "приватная" часть, которая предназначена для использования только со стороны диспетчера:

class demand_queue_t   {      demand_queue_t * m_next{ nullptr };   public:      [[nodiscard]]      demand_queue_t *      next() const noexcept { return m_next; }      void      set_next( demand_queue_t * q ) noexcept { m_next = q; }      void      drop_next() noexcept { set_next( nullptr ); }

Эта часть нужна для того, чтобы диспетчер мог провязывать непустые очереди заявок в интрузивный односвязный список.

dispatcher_handle. Что это и зачем?

После того, как с очередями разобрались, можно перейти к самому диспетчеру. И первое, с чем мы сталкиваемся, так это с тем, что в SObjectizer 5.6 и 5.7 нет никакого явного интерфейса для диспетчера, как это было в SObjectizer 5.5 и более ранних версиях. Т.е. реализовать диспетчер можно как угодно и в виде чего угодно (в SO-5.5 же диспетчер должен был наследоваться от специального класса dispatcher_t).

В SO-5.6/5.7 пользователь взаимодействует с диспетчерами посредством двух сущностей: dispatcher_handle и disp_binder. При disp_binder мы поговорим ниже, а пока рассмотрим dispatcher_handle.

За создание экземпляра диспетчера в SO-5.6/5.7 обычно отвечает функция-фабрика make_dispatcher(). Эта функция должна что-то возвратить, но что, если для диспетчера в современном SObjectizer-е нет никакого C++ного интерфейса?

А вот некий дескриптор/хэндл и возвращается. Именно это и называется dispatcher_handle.

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

Обычно у dispacher_handle есть публичный метод binder() который создает экземпляр disp_binder-а для этого диспетчера. Возможно, у dispatcher_handle есть и другие методы, специфические для конкретного типа диспетчера. Но обычно это binder() и несколько методов, делающих dispatcher_handle похожим на shared_ptr.

В рассматриваемой реализации у dispatcher_handler минималистичный интерфейс:

namespace impl{class dispatcher_t;using dispatcher_shptr_t = std::shared_ptr< dispatcher_t >;class dispatcher_handle_maker_t;} /* namespace impl */class [[nodiscard]] dispatcher_handle_t   {      friend class impl::dispatcher_handle_maker_t;      impl::dispatcher_shptr_t m_disp;      dispatcher_handle_t( impl::dispatcher_shptr_t disp );      [[nodiscard]]      bool      empty() const noexcept;   public :      dispatcher_handle_t() noexcept = default;      [[nodiscard]]      so_5::disp_binder_shptr_t      binder( demand_queue_shptr_t demand_queue ) const;      [[nodiscard]]      operator bool() const noexcept { return !empty(); }      [[nodiscard]]      bool      operator!() const noexcept { return empty(); }      void      reset() noexcept;   };

Функция-фабрика make_dispatcher() для нашего one_thread-диспетчера будет возвращать экземпляр dispatcher_handler именно этого типа.

disp_binder. Что это и что нам нужно от disp_binder для one_thread-диспетчера?

Выше мы уже несколько раз упоминали привязку агентов к диспетчерам. Теперь же настало время поговорить об это в подробностях.

И вот тут в дело вступают специальные объекты под названием disp_binder-ы. Они служат как раз для того, чтобы привязать агента к диспетчеру при регистрации кооперации с агентом. А также для того, чтобы отвязать агента от диспетчера при дерегистрации кооперации.

В SObjectizer определен интерфейс, который должны поддерживать все disp_binder-ы. Конкретные же реализации disp_binder-ов зависят от конкретного типа диспетчера. И каждый диспетчер реализует свои собственные disp_binder-ы.

Начиная с версии 5.6 интерфейс этот выглядит следующим образом:

class disp_binder_t   : private std::enable_shared_from_this< disp_binder_t >{   public:      disp_binder_t() = default;      virtual ~disp_binder_t() noexcept = default;      virtual void      preallocate_resources( agent_t & agent ) = 0;      virtual void      undo_preallocation( agent_t & agent ) noexcept = 0;      virtual void      bind( agent_t & agent ) noexcept = 0;      virtual void      unbind( agent_t & agent ) noexcept = 0;};

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

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

На первой стадии SObjectizer пытается выделить все ресурсы, необходимые для агентов из новой кооперации. Например, какие-то диспетчеры должны создать для новых агентов новые рабочие нити. Как раз на этой стадии у disp_binder-а вызывается preallocate_resources(). В этом методе disp_binder должен создать все, что агенту потребуется для работы внутри SObjectizer (например, новая рабочая нить, очередь заявок и т.д.). Если все это создалось нормально, то disp_binder должен сохранить это у себя до тех пор, пока у него не вызовут метод bind() для этого же агента.

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

При возникновении подобных проблем все, что было сделано до этого момента, нужно откатить. Для чего и предназначен метод undo_preallocation(). Если у disp_binder-а вызывается метод undo_preallocation(), то disp_binder должен освободить все ресурсы для агента, которые ранее были зарезервированы в preallocate_resources().

Если же стадия резервирования ресурсов завершилась успешно, то выполняется стадия собственно привязки агентов к диспетчерам. И вот здесь уже у disp_binder-а вызывается метод bind(). В этом методе disp_binder обязательно должен вызывать у привязываемого агента метод so_bind_to_dispatcher().

Метод bind() не случайно помечен как noexcept, т.к. на этой стадии исключений SObjectizer не ожидает (а если таковое возникнет, то восстановиться уже не получится).

Метод unbind(), очевидно, используется уже когда кооперация дерегистрируется и агент завершил все свои активности на рабочем контексте (включая и обработку evt_finish). Так что в unbind() disp_binder должен освободить все ресурсы, которые были выделены для агента в preallocate_resources().

Возможно звучит все это сложновато. Но в данном случае реализация disp_binder-а оказывается очень простой:

class actual_disp_binder_t final : public so_5::disp_binder_t   {      actual_event_queue_t m_event_queue;   public:      actual_disp_binder_t(         demand_queue_shptr_t demand_queue,         dispatcher_data_shptr_t disp_data ) noexcept         :  m_event_queue{ std::move(demand_queue), std::move(disp_data) }         {}      void      preallocate_resources(         so_5::agent_t & /*agent*/ ) override         {}      void      undo_preallocation(         so_5::agent_t & /*agent*/ ) noexcept override         {}      void      bind(         so_5::agent_t & agent ) noexcept override         {            agent.so_bind_to_dispatcher( m_event_queue );         }      void      unbind(         so_5::agent_t & /*agent*/ ) noexcept override         {}   };

Все, что данный disp_binder должен сделать это вызывать so_bind_to_dispatcher(). Никакого резервирования ресурсов выполнять не нужно. Т.к. единственный ресурс это экземпляр actual_event_queue_t, который автоматически создается вместе с disp_binder-ом.

one_thread-диспетчер

Рассматриваемый нами one_thread-диспетчер состоит из трех частей.

Во-первых, это структура dispatcher_data_t, которая хранит необходимые диспетчеру данные:

struct dispatcher_data_t   {      std::mutex m_lock;      std::condition_variable m_wakeup_cv;      bool m_shutdown{ false };      demand_queue_t * m_head{ nullptr };      demand_queue_t * m_tail{ nullptr };   };using dispatcher_data_shptr_t =      std::shared_ptr< dispatcher_data_t >;

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

Так что вторая часть диспетчера это реализация интерфейса event_queue_t для one_thread-диспетчера:

class actual_event_queue_t final : public so_5::event_queue_t   {      demand_queue_shptr_t m_demand_queue;      dispatcher_data_shptr_t m_disp_data;   public:      actual_event_queue_t(         demand_queue_shptr_t demand_queue,         dispatcher_data_shptr_t disp_data ) noexcept         :  m_demand_queue{ std::move(demand_queue) }         ,  m_disp_data{ std::move(disp_data) }         {}      void      push( so_5::execution_demand_t demand ) override         {            std::lock_guard< std::mutex > lock{ m_disp_data->m_lock };            auto & q = *m_demand_queue;            const bool queue_was_empty = q.empty();            q.push( std::move(demand) );            if( queue_was_empty )               {                  // В этом блоке кода исключений быть не должно.                  [&]() noexcept {                     const bool disp_was_sleeping =                           (nullptr == m_disp_data->m_head);                     if( disp_was_sleeping )                        {                           m_disp_data->m_head = m_disp_data->m_tail = &q;                           m_disp_data->m_wakeup_cv.notify_one();                        }                     else                        {                           m_disp_data->m_tail->set_next( &q );                           m_disp_data->m_tail = &q;                        }                  }();               }         }   };

Именно экземпляр такой event_queue и хранится внутри описанного выше disp_binder-а.

Тут нужно отметить, что в actual_event_queue_t хранится два умных указателя. Один на demand_queue, второй на экземпляр dispatcher_data_t. Тем самым контролируется время жизни этих сущностей. Т.е. и demand_queue, и dispatcher_data_t живут до тех пор, пока есть хотя бы один actual_event_queue_t. А поскольку actual_event_queue_t является частью disp_binder-а, то время жизни demand_queue и dispatcher_data_t определяется временем жизни disp_binder-ов. Когда все disp_binder-у исчезнут, пропадет и надобность в demand_queue и dispatcher_data_t.

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

Первый фрагмент это основная функция рабочей нити и обслуживание заявок из непустых demand_queue:

class dispatcher_t final   :  public std::enable_shared_from_this< dispatcher_t >   {      dispatcher_data_t m_disp_data;      std::thread m_worker_thread;      void      thread_body() noexcept         {            const auto thread_id = so_5::query_current_thread_id();            bool shutdown_initiated{ false };            while( !shutdown_initiated )               {                  std::unique_lock< std::mutex > lock{ m_disp_data.m_lock };                  shutdown_initiated = try_extract_and_execute_one_demand(                        thread_id,                        std::move(lock) );               }         }      [[nodiscard]]      bool      try_extract_and_execute_one_demand(         so_5::current_thread_id_t thread_id,         std::unique_lock< std::mutex > unique_lock ) noexcept         {            do               {                  auto [demand, has_non_empty_queues] =                        try_extract_demand_to_execute();                  if( demand )                     {                        unique_lock.unlock();                        demand->call_handler( thread_id );                        break;                     }                  else if( !has_non_empty_queues )                     {                        m_disp_data.m_wakeup_cv.wait( unique_lock );                     }               }            while( !m_disp_data.m_shutdown );            return m_disp_data.m_shutdown;         }      [[nodiscard]]      std::tuple< std::optional< so_5::execution_demand_t >, bool >      try_extract_demand_to_execute() noexcept         {            std::optional< so_5::execution_demand_t > result;            bool has_non_empty_queues{ false };            if( !m_disp_data.m_head )               return { result, has_non_empty_queues };            auto * dq = m_disp_data.m_head;            m_disp_data.m_head = dq->next();            dq->drop_next();            if( !m_disp_data.m_head )               m_disp_data.m_tail = nullptr;            else               has_non_empty_queues = true;            result = dq->try_extract();            if( !dq->empty() )               {                  if( m_disp_data.m_tail )                     m_disp_data.m_tail->set_next( dq );                  else                     m_disp_data.m_head = m_disp_data.m_tail = dq;               }            return { result, has_non_empty_queues };         }

Второй фрагмент это реализация метода make_disp_binder:

[[nodiscard]]so_5::disp_binder_shptr_tmake_disp_binder(   demand_queue_shptr_t demand_queue )   {      return std::make_shared< actual_disp_binder_t >(            std::move(demand_queue),            dispatcher_data_shptr_t{ shared_from_this(), &m_disp_data } );   }

Важный момент, который стоит здесь пояснить это факт того, что экземпляр dispatcher_data_t хранится в dispatcher_t по значению. Но в методе make_disp_binder в конструктор actual_disp_binder_t передается shared_ptr<dispatcher_data_t>. Тут всего лишь используется трюк c aliasing constructor для std::shared_ptr: хранить shared_ptr будет указатель на объект T, но вот счетчик ссылок будет использоваться от объекта Y. В нашем случае счетчик ссылок от dispatcher_t.

Вот, собственно, и все. Если кто-то хочет взглянуть на реализацию dispatcher_handler и make_dispatcher, то сделать это можно здесь.

Заключение

Данная статья преследует две цели:

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

Во-вторых, хочется понять, насколько вообще может быть востребованна подобная функциональность. Если у тех, кто пробовал SObjectizer или же присматривался к SObjectizer-у, время от времени надобность в приоритетной доставке сообщений возникает, то ее можно добавить в so5extra. Или даже в сам SObjectizer. Мы вполне можем это сделать. Но только если такая функциональность действительно востребована.

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

Кстати, SObjectizer-5 уже 10 лет

Разработка SObjectizer-5 началась осенью 2010-го года и продолжается до сих пор. Радует и удивляет. А если кому-то интересно что лично я думаю по этому поводу, то можно заглянуть сюда.

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

В этой статье мы попробуем разобраться с одним из самых неоднозначных и непонятных нововведений стандарта C++17 функцией стандартной библиотеки std::launder. Мы посмотрим на std::launder с другой стороны, посмотрим на источник. Разберем что лежит в основе функции на примере решения задачи девиртуализации и реализации виртуальных указателей в LLVM.

Девиртуализация это крайне важная оптимизация компилятора, которая позволяет заменить виртуальные (dynamic, indirect) вызовы обычными (static, direct). Виртуальные вызовы приводят к снижению производительности, не могут быть встроены, имеют более сложные механизмы спекулятивного выполнения (Indirect branch prediction), которые могут приводить к снижению безопасности и служить вектором атаки (например, Spectre). Clang и LLVM обеспечивают полную девиртуализацию виртуальных вызовов, когда удается статически определить динамический тип объекта или определить отсутствие переопределения метода и устраняют избыточную загрузку динамической информации (виртуальных таблиц) во всех остальных случаях.

Виртуальный вызов

Виртуальные вызовы реализуют концепцию, которая часто называется динамической диспетчеризацией (dynamic dispatch). Динамическая диспетчеризация это механизм, позволяющий выбрать реализацию полиморфного метода на основе динамического (фактического) типа объекта во время выполнения программы. По умолчанию вызовы методов выполняются в рамках статической диспетчеризации т.е. на основе статического типа известного во время компиляции. Спецификатор virtual у метода позволяет сменить тип диспетчеризации.

В выражение вида E1.E2, например, вызов метода a->foo() или a.foo(), выражение E1 называется object expression. Динамический тип в данном контексте это тип объекта, на который ссылается текущее значение выражения E1.

struct A{    int foo() { return 1; }    // объявление метода с virtual меняет статическую диспетчеризацию на динамическую.    virtual int bar() { return 1; }};struct B : A{    int foo() { return 2; }    int bar() override { return 2; }};int main(){    B b;    A *a = &b;    // вызов A::foo() на основе статического типа а    const int v1 = a->foo();    // вызов B::foo() на основе динамического (фактического) типа а.    // динамический тип это тип объекта, на который ссылается указатель а.    // в данном случае, это объект типа B.    const int v2 = a->bar();    assert(v1 == 1);    assert(v2 == 2);}

Стандарт не регулирует каким именно образом должен быть реализован механизм динамической диспетчеризации. Все современные компиляторы C++ реализуют динамическую диспетчеризацию и виртуальные вызовы с помощью специальных структур: виртуальных таблиц (virtual table, vtable, vtbl).

Виртуальные таблицы

Виртуальные таблицы генерируются для каждого класса с виртуальными методами или виртуальными базовыми классами. Во время создания экземпляра такого класса, адрес соответствующей таблицы записывается в специальное техническое поле: виртуальный указатель (virtual pointer). Виртуальных указателей может быть несколько, для каждого базового класса. При этом под адресом виртуальной таблицы т.е. адрес, который будет записан в виртуальный указатель экземпляра класса, не всегда понимается адрес начала таблицы. В терминах ABI этот адрес называется address point. Доступ ко всем записям таблицы осуществляется фиксированными смещениями, как положительными, так и отрицательными, относительно этого адреса.

Виртуальные таблицы содержат следующую информацию:

1. Virtual call offsets. Записи содержат смещения для корректировки указателя (this) от виртуального базового класса до класса-потомка. Используются для вызова переопределенного в классе-потомке метода виртуального базового класса.
2. Virtual base offsets. Записи содержат смешения от адреса поля виртуального указателя до адреса подобъекта виртуального базового класса. Добавляется для каждого виртуального базового класса.
3. Offset to top. Запись содержит смешение от адреса поля виртуального указателя до адреса начала объекта т.е. адреса первого байта. Смещение позволяет найти начало объекта из любого базового подобъекта с помощью виртуального указателя.
4. Typeinfo pointer. Запись содержит адрес объекта с данными о типе RTTI.
5. Virtual function pointers. Записи содержат адреса виртуальных методов класса или адреса вторичных точек входа (thunk). Используются для динамической диспетчеризации. Реализация таких указателей определяется конкретным ABI. Последовательность записей совпадает с последовательностью объявлений соответствующих методов в классах. Все записи в таблицах иерархии совместимых классов находятся в согласованном состояние т.е. для каждого виртуального метода в дереве наследования имеется одно, фиксированное смещение в таблице. Если дочерний класс перегружает реализацию базового метода, то в таблице этого класса меняется соответствующая запись на адрес перегруженного метода. Такая таблица совместима с таблицей базового класса.

Например, для иерархии классов:

struct A{    void s();    virtual void f();    virtual void g();};struct B : A{    void f() override;    virtual void h();};struct C{    virtual void k();};struct D : A, C{    void g() override;    void k() override;};

Будут сгенерированы следующие таблицы (x86-64 clang 10.0.0):

# виртуальная таблица для класса Аvtable for A:    .quad 0                # Смещение Offset To Top    .quad typeinfo for A   # адрес объекта typeinfo с данными о типе RTTI    .quad A::f()           # адрес базовой реализации метода f()    .quad A::g()           # адрес базовой реализации метода g()# виртуальная таблица для класса Bvtable for B:    .quad 0                # Смещение Offset To Top    .quad typeinfo for B   # адрес объекта typeinfo с данными о типе RTTI    .quad B::f()           # адрес переопределенного метода f()    .quad A::g()           # адрес базовой реализации метода g()    .quad B::h()           # адрес метода h()# виртуальная таблица для класса Cvtable for C:    .quad 0                # Смещение Offset To Top    .quad typeinfo for C   # адрес объекта typeinfo с данными о типе RTTI    .quad C::k()           # адрес базовой реализации метода k()# виртуальная таблица для класса D# состоит из двух таблиц,# одна совместима с виртуальной таблицей B, другая с виртуальной таблицей Cvtable for D:    #                        Cовместимая с B таблица    .quad 0                # Смещение Offset To Top    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI    .quad A::f()           # адрес базовой реализации метода f()    .quad D::g()           # адрес переопределенного метода g()    .quad D::k()           # адрес переопределенного метода k()    #                        Cовместимая с С таблица    .quad -8               # Смещение Offset To Top    .quad typeinfo for D   # адрес объекта typeinfo с данными о типе RTTI    .quad thunk for D::k() # вторичная точка входа для переопределенного метода D::k()

Можно заметить, что записи о виртуальных методах в таблицах совместимы, например, метод f() имеет одно и тоже смещение во всех таблицах совместимых типов (А, B, D).

Класс D использует множественное наследование с несколькими базовыми классами: A и C. Объект типа D содержит два виртуальных указателя. Один принадлежит базовому подобъекту A и указывает на таблицу совместимую с таблицей класса A, другой принадлежит базовому подобъекту C и содержит адрес таблицы совместимой с виртуальной таблицей класса C.

Чтобы понять почему в таблице совместимой с классом С вместо указателя на метод D::k() помещен thunk for D::k(), рассмотрим следующий код:

D *d = new D;A *a = dynamic_cast<A*>(d);C *c = dynamic_cast<C*>(d);c->k();

Если посмотреть на адреса d, a, c и this в методе k(), то они будут, например, такими

d:    0x1edcee0a:    0x1edcee0c:    0x1edcee8this: 0x1edcee0

Адреса d, а, this совпадают, а адрес с смещен на 8 байт относительно d. Так происходит из-за того, что в памяти базовый подобъект C смещен на 8 байт из-за технического поля (виртуального указателя) базового подобъекта A. Поэтому при вызове, мы не можем передать c в качестве this в метод k(). Перед вызовом this должен быть скорректирован, чтобы указывать на объект класса, который выполнил переопределение метода. Именно эту корректировку и делает thunk перед передачей управления методу k().

Таким образом, вторичная точка входа thunk это сегмент кода ассоциированный с целевым методом, который выполняет определенные корректировки входных параметров (например, this) перед передачей управления методу. Thunk может содержать просто дополнительную инcтрукцию, которая будет выполнена до перехода к целевому методу или быть полноценной функцией со своим стековым кадром и дальнейшим полноценным вызовом метода. Используется при множественном наследовании.

Ассоциация виртуальных таблиц

При создании объекта в конструкторах генерируется код, сохраняющий адрес соответствующей виртуальной таблицы в поле виртуального указателя.

void test(A *a){    a->s();    a->f();    a->f();    a->g();}int main(){    A *a = new B;    test(a);}

Будет сгенерирован следующий код (x86-64 clang 10.0.0):

# виртуальная таблица для класса Аvtable for A:    .quad 0    .quad typeinfo for A    .quad A::f()   # address point    .quad A::g()# виртуальная таблица для класса Bvtable for B:    .quad 0    .quad typeinfo for B    .quad B::f()   # address point    .quad A::g()    .quad B::h()main:    push    rbx    mov     edi, 8    # new expression    # вызов оператора new    call    operator new(unsigned long)    mov     rbx, rax    mov     rdi, rax    # вызов конструктора B    call    B::B() [base object constructor]    mov     rdi, rbx    call    test(A*)    xor     eax, eax    pop     rbx    ret# конструктор класса BB::B() [base object constructor]:    push    rbx    mov     rbx, rdi    # вызов конструктора базового класса A    call    A::A() [base object constructor]    # сохраняем адрес виртуальной таблицы (address point) класса B    # переписываем значение сохраненное в конструкторе базового класса    # 16 - это смещение до address point таблицы B    mov     qword ptr [rbx], offset vtable for B+16    pop     rbx    ret# конструктор класса AA::A() [base object constructor]:    # сохраняем адрес виртуальной таблицы (address point) класса A    # 16 - это смещение до address point таблицы A    mov     qword ptr [rdi], offset vtable for A+16    ret

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

Вызов виртуального метода

В общем случае виртуальный вызов состоит из следующих шагов:

1. Прочитать адрес виртуальной таблицы из виртуального указателя;
2. Сместить значение загруженного указателя до записи в таблице с адресом вызываемого метода;
3. Прочитать адрес метода;
4. Выполнить косвенный вызов по прочитанному адресу.

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

Сгенерированный код функции test() из предыдущего примера (x86-64 clang 10.0.0 -std=c++17 -O1):

test(A*):    push    rbx    mov     rbx, rdi    # вызов a->e()    # прямой вызов метода по фиксированному адресу, статическая диспетчеризация,    # тип известен на этапе компиляции    call    A::e()    # вызов a->f()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода f()    mov     rax, qword ptr [rbx]    # читаем адрес f() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax]    # еще один вызов a->f()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода в f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    # читаем адрес f() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax]    # вызов a->g()    # читаем виртуальный указатель, хранит    # адрес записи в виртуальной таблице с адресом метода в f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    # смещаем на следующую запись относительно f(): adress point + 8    # запись содержит адрес метода g()    # читаем адрес g() из таблицы и выполняем косвенный вызов метода    call    qword ptr [rax + 8]    pop     rbx    ret

Задача девиртуализации заключается в замене виртуальных (косвенных) вызовов прямыми (с фиксированным адресом), в случае когда удается статически (во время компиляции) определить динамический тип объекта или убедиться, что виртуальный метод не переопределен. Если на этапе компиляции динамический тип определить не удалось, то устранить избыточное чтение виртуальных указателей и адресов методов.

Девиртуализация может быть выполнена на разных уровнях:

1. Front-end. На уровне конкретного языка, эксплуатируя конкретные языковые особенности;
2. Middle-end. На уровне промежуточного представления, в нашем случае LLVM IR, до этапа генерации кода.

Front-end. Девиртуализация на уровне C++

Девиртуализация по своей природе является оптимизацией конкретного языка, поэтому естественно ожидать, что она будет реализована во внешнем интерфейсе. Исключая LTO (Link-Time Optimization), в обрабатываемом юните трансляции есть только несколько случаев, когда компилятор может сделать вывод об отсутствии переопределения метода или статически определить динамический тип объекта.

Динамический тип совпадает со статическим

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    B a;    a.f();    a.f();}

По стандарту, вызов a.f() также является виртуальным. Любой вызов виртуального метода является виртуальным, исключая вызовы с явно квалифицированным именем метода. Т.е. вызов a.A::f() выполняется в рамках статической диспетчеризации.

Напомним, что в выражении вида E1.E2, например, вызов метода a.f(), динамический тип это тип объекта, на который ссылается значение выражения E1 (object expression). Значение выражения в данном случае, является сам объект а, т.е. динамический и статический тип совпадают. Поэтому мы можем просто заменить косвенный вызов на прямой.

Будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O0):

test():    push    rbp    mov     rbp, rsp    sub     rsp, 16    lea     rdi, [rbp - 8]    call    B::B() [base object constructor]    lea     rdi, [rbp - 8]    # прямой вызов B::f()    call    B::f()    lea     rdi, [rbp - 8]    # прямой вызов B::f()    call    B::f()    add     rsp, 16    pop     rbp    ret

Вызов виртуальных методов в конструкторе/деструкторе

struct A{    A()    {        f();    }    virtual ~A()    {        f();    }    virtual void f();};struct B : A{    B()    {        f();    }    ~B()    {        f();    }    void f() override;};

Поcмотрим еще раз на генерируемый код и на порядок инициализации виртуального указателя в конструкторе/деструкторе.

# конструктор класса AA::A() [base object constructor]:    push    rax    # сохраняем адрес виртуальной таблицы для класса А    mov     qword ptr [rdi], offset vtable for A+16    # прямой вызов A::f();    call    A::f()    pop     rax    ret# деструктор класса AA::~A() [base object destructor]:    push    rax    # сохраняем адрес виртуальной таблицы для класса А    mov     qword ptr [rdi], offset vtable for A+16    # прямой вызов A::f()    call    A::f()    pop     rax    ret# конструктор класса BB::B() [base object constructor]:    push    rbx    mov     rbx, rdi    # вызов конструктора базового класса    call    A::A() [base object constructor]    # сохраняем адрес виртуальной таблицы для класса B    mov     qword ptr [rbx], offset vtable for B+16    mov     rdi, rbx    # прямой вызов B::f()    call    B::f()    pop     rbx    ret# деструктор класса BB::~B() [base object destructor]:    push    rbx    mov     rbx, rdi    # сохраняем адрес виртуальной таблицы для класса B    mov     qword ptr [rdi], offset vtable for B+16    # прямой вызов B::()    call    B::f()    mov     rdi, rbx    # вызов деструктора базового класса    call    A::~A() [base object destructor]    pop     rbx    ret

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

На front-end'е эту оптимизацию делают GCC и MSVC. Clang оставляет эту задачу LLVM. LLVM оптимизирует эти вызовы с помощью store to load propagation (в конструкторе/деструкторе видны запись и чтение виртуального указателя) в рамках прохода GVN (Global Value Numbering).

Локализация класса в юните трансляции

namespace{    struct A    {        virtual int f() { return 1; }    };}int test(A *a){    return a->f();}

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

Финализация класса/метода

struct A{    virtual int f() final;    virtual int g();};struct B final : A{    int g() override;};void test(A *a, B *b){    a->f();    a->g();    b->g();}

Сгенерированный код (x86-64 clang 10.0.0 -std=c++17 -O0):

test(A*, B*):    push    rbp    mov     rbp, rsp    sub     rsp, 32    mov     qword ptr [rbp - 8], rdi    mov     qword ptr [rbp - 16], rsi    mov     rdi, qword ptr [rbp - 8]    # прямой вызов A::f(),    # метод f() финализирован в классе А и не может быть переопределен    call    A::f()    mov     rcx, qword ptr [rbp - 8]    mov     rdx, qword ptr [rcx]    mov     rdi, rcx    mov     dword ptr [rbp - 20], eax    # косвенный вызов метода g(),     # т.к. может существовать класс-потомок переопределяющий метод    call    qword ptr [rdx + 8]    mov     rdi, qword ptr [rbp - 16]    mov     dword ptr [rbp - 24], eax    # прямой вызов B::g(), т.к. класс B финализирован    call    B::g()    add     rsp, 32    pop     rbp    ret

Middle-end. Девиртуализация на уровне промежуточного представления

Рассмотрим небольшой пример, чтобы понять на чем оcнован традиционный подход к девиртуализации:

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    A *a = new B;    a->f();}

Для девиртуализации метода, компилятору нужно знать три вещи:

1. Значение виртуального указателя. Адрес конкретной виртуальной таблицы. Т.е. по сути, компилятор должен видеть значение, которое записывается в виртуальный указатель в конструкторе.
2. Адрес конкретного метода. Т.к. виртуальные таблицы константны: генерируются для каждого типа в момент компиляции и не могут меняться во время выполнения, то для получения адреса метода из таблицы, наблюдая значение виртуального указателя (конкретную таблицу), нам достаточно просто определения этой таблицы (virtual table definition).
3. Компилятор должен быть уверен, что с момента инициализации виртуального указателя (записи значения) в конструкторе и до момента вызова конкретного виртуального метода т.е. чтения виртуального указателя, его значение не переписывается (no clobbering).

Если все эти условия соблюдены, то компилятор может выполнить store to load propagation на виртуальном указателе и заменить виртуальный вызов прямым. Здесь важно понимать, что это оптимизация на уровне промежуточного представления (target-independed optimization) и код обрабатывается без какой-либо семантической нагрузки из C++.

Например, выше мы рассматривали вызов виртуального метода в конструкторе. Там все условия соблюдаются, поэтому Clang/LLVM выполнят девиртуализацию таких вызовов.

Для функции test после всех оптимизаций в IR будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2):

test():    push    rax    mov     edi, 8    call    operator new(unsigned long)    # заинлайненый конструктор объекта B    # сохранение адреса виртуальной таблицы в виртуальный указатель    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    pop     rax    # прямой вызов f()    jmp     B::f()

В этом подходе есть ряд ограничений.

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

Для функции test будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2 -fno-inline):

test():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    mov     rdi, rax    # внешний конструктор    call    B::B() [base object constructor]    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов f()    jmp     qword ptr [rax]B::B() [base object constructor]:    push    rbx    mov     rbx, rdi    call    A::A() [base object constructor]    mov     qword ptr [rbx], offset vtable for B+16    pop     rbx    ret

В точке вызова компилятор не видит инициализацию виртуального указателя и не может сделать предположение о его значении после вызова конструктора объекта.

Вторая проблема заключается в отслеживании инварианта виртуального указателя. Следует отметить, что ни каких дополнительных знаний о виртуальном указателе у компилятора нет и отслеживание состояния сводится к отслеживанию инструкций записи. Эта задача лежит на модуле Alias Analysis (Pointer Analysis). Это набор алгоритмов, с помощью которых модуль в общем случае пытается определить: могут ли два указателя ссылаться на один и тот же объект в памяти. Для поиска предшествующих операций с памятью, от которых зависит заданная инструкция, LLVM может использовать интерфейс MemDep (Memory Dependence Analysis) или более эффективный MemSSA (Memory SSA). Одно из основных положение такого анализа это отслеживание: выходит ли указатель за пределы функции или юнита трансляции т.е. обращаются ли к памяти со стороны или мы работаем с памятью локально. Для локальной обработки алгоритмы могут достаточно точно определить какие указатели могут указывать на объект и соответственно какие инструкции этот объект меняют. В случае выхода указателя за пределы анализатор предполагает, что память может быть перезаписана.

Дополним пример выше:

struct A{    virtual void f();};struct B : A{    void f() override;};void test(){    A *a = new B;    a->f();    // второй вызов виртуального метода,     // компилятор не видит определение метода f()    a->f();}void foo(A *a);void test1(){    A *a = new B;    // вызов внешней функции и передача указателя    foo(a);    a->f();}

Будет сгенерирован следующий код (x86-64 clang 10.0.0 -std=c++17 -O2):

test():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    # прямой вызов метода f()    call    B::f()    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов метода f()    jmp     qword ptr [rax]test1():    push    rbx    mov     edi, 8    call    operator new(unsigned long)    mov     rbx, rax    # встроенный конструктор    mov     qword ptr [rax], offset vtable for B+16    mov     rdi, rax    # вызов внешней функции    call    foo(A*)    mov     rax, qword ptr [rbx]    mov     rdi, rbx    pop     rbx    # косвенный вызов метода f()    jmp     qword ptr [rax]

Второй вызов метода f() в функции test() не будет оптимизирован. Так происходит потому, что анализатор не знает что на самом деле делает метод f() и у него нет другой альтернативы кроме как предположить худший вариант: представление объекта, на который указывает а может поменяться, смениться динамический тип и соответственно значение виртуального указателя. Аналогичная ситуация с функцией test1() и вызовом foo(a). Еще раз заметим, что с точки зрения LLVM виртуальный указатель это просто указатель с адресом, как любой другой. Ни какой семантики из C++ на него не наложено.

Ключевой вопрос здесь, каким образом мы может изменить динамический тип объекта и значение виртуального указателя в C++?

Кроме того, что виртуальный указатель несколько раз меняется в процессе вызова конструктора и деструктора, объектная модель C++ дает нам возможность завершить время жизни (lifetime) любого объекта и переиспользовать выделенную под него память, создав там другой объект.

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

Существование объекта можно разделить на следующие этапы:

1. Память под объект была выделана, время жизни объекта еще не началось;
2. Процесс создания объекта (constructor);
3. Существование объекта;
4. Процесс уничтожения объекта (destructor);
5. Время жизни объекта закончилось, память или переиспользуется другим объектом или освобождена.

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

• Указатель не может выступать в качестве операнда delete expression, если время жизни объекта было закончено. Исключая объекты с тривиальным деструктором;
• Указатель не может использоваться для доступа к полям и методам класса;
• Указатель не может быть приведен к указателю на виртуальный базовый класс;
• Указатель не может выступать в качестве операнда static_cast. Исключая приведение к void* и/или дальнейшее приведение к char*, unsigned char* или std::byte*;
• Указатель не может выступать операндом dynamic_cast.

Т.е. каждое из этих условий требует доступ к объекту, который еще не был создан или уже был удален.

Здесь есть важное замечание. Если после завершения времени жизни объекта мы переиспользуем память и вновь созданный объект имеет заменяемый тип (transparently replaceable), то все указатели, ссылки и имена, которые ссылались на исходный объект, автоматически начинают указывать на новый и могут быть использованы для оперирования новым объектом. Два типа называются заменяемыми, в данном контексте, если выполнены следующие условия:

• Новый объект использует в точности всю память старого объекта;
• Объекты имеют одинаковый тип с точностью до cv-квалификаторов;
• Тип исходный объект не является константным и тип не содержит константных или ссылочных полей (в случае пользовательского типа данных).

Ниже мы увидим что transparently replaceable является крайне точным термином.

Вернемся к нашему примеру:

void B::f(){    // виртуальный метод класса меняет динамический тип объекта    // мы завершаем время жизни существующего объекта    // и создаем новый другого типа    new(this) A;}void test(){    A *a = new B;    a->f();    // неопределенное поведение    a->f();}

Код метода B::f(), с точки зрения описанных выше правил, корректен, но т.к. типы исходного и нового объектов не заменяемы, то все существующие указатели (включая this) мы можем использовать только ограниченным образом, т.е. только как указатели на область памяти, а не как указатели на конкретные объекты. Как следствие, второй вызов метода a->f() приводит к неопределенному поведению, т.к. указатель a ссылается на объект, чье время жизни было закончено.

Для полноты описания так же заметим, что placement new возвращает указатель, который может быть использован для манипулирования новым объектом.

Например:

void B::f(){    // виртуальный метод класса меняет динамический тип объекта    // мы завершаем время жизни существующего объекта    // и создаем новый, другого типа    A *a = new(this) A;    // a может может использоваться для доступа к методам и полям нового объекта    // однако вызов g(), используя this является Undefined Behavior,    // при этом this и a, по умолчанию, указываю на одну и ту же область памяти    a->g();    // создаем еще один объект с исходным типом    // использование this является корректным, а    // использование указателя a для доступа к полям Undefined Behavior    new (this) B;    g();}

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

Основная сложность представления в LLVM IR описанной семантики заключается в том, что указатели ссылающиеся на один и тот же адрес могут указывать на объекты с разным временем жизни и не должны рассматриваться как эквивалентные т.е. с точки зрения оптимизатора не могут участвовать в подстановке (substitution).
Реализация Clang/LLVM позволяющая выразить семантику выше, время жизни динамических объектов и инварианты виртуальных указателей, доступна с флагом -fstrict-vtable-pointers.

Инварианты виртуальных указателей

Мы будем рассматривать код:

struct A{    virtual void f();    virtual void g();};struct B : A{    void f() override;    void g() override;};A* get_object();void test(){    A *a = get_object();    a->f();    a->f();    a->f();    a->g();}

Используя традиционный, описанный выше, подход к девиртуализации, cо всеми оптимизациями в IR мы получим следующий код (x86-64 clang 10.0.0 -std=c++17 -O2, код немного упрощен, убраны несущественные детали, атрибуты, метаданные).

define dso_local void @test(){    ; запрос объекта    %1 = call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; вызов метода f()    ; чтение виртуального указателя    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; чтение адреса метода f()    %4 = load void (%struct.A*)*, void (%struct.A*)** %3    ; косвенный вызов f()    call void %4(%struct.A* %1)    ; второй вызов метода f()    ; повторное чтение виртуального указателя    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; повторное чтение адреса метода f()    %6 = load void (%struct.A*)*, void (%struct.A*)** %5    ; косвенный вызов f()    call void %6(%struct.A* %1)    ; третий вызов f()    ; еще одно чтение виртуального указателя    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; еще одно чтение адреса метода f()    %8 = load void (%struct.A*)*, void (%struct.A*)** %7    ; косвенный вызов f()    call void %8(%struct.A* %1)    ; вызов метода g()    ; еще одно чтение виртуального указателя    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2    ; смещение адреса виртуальной таблицы до записи с адресом метода g()    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1    ; чтение адреса метода g()    %11 = load void (%struct.A*)*, void (%struct.A*)** %10    ; косвенный вызов g()    call void %11(%struct.A* %1)}

В данном случае, ни один вызов не будет девиртуализирован, потому что компилятор не видит что делает функция get_object, не видит создание объекта и запись виртуального указателя. Задача LLVM, в данном примере, учесть факт того, что динамический тип не может поменяться в процессе вызовов, выразив инвариантность виртуального указателя и константность виртуальной таблицы, избавившись в итоге от избыточного чтения.

LLVM расширяет список возможных метаданных инструкций чтения и записи новым элементом invariant.group. Метаданные инструкций это подсказка оптимизатору об уникальных свойствах инструкции. Наличие или отсутствие таких метаданных не меняет семантику программы.

Присутствие метаданных в инструкции invariant.group указывает оптимизатору, что чтение/запись с одним и тем же операндом или другими словами, если операнд принадлежит одной и той же инвариантной группе, возвращает/сохраняет одно и тоже значение. Чтобы выразить инвариант виртуального указателя, каждая инструкция чтения виртуального указателя (в рамках виртуального вызова) и каждая инструкция записи виртуального указателя (в рамках инициализации в конструкторе/деструкторе) сопровождается метаданными invariant.group.

Так же каждую инструкцию чтения виртуальной таблицы в процессе виртуального вызова LLVM сопровождает метаданными invariant.load. Эти метаданные указывают на то, что область памяти, на которую ссылается операнд инструкции чтения, содержит одно и тоже значение независимо от того в какой момент и где мы эти данные читаются. Это позволяет выразить тот факт, что содержимое виртуальной таблицы постоянно и в процессе выполнения меняется не может.

define dso_local void @test(){    ; запрос объекта    %1 = tail call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; вызов метода f()    ; чтение виртуального указателя,    ; инструкция содержит метаданные invariant.group    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}    tail call void %4(%struct.A* %1)    ; второй вызов метода f()    ; повторное чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %5 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу    ; постоянны и не могут изменится в процессе выполнения    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    tail call void %6(%struct.A* %1)    ; третий вызов f()    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %7 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы,    ; инструкция содержит метаданные invariant.load    ; оптимизатор знает что данные загружаемые инструкцией по переданному адресу    ; постоянны и не могут изменится в процессе выполнения    %8 = load void (%struct.A*)*, void (%struct.A*)** %7, !invariant.load !{}    tail call void %8(%struct.A* %1)    ; вызов метода g()    ; еще одно чтение виртуального указателя, инструкция помечена invariant.group    ; оптимизатор может предположить что данные уже прочитаны в %3    %9 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    %10 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %9, i64 1    ; чтение адреса метода g() из виртуальной таблицы,    ; инструкция содержит метаданные !invariant.load    %11 = load void (%struct.A*)*, void (%struct.A*)** %10, !invariant.load !{}    tail call void %11(%struct.A* %1)}

Обработку этих метаданных берет на себя модуль MemDep. В итоге после оптимизации (-std=c++17 -O2 -fstrict-vtable-pointers) мы получаем следующее:

define dso_local void @test(){    ; запрос объекта    %1 = tail call %struct.A* @get_object()    %2 = bitcast %struct.A* %1 to void (%struct.A*)***    ; чтение виртуального указателя, избыточные чтения удалены    %3 = load void (%struct.A*)**, void (%struct.A*)*** %2, !invariant.group !{}    ; чтение адреса метода f() из виртуальной таблицы    %4 = load void (%struct.A*)*, void (%struct.A*)** %3, !invariant.load !{}    ; три косвенных вызова метода f()    tail call void %4(%struct.A* %1)    tail call void %4(%struct.A* %1)    tail call void %4(%struct.A* %1)    ; смещение адреса виртуальной таблицы до записи с адресом метода g()    %5 = getelementptr inbounds void (%struct.A*)*, void (%struct.A*)** %3, i64 1    ; чтение адреса метода g() из виртуальной таблицы,    ; виртуальный указатель уже прочитан    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    ; косвенный вызов метода g()    tail call void %6(%struct.A* %1)}

И после генерации кода back-end'ом:

test():        push    r15        push    r14        push    rbx        call    get_object()        mov     rbx, rax        mov     rax, qword ptr [rax]        mov     r14, qword ptr [rax]        mov     r15, rax        mov     rdi, rbx        call    r14        mov     rdi, rbx        call    r14        mov     rdi, rbx        call    r14        mov     rdi, rbx        mov     rax, r15        pop     rbx        pop     r14        pop     r15        jmp     qword ptr [rax + 8]

Проблема внешнего конструктора

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

Рассмотрим пример с отключенным инлайненгом (x86-64 clang 10.0.0 -std=c++17 -O2 -fno-inline -fstrict-vtable-pointers):

struct A{    virtual void f();};void test(){    A *a = new A;    a->f();}

define void @test(){    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    ; вызов конструктора объекта A::A()    call void @Constructor_A(%struct.A* nonnull %2)    %3 = bitcast i8* %1 to i8***    ; читаем адрес сохраненный в виртуальном указателе    ; важно что чтение также сопровождается метаданными invariant.group    %4 = load i8**, i8*** %3, !invariant.group !{}    ; сравниваем прочитанное значение с адресом виртуальной таблицы для класса A    %5 = icmp eq i8** %4, @VTABLE_A    ; вызываем llvm.assume и передаем результат сравнения.    call void @llvm.assume(i1 %5)    ; в итоге прямой вызов метода A::f()    call void @f(%struct.A* nonnull %2)    ret void}; конструктор класса Adefine void @Constructor_A(%struct.A* %0){    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0    ; сохранение адреса виртуальной таблицы A в виртуальный указатель объекта    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group !{}    ret void}

После вызова конструктора генерируются три дополнительные инструкции:

1. Чтение виртуального указателя вновь созданного объекта. Чтение сопровождается метаданными invariant.group.
2. Сравнение загруженного адреса виртуальной таблицы с адресом предполагаемой таблицы (исходя из типа объекта);
3. Вызов и передача результата сравнения в @llvm.assume. Встроенная функция @llvm.assume не генерирует ни каких дополнительных инструкций. Семантически вызов похож на assert на уровне оптимизатора и позволяет предположить, что переданный результат сравнения всегда истинен, если условие нарушается, то дальнейшее поведение считается неопределенным.

В результате к моменту вызова у оптимизатора уже есть актуальное значение виртуального указателя: оптимизатор сделал предположение чему он равен. И вызов может быть девиртуализирован.

В случае когда удалось встроить конструктор, все инструкции выше могут быть оптимизированы:

    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    %3 = bitcast i8* %1 to i8***    ; встроенный конструктор,    ; сохраняем адрес виртуальной таблицы в виртуальном указателе.    ; запись помечена invariant.group, это значит  что в рамках этой инвариантной группы    ; в этом виртуальном указателе может быть сохранен только @VTABLE_A    store i32 (...)** @VTABLE_A, i32 (...)*** %3, !invariant.group !{}    ; читаем адрес сохраненный в виртуальном указателе.    ; чтение сопровождается метаданными invariant.group    ; чтение принадлежит той же инвариантной группе, что и запись выше.    ; у оптимизатора уже есть информация, что по этому адресу может быть записан только @VTABLE_A    ; и чтение может быть заменено на @VTABLE_A    %4 = load i8**, i8*** %3, !invariant.group !{}    ; после оптимизации чтения это условие всегда true: @VTABLE_A == @VTABLE_A    %5 = icmp eq i8** %4, @VTABLE_A    ; вызов llvm.assume(true) можно удалить    call void @llvm.assume(i1 %5)

Барьеры оптимизации

Существует ряд семантических случаев, когда виртуальный указатель меняет свое значение:

• Конструкторы. Конструктор каждого класса в иерархии инициализирует виртуальный указатель адресом своей виртуальной таблицы;
• Деструкторы. Деструкторы каждого класса восстанавливают значение виртуального указателя для безопасного использования виртуальных методов;
• Placement new. Выражение завершает время жизни объекта (если используется тривиальный деструктор) и переиспользует выделенную под него память, создав там другой объект. В результате меняется динамический тип и соответственно значение виртуального указателя. Возвращает указатель, для доступа к новому объекту.

В рамках семантики инвариантных групп у инструкций чтения и записи нам нужны инструменты, чтобы сообщить оптимизатору, что информация об инварианте обновилась или ее не нужно учитывать. Необходимо предусмотреть случай сравнения двух указателей в рамках оптимизации. Указатели могут ссылаться на одну и туже область памяти, но на объекты с разным временем жизни. Равенство таких указателей не должна вводить в заблуждение оптимизатор: оптимизатор не должен иметь возможность выполнить подстановку (substitution). Необходимо выразить концепцию equal-but-not-equivalent.

LLVM вводит две дополнительные операции: strip и launder.

Операция strip

Операция strip может использоваться, когда нам нужен указатель на те же данные с возможностью доступа к ним, но без инвариантной информации установленной метаданными invariant.group.
Операция представлена новой встроенной функцией @llvm.strip.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и убирает ассоциацию указателя с инвариантной группой.

Свойства операции:

• Операция является детерминированной и не обладает побочными эффектами. Т.е. возвращаемое значение зависит только от переданного аргумента. Такие операции часто называются чистыми (pure);
• Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
• strip(X) == strip(strip(X)). Т.к. операция не берет во внимание ассоциированные инвариантные данные.

Один из случаев использования операции strip это сравнение указателей:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    if (a == b)        b->f();}

    ...    ; читаем адрес виртуальной таблицы а    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}    ...    ; if(a == b)    %res = icmp eq %struct.A* %a, %b    br %res, label %if, label %after    if:        ; если %b будет заменен на %a,        ; то оптимизатор заменить чтение адреса виртуальной таблицы %vtable_b        ; на уже прочитанный %vtable_a.        ; т.к. чтение сопровождается метаданными invariant.group        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}        ...    ...

Проблема в том, что LLVM основываясь на результате сравнения a и b может заменить SSA значение b на a (в проходе GVN). Это абсолютно легальная оптимизация. Но в рамках девиртуализации и обработки инвариантов, такая замена приведет к неопределенному поведению, потому что при втором вызове метода f() будет использоваться не та виртуальная таблица.

Решение заключается в сравнение указателей без учета инвариантной информации:

    ...    ; читаем адрес виртуальной таблицы a    %vtable_a = load void (%struct.A*)**, void (%struct.A*)*** %a, !invariant.group !{}    ...    ; if(a == b)    ; сравниваем указатели без инвариантов    ; strip_a и strip_b имеют доступ и указывают на ту же область,    ; на которую указывают a и b соответственно    %strip_a = call i8 * @llvm.strip.invariant.group(i8 * %a)    %strip_b = call i8 * @llvm.strip.invariant.group(i8 * %b)    %res = icmp eq %struct.A* %strip_a, %strip_b    br %res, label %if, label %after    if:        ; Равенство псевдонимов не является достаточной причиной для оптимизатора,        ; чтобы выполнить подстановку исходных указателей        %vtable_b = load void (%struct.B*)**, void (%struct.B*)*** %b, !invariant.group !{}        ...    ...

Операция launder

Операция launder используется, когда нам нужен указатель на те же данные с возможностью доступа к ним, но c очищенной информацией об инварианте.
Операция представлена новой встроенной функцией @llvm.launder.invariant.group. Функция возвращает новый указатель, который является псевдонимом (alias) переданному аргументу, т.е. указывает и может использоваться для доступа к той же памяти что и аргумент и ассоциирует указатель с новой инвариантной группой. Т.е. переданный в функцию указатель и новый указатель, в контексте обработки метаданных invariant.group на операциях чтения и записи, рассматриваются как два разных указателя.

Свойства операции:

• Операция по своей сути является недетерминированной. Ни какие два вызова не возвращают одинаковое значение;
• Возвращает псевдоним аргумента (alias). Возвращает указатель, который указывает и может использоваться для доступа к той же памяти что и аргумент;
• strip(x) == strip(launder(x)).

LLVM использует операцию launder во всех семантических случаях, когда виртуальный указатель меняет свое значение т.е. каждое новое значение виртуального указателя должно принадлежать своей инвариантной группе, это позволяет в процессе девиртуализации избежать неопределенного поведения. Также операция используется в ряде краевых случаев, таких как доступ к членам union.

В случае конструктора/деструктора, каждый класс-потомок передает в конструктор/деструктор базового класса launder(this):

; конструктор класса Adefine void @Constructor_A(%struct.A* %0){    %2 = getelementptr %struct.A, %struct.A* %0, i64 0, i32 0    ; запись адреса виртуальной таблицы A    store i32 (...)** @VTABLE_A, i32 (...)*** %2, !invariant.group, !{}    ret void}; конструктор класса Bdefine void @Constructor_B(%struct.B* %0){    %2 = bitcast %struct.B* %0 to i8*    ; запрос нового указателя с новой инвариантной группой launder(this)    %3 = call i8* @llvm.launder.invariant.group(i8* %2)    %4 = bitcast i8* %3 to %struct.A*    ; передача launder(this) в конструктор базового класса A    call void @Constructor_A(%struct.A* %4)    %5 = getelementptr %struct.B, %struct.B* %0, i64 0, i32 0, i32 0    ; запись адреса виртуальной таблицы B    store i32 (...)** @VTABLE_B, i32 (...)*** %5, !invariant.group, !{}    ret void}

Детально рассмотрим случай выражения placement new:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    b->f();}

Если мы используем умалчиваемую реализацию оператора размещающего new, то указатель a будет побитово равен указателю b. Но в рамках объектной модели C++, a и b указывают на разные объекты: a указывает на объект типа A, время жизни которого завершено, b указывает на вновь созданный, в той же области памяти, объект типа B. Соответственно, в контексте девиртуализации вызов b->f() должен загружать правильную виртуальную таблицу: таблицу класса B и указатели a и b не должны рассматриваться как эквивалентные. С помощью операции launder оптимизатор может достичь описанной семантики.

define void @test(){    ; new expression    ; вызов оператора new    %1 = call dereferenceable(8) i8* @New(i64 8)    %2 = bitcast i8* %1 to %struct.A*    ; создание объекта типа A, вызов конструктора A    %3 = call %struct.A* @Constructor_A(%struct.A* nonnull %2)    %4 = bitcast i8* %1 to void (%struct.A*)***    ; чтение виртуального указателя созданного объекта типа A    ; т.к. чтение сопровождается метаданными invariant.group    ; для указателя регистрируется новая инвариантная группа    %5 = load void (%struct.A*)**, void (%struct.A*)*** %4, !invariant.group !{}    %6 = load void (%struct.A*)*, void (%struct.A*)** %5, !invariant.load !{}    ; косвенный вызов A::f(). После того как оптимизатор заинлайнет конструктор    ; (или сделает предположение о значение виртуального указателя, assumtion loads)    ; вызов будет девиртуализирован в прямой вызов A::f()    call void %6(%struct.A* nonnull %2)    ; placement new expression    ; создание нового указателя и    ; ассоциация его с новой инвариантной группой.    ; указатель ссылается и имеет доступ к области памяти,    ; которая была выделена ранее под объект типа A    %7 = call i8* @llvm.launder.invariant.group(i8* nonnull %1)    %8 = bitcast i8* %7 to %struct.B*    ; создание объекта типа B, вызов конструктора B    ; в конструктор передается новый указатель    ; это важно т.к. конструктор меняет значение виртуального указателя    %9 = call %struct.B* @Constructor_B(%struct.B* nonnull %8)    %10 = bitcast i8* %7 to void (%struct.B*)***    ; чтение виртуального указателя созданного объекта типа B    ; оптимизатор не сможет здесь использовать ранее загруженную таблицу для старого объекта    ; т.к. указатели принадлежат разным инвариантным группам.    %11 = load void (%struct.B*)**, void (%struct.B*)*** %10, !invariant.group !{}    %12 = load void (%struct.B*)*, void (%struct.B*)** %11, !invariant.load !{}    ; косвенный вызов B::f(). После того как оптимизатор заинлайнет конструктор    ; (или сделает предположение о значение виртуального указателя, assumtion loads)    ; вызов будет девиртуализирован в прямой вызов B::f()    call void %12(%struct.B* nonnull %8)    ret void}

Важно, что операции strip и launder возвращают псевдонимы (aliases) своих аргументов, это не дает оптимизатору выполнить неверную подстановку, но дает возможность делать предположения о значение, не позволяя подавлять существующие оптимизации. Вызовы соответствующих функций удаляются перед фазой генерации кода back-end'ом и не несут нагрузки на выполнение и размер объектного кода.

std::launder

Если посмотреть более внимательно на последний пример использования операции launder с placement new, то можно заметить, что на уровне LLVM IR, указатель b это не что иное, как launder(a). И семантика выражения размещающего new сводится к следующему:

1. Запрос нового указателя вызовом функции @llvm.launder.invariant.group на основе переданного аргумента.
2. Создание нового объекта в заданной области памяти: вызов конструктора. В нашем случае переиспользование памяти завершает время жизни, существующего в переданной области памяти, объекта. В конструктор передается новый указатель, т.к. конструктор меняет значение виртуального указателя (та же семантика, что и при вызове конструктора базового класса). В итоге новый указатель ссылается на новый объект со своим значением виртуального указателя и ассоциирован с "чистой" (новой) инвариантной группой. Этот указатель рассматривается как результат вычисления выражения placement new.

Вернемся к коду и к уже упомянутому состоянию Undefined Behavior:

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    // определенное поведение    b->f();    // неопределенное поведение    a->f();}

На состояния Undefined Behavior можно смотреть как на компромисс, договоренность между программистом и компилятором. Это набор дополнительных правил и ограничений, позволяющий компилятору генерировать более эффективный код. В нашем случае оптимизатор эксплуатирует объектную модель C++ и описанное неопределенное поведение, что бы реализовать девиртуализацию методов. Если девиртуализация не используется, то второй вызов a->f() будет иметь ожидаемое поведение: косвенный вызов B::f(). Но с описанной моделью девиртуализации, вызов a->f() будет оптимизирован в прямой вызов A::f(). Вызов b->f() всегда имеет ожидаемой поведение, т.к. указатель учитывает состояние инварианта и не позволяет оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные в рамках вновь созданного объекта.

Операция launder позволяет правильно оперировать инвариантными группами в рамках девиртуализации. С++ дает возможность принудительно генерировать вызов операции в промежуточном представление.

Вызов std::launder это принудительная (ручная) генерация вызова функции @llvm.launder.invariant.group в IR. Точная реализация на стороне IR зависит от настройки компиляции и обрабатываемого типа. Если мы не используем описанную модель девиртуализации (флаг -fstrict-vtable-pointers) или обрабатываем не полиморфный тип, то в IR просто генерируется алиасный указатель.

Таким образом, исходя из семантики выражения placement new эти две реализации функции test генерируют один и тот же код и не приводят к неопределенному поведению:

void test(){    A *a = new A;    a->f();    new(a) B;    std::launder(a)->f();}

void test(){    A *a = new A;    a->f();    A *b = new(a) B;    b->f();}

Использование std::launder

Мотивирующий пример из стандарта:

struct X{    const int n;};void test(){    X *p = new X{1};    const int a = p->n;    X *p1 = new (p) X{2};    // определенное поведение    const int b = p1->n;    // неопределенное поведение, значение p->n может быть 1.    const int c = p->n;    // определенное поведение    const int d = std::launder(p)->n;}

Выше мы описывали, что такое заменяемый тип (transparently replaceable) в терминах объектной модели C++. После переиспользования памяти, все имена, ссылки и указатели ссылающиеся на исходный объект, станут автоматически указывать на вновь созданный объект, только если типы исходного и нового объекта являются заменяемыми.

В этом примере как и в примере с девиртуализацией неопределенное поведение обусловлено тем, что типы не являются заменяемыми, из-за наличия константных полей. Это дает возможность оптимизатору предположить, что динамический тип объекта измениться не может и значение константного поля не меняется. Поэтому значение поля n можно прочитать только один раз и заменить все дальнейшие чтения этого поля через данный указатель на прочитанное значение. Ситуация аналогичная чтению виртуального указателя. Указатели p1 или std::launder(p) должны учитывать состояние инвариантов и не позволять оптимизатору выполнить подстановку (substitution), т.е. использовать, прочитанные для исходного объекта, данные (значение a) в рамках вновь созданного.

Более абстрактно семантику std::launder можно свести к следующему:

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

Из определения этой семантики можно сделать следующие выводы:

• std::launder не оказывает ни какого эффекта, если аргумент не указывает на объект, время жизни которого закончилось, после переиспользования памяти.
• В области памяти, на который ссылается аргумент функции, должeн существовать новый объект, который переиспользует память.

Ограничения на использование ссылок и констант в таком контексте было введено еще в C++03 3.8 7. Но, на данный момент ни один из популярных компиляторов (GCC, Clang, MSVC) не эксплуатирует это неопределенное поведение. Следует отметить только компилятор IBM XL, который выполняет подобную оптимизацию константных полей, но только в ограниченных случаях:

struct A{    const int x;    int y;};// оптимизация выполняется только для static storage durationA a = { 42, 0 };void foo();int test(){    // внешняя функция, компилятор не видит определения    foo();    // чтение a.х заменяется на 42    return a.x;}

Причин, почему компиляторы не делают такую const/reference оптимизацию несколько. До введения функции std::launder избежать неопределенного поведения можно было только использовав возвращаемое значение placement new. Но, на практике, не всегда легко это сделать, например:

template <typename T>union Storage{    constexpr Storage(T &&v)        : value(std::forward<T>(v))    {}    unsigned char dummy;    T value;};template <typename T>struct SimpleOptional{    constexpr SimpleOptional(T&& v)        : storage{std::forward<T>(v)}    {}    template <typename... Args>    void emplace(Args&&... args)    {        storage.value.~T();        ::new (&storage.value) T{std::forward<Args>(args)...};    }    constexpr const T& operator*() const    {        // чтение значение может привести к неопределенному поведению        // после переиспользования памяти        return storage.value;    }private:    Storage<T> storage;};struct A{    const int x;    int y;}void test(){    SimpleOptional<A> so = A{1, 0.5f};    const int n = (*so).x;    so.emplace(2, 0.4f);    // неопределенное поведение, x может быть равен 1 или 2    const int n1 = (*so).x;}

В данном случае, чтобы избежать неопределенного поведения придется отдельно хранить результат выражения placement new.

Более интересный пример это стандартные аллокаторы. Точнее метод construct, который используя placement new, возвращает void. Такой интерфейс аллокаторов приводит к неопределенному поведению при использование стандартных контейнеров, например, std::vector с элементами содержащими константные или ссылочные поля. Заметим, что до С++11 использование таких типов в стандартных контейнерах было невозможно. С приходом C++11 и move-семантики этого ограничение не стало.

Пример использования в контейнере:

template <typename T, typename A = std::allocator<T>>class vector{public:    using allocator_traits = typename std::allocator_traits<A>;    using pointer = typename allocator_traits::pointer pointer;    ...public:    ...    void push_back(const T& value)    {        // reserve        ...        // вызов std::allocator::construct,        // использование placement new и игнорирование возвращаемого значения        allocator_traits::construct(allocator, end, value);        ++end;    }    T& operator[] (size_t i)    {        // чтение значение может приводит к неопределенному поведению        // после переиспользования памяти в случае нарушения требований         // к заменяемым типам        return begin[i];    }    ...private:    pointer begin;    pointer end;    A allocator;    size_t capacity;};struct A{    const int x;    int y;};void test(){    vector<X> c;    c.push_back(X{1});    c.clear();    c.push_back(X{2});    // неопределенное поведение    assert(c[0].x == 2);}

Использование std::launder в общем случае так же не может решить проблему с использованием стандартных аллокаторов:

...    using pointer = typename allacoter_traits::pointer pointer;...    T& operator[] (size_t i)    {        // тип pointer в общем случае может не быть указателем        // в этом случае мы не можем использовать std::launder        return std::launder(begin)[i];    }

В результате использование стандартных аллокаторов с пользовательскими типами, содержащими константные или ссылочные поля и стандартных контейнеров будет приводить к неопределенному поведению. Эта одна из причин, почему начиная с C++17 метод construct помечен как deprecated и удален в C++20. И в конечном итоге в C++20 изменили требования к заменяемым типам, убрав ограничение на наличие константных и ссылочных подобъектов в пользовательских типах данных RU007. Поэтому пример выше формально больше не приводит к неопределенному поведению.

Заключение

К счастью, стандарт языка C++ не разрабатывается в вакууме. Автор std::launder и связанных с ним изменений является также тех.лидом в Clang и одним из авторов новой модели девиртуализации. Новые требования и std::launder хорошо ложатся в архитектуру Clang, чего нельзя сказать о GCC. В GCC эта фича до сих пор носит статус экспериментальной и не во всех случаях работает правильно. Например, Bug 95349.

Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!

rotor ненавязчивый С++ акторный микрофремворк с возможностью создания иерархий супервайзеров, похожий на своих старших братьев caf и sobjectizer. В последних релизах с момента последнего анонса накопились существенные улучшения, которые хотелось бы осветить.

Общий интерфейс для таймеров (v0.10)

Таймеры сами по себе вездесущи во всех акторных фрейморках, т. к. они делают программы более надёжными. До v0.10 не было API для того, чтобы взвести таймер; это можно было сделать только посредством доступа к низлежащему движку событий (event loop) и использованию соответствующего API, разного для разных движков. Это было не очень удобно и ломало абстракции: кроме доступа к API движка, нужно было в обработчике таймера использовать низкоуровневый API rotor'а, чтобы работала доставка сообщений. Кроме того, отмена таймера также имеет свои особенности в каждом цикле событий, что захламляло ненужными деталями логику работы актора.

Начиная с v0.10 в rotor'е, можно делать что-то вроде:

namespace r = rotor;struct some_actor_t: r::actor_base_t {    void on_start() noexcept {        timer_request = start_timer(timeout, *this, &some_actor_t::on_timer);    }    void on_timer(r::request_id_t, bool cancelled) noexcept {        ...;    }    void some_method() noexcept {        ...        cancel_timer(timer_id);    }    r::request_id_t timer_id;};

Надо отметить, что к моменту завершения работы актора (shutdown_finish), все взведённые таймеры должны сработать или быть отменены, иначе это ведёт к неопределённому поведению (undefined behavior).

Поддержка отмены запросов (v0.10)

По-моему мнению, у всех сообщений в caf семантика "запрос-ответ", в то время как в sobjectizer'е все сообщения имеют обычную "отправил-и-забыл" ("fire-and-forget") семантику. rotor поддерживает оба типа, причём по-умолчанию сообщения являются "отправил-и-забыл", а "запрос-ответ" можно сделать поверх обычных сообщений.

В обоих фреймворках, caf и sobjectizer, у каждого актора есть управляемая очередь сообщений, что обозначает, что фреймворк не доставляет новое сообщение, пока предыдущее не было обработано. В противоположность этим фреймворкам, в rotor'е нет управляемой очереди сообщений, что обозначает, что актор сам должен создать свою собственную очередь и заботиться о перегрузках при необходимости. Для мгновенно обрабатываемых сообщений типа "пинг-понг" это не имеет особого значений, однако для "тяжёлых" запросов, которые в процессе своей обработки делают ввод-вывод (I/O), разница может быть существенна. Например, если актор опрашивает удалённую сторону через HTTP-запросы, нежелательно начинать новый запрос, пока предыдущий ещё не закончился. Ещё раз: сообщение не доставлено, пока предыдущее не обработано, и не важно, что за типа сообщения.

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

В rotor'е, при необходимости, надо создавать собственную очередь запросов, и, если сообщение-отмена поступает, то актор должен либо поискать в очереди и отменить его, либо, если сообщение уже обрабатывается, отменить соответствующие операции ввода-вывода, и, в конечном итоге, ответить на исходный запрос со статусом "отменено". Нужно заметить, что только сообщения-запросы могут быт отменены, т. к. у них есть внутренний идентификатор.

namespace r = rotor;namespace payload {struct pong_t {};struct ping_t {    using response_t = pong_t;};} // namespace payloadnamespace message {using ping_request_t = r::request_traits_t<payload::ping_t>::request::message_t;using ping_response_t = r::request_traits_t<payload::ping_t>::response::message_t;using ping_cancel_t = r::request_traits_t<payload::ping_t>::cancel::message_t;} // namespace messagestruct some_actor_t: r::actor_base_t {    using ping_ptr_t = r::intrusive_ptr_t<message::ping_request_t>;    void on_ping(ping_request_t& req) noexcept {        // just store request for further processing        ping_req.reset(&req);    }    void on_cancel(ping_cancel_t&) noexcept {        if (req) {            // make_error is v0.14 feature            make_response(*req, make_error(r::make_error_code(r::error_code_t::cancelled)));            req.reset();        }    }    // простейшая "очередь" из одного сообщения.    ping_ptr_t ping_req;};

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

std::thread backend/supervisor (v0.12)

Это давно ожидаемая возможность, которая делает rotor похожим на sobjectizer: в случае, когда актору нужно осуществить блокирующие операции и ему не нужен никакой цикл событий. Например, обработчик сообщений должен выполнить интенсивные вычисления на центральном процессоре.

Очевидно, что во время блокирующих операций нет возможности сработать таймерам или другим сообщениям быть доставленными. Другими словами, во время блокирующих операций актор теряет свою реактивность, так как он не может реагировать на входящие сообщения. Чтобы преодолеть это, блокирующие операции должны быть разбиты на более мелкие итеративные куски; а когда актор закончит обрабатывать текущий кусок работы, он посылает себе сообщение с номером следующего куска для обработки, и так далее, пока все части не будут обработаны. Это даст текущему потоку выполнения немного воздуха, чтобы доставить другие сообщения, выполнить код, связанный с истекшими таймерами и т.п. Например, вмето того, чтобы вычислять свёртку sha512 для всего файла размером 1TB, задание может быть разделено на вычисление свёрток помегабайтово, что сделает поток вычисления достаточно реактивным. Данный подход универсален и применим для любого актороного фреймворка.

Само собой разумеется, что целая иерархия акторов может быть запущена на std::thread бэкенде, не только один актор. Следующий нюанс, на который следует обратить внимание, это то, что rotor'у надо подсказать, какие обработчики сообщений "тяжёлые" (блокирующие), чтобы обновить таймеры после этих обработчиков. Это делается во время подписки, т.е.:

struct sha_actor_t : public r::actor_base_t {    ...    void configure(r::plugin::plugin_base_t &plugin) noexcept override {        r::actor_base_t::configure(plugin);        plugin.with_casted<r::plugin::starter_plugin_t>([&](auto &p) {            p.subscribe_actor(&sha_actor_t::on_process)->tag_io(); // важно        });    }

Полный исходный код реактивного актора, который вычисляет свёртку sha512, который реагирует на CTRL+c, доступен по ссылке.

Идентификация Акторов (v0.14)

Канонический способ идентификации актора по основной адресу (в rotor'е у актора может быть несколько адресов, аналогично как в sobjectizer'е агент может быть подписан на несколько mbox'ов). Однако, иногда желательно вывести в лог имя актора, который завершил работу, в соответствующем колбеке в его супервайзере:

struct my_supervisor_t : public r::supervisor_t {    void on_child_shutdown(actor_base_t *actor) noexcept override {        std::cout << "actor " << (void*) actor->get_address().get() << " died \n";    }}

Адрес актора динамичен и меняется при каждом запуске программы, так что эта информация почти бесполезна. Чтобы она имела смысл, актор должен напечатать свой основной адрес, где, например, в перекрытом методе on_start(). Однако, это решение не очень удобно, поэтому было решено ввести свойство std::string identity непосредственно в базовый класс actor_base_t. Таким образом, идентичность актора может быть выставлена в конструкторе или во время конфигурации плагина address_maker_plugin_t:

struct some_actor_t : public t::actor_baset_t {    void configure(r::plugin::plugin_base_t &plugin) noexcept override {        plugin.with_casted<r::plugin::address_maker_plugin_t>([&](auto &p) {            p.set_identity("my-actor-name", false);        });        ...    }};

Теперь можно выводить идентичность актора в его супервайзере:

struct my_supervisor_t : public r::supervisor_t {    void on_child_shutdown(actor_base_t *actor) noexcept override {        std::cout << actor->get_identity() << " died \n";    }}

Иногда акторы уникальны в одной программе, а иногда сосуществуют несколько экземпляров одного и того же класса акторов. Чтобы различать между их, адрес каждого может быть добавлен к имени актора. В этом и смысл второго параметра bool в методе set_identity(name, append_addr) выше.

По умолчанию идентичность актора равна чему-то вроде actor 0x7fd918016d70 или supervisor 0x7fd218016d70. Эта возможность появилась в rotor'е начиная с версии v0.14.

Extended Error вместо std::error_code, shutdown reason (v0.14)

Когда случается что-то непредвиденное в процессе обработки запроса, до версии v0.14, ответ содержал код ошибки в виде std::error_code. Такой подход хорошо служил своей цели, но, ввиду, иерархичной природы rotor'а, этого оказалось не достаточно. Представим себе случай: супервыйзер запускает двух акторов, и у одного из них произошёл сбой в инициализации. Супервайзер экскалирует проблему, т. е. выключается сам и шлёт запрос на выключение второму актору. Однако, на момент, когда второй актор выключился, исходный контекст уже был потерян, и совершенно неясно, почему он выключился. А причина кроется в том, что std::error_code не содержит в себе достаточно информации.

Поэтому было решено ввести собственный класс расширенной ошибки rotor::extended_error_t, который содержит std::error_code, std::string в качестве контекста (обычно это идентичность актора), а также умный указатель на следующую расширенную ошибку, что вызвала текущую. Теперь схлопывание иерархии акторов может быть представлено цепочкой расширенных ошибок, где причина выключения каждого актора может быть отслежена:

struct my_supervisor_t : public r::supervisor_t {    void on_child_shutdown(actor_base_t *actor) noexcept override {        std::cout << actor->get_identity() << " died, reason :: " << actor->get_shutdown_reason()->message();    }}

выведет что-то вроде:

actor-2 due to supervisor shutdown has been requested by supervisor <- actor-1 due initialization failed

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

Содержание

• Что такое boost.compute
• Проблемы с подключением boost.compute к проекту
• Введение в boost.compute
• Основные классы compute
• Приступаем к работе
• Заключение

Что такое boost.compute

Проблемы с подключением boost.compute к проекту

Введение в boost.compute

#include <boost/compute.hpp>using namespace boost;

std::vector<float> std_vector(10);compute::vector<float> compute_vector(std_vector.begin(), std_vector.end(), queue); // пока не обращайте внимания на третий аргумент, к нему мы вернёмся позже.

compute::copy(compute_vector.begin(), compute_vector.end(), std_vector.begin(), queue);

Основные классы compute

• compute::device (будет определять с каким именно устройством мы будем работать)
• compute::context (объект данного класса хранит в себе ресурсы OpenCL, включая буферы памяти и другие объекты)
• compute::command_queue (предоставляет интерфейс для взаимодействия с вычислительным устройством)

auto device = compute::system::default_device(); // устройство по умолчанию это видеокартаauto context = compute::context::context(device); // обычное объявление переменнойauto queue = compute::command_queue(context, device); // аналогично к предыдущему

std::cout << device.name() << std::endl; 

Приступаем к работе

std::vector<float> host_vec = {1, 4, 9};compute::vector<float> com_vec(host_vec.begin(), host_vec.end(), queue);// передавая в аргументы начальный и конечный указатель предыдущего вектора можно не//использовать функцию copy()compute::vector<float> buff_result(host_vec.size(), context);transform(com_vec.begin(), com_vec.end(), buff_result.begin(), compute::sqrt<float>(), queue);std::vector<float> transform_result(host_vec.size());compute::copy(buff_result.begin(), buff_result.end(), transform_result.begin(), queue);cout << "Transforming result: ";for (size_t i = 0; i < transform_result.size(); i++){cout << transform_result[i] << " ";}cout << endl;float reduce_result;compute::reduce(com_vec.begin(), com_vec.end(), &reduce_result, compute::plus<float>(),queue);cout << "Reducing result: " << reduce_result << endl;

transform(com_vec.begin(),    com_vec.end(),    buff_result.begin(),    compute::sqrt<float>(),    queue);

compute::reduce(com_vec.begin(),    com_vec.end(),    &reduce_result,    compute::plus<float>(),   queue);

Заключение

Ассоциативные контейнеры в C++ работают с конкретным типом ключа. Для поиска в них по ключу подобного типа (std::string, std::string_view, const char*) мы можем нести существенные потери в производительности. В этой статье я расскажу как этого избежать с помощью относительно недавно добавленной возможности гетерогенного поиска.

Имея контейнер std::map<std::string, int> с мы должны быть проинформированны о возможной высокой цене при поиске (и некоторых других операциях с ключом в виде параметра) по нему в стиле c.find("hello world"). Дело в том, что по умолчанию все эти операции требуют ключ требуемого типа, в нашем случае это std::string. В результате чего при вызове find нам нужно неявно сконструировать ключ типа std::string из const char*, что будет стоить нам в лучшем случае одного лишнего memcpy (если в нашей реализации стандартной библиотеки есть "small string optimization" и ключ короткий), а также лишнего strlen (если компилятор не догадается или не будет иметь возможности вычислить длину строки во время компиляции). В худшем же случае придётся заплатить по полной: выделением и освобождением памяти из кучи для временного ключа на ровном, казалось бы, месте, а это уже может быть сопоставимо с самим временем поиска.

Мы можем избежать ненужной работы с помощью гетерогенного поиска. Функции для его корректной работы добавлены в упорядоченные контейнеры (set, multiset, map, multimap) во всех подобных местах с С++14 стандарта и в неупорядоченные (unordered_set, unordered_multiset, unordered_map, unordered_multimap) с C++20.

// до C++14 мы имели только такие функции поискаiterator find(const Key& key);const_iterator find(const Key& key) const;// начиная с C++14 мы имеем ещё и вот такиеtemplate < class K > iterator find(const K& x);template < class K > const_iterator find(const K& x) const;

Но, как и всегда, в C++ в этом месте есть подвох, имя ему дефолтный компаратор. Компаратор по умолчанию для нашего std::map<std::string, int> это std::less<std::string> функция сравнения которого объявлена как:

// где T это тип нашего ключа, т.е. std::stringbool operator()(const T& lhs, const T& rhs) const;

Он не может быть использован для нашего гетерогенного сравнения, так как имеет всё такие же проблемы (нужно конструировать конкретный тип ключа). На помощь приходит специализация std::less<void> которая лишена этих проблем.

template <>struct less<void> {    using is_transparent = void;    template < class T, class U >    bool operator()(T&& t, U&& u) const {        return std::forward<T>(t) < std::forward<U>(u);    }};

Примерно так выглядит эта специализация, я упустил моменты с constexpr и noexcept для простоты описания.

Пометка is_transparent говорит контейнерам, что этот компаратор умеет гетерогенное сравнение и по ней же становятся доступны новые функции гетерогенного поиска.

Теперь можно объявить контейнер, который будет использовать всё это добро:

std::map<std::string, int, std::less<>> c;

Естественно, можно написать и свой компаратор для своих типов, например, когда отсутствует глобальный operator< для них. Иногда мы просто не можем создать такой временный ключ прозрачно и гетерогенный поиск единственная возможность искать что-то в контейнерах по ключу, например, при хранении std::thread в std::set и поиску по std::thread::id.

struct thread_compare {    using is_transparent = void;    bool operator()(const std::thread& a, const std::thread& b) const {        return a.get_id() < b.get_id();    }    bool operator()(const std::thread& a, std::thread::id b) const {        return a.get_id() < b;    }    bool operator()(std::thread::id a, const std::thread& b) const {        return a < b.get_id();    }};// объявляем контейнер с нашим гетерогенным компараторомstd::set<std::thread, thread_compare> threads;// имеем возможность искать по idthreads.find(std::this_thread::get_id());

Ну и не стоит забывать, что это всё касается не только функции find. Так же это касается функций: count, equal_range, lower_bound, upper_bound и contains.

Счастливого гетерогенного поиска, уважаемый хаброчитатель!