Выпуск ARM-процессора Apple M1 вдохновил меня на то, чтобы написать в Твиттер про опасности программирования без блокировок (lock-free). Этот твит вызвал бурную дискуссию. Обсуждение прошло довольно неплохо, учитывая то, что попытки втиснуть в рамки Твиттера обсуждениие такой сложной темы, как модели памяти центрального процессора, в принципе бессмысленны. Но у меня осталось желание немного раскрыть тему.

Этот пост задуман не только как обычная вводная статья про опасности программирования без блокировок (о которых я в последний раз писал около 15 лет назад), но и как объяснение, почему слабая модель памяти ARM ломает некоторый код, и почему этот код, вероятно, не работал изначально. Я также хочу объяснить, почему стандарт C++11 значительно улучшил ситуацию в программировании без блокировок (несмотря на возражения против противоположной точки зрения).

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

Основные проблемы программирования без блокировок лучше всего объяснять на примере паттерна производитель/потребитель, в котором не используются блокировки и поток-производитель выглядит следующим образом (псевдокод C ++ без деления на функции):

// Поток-производительData_t g_data1, g_data2, g_data3;bool g_flagg_data1 = calc1();g_data2 = calc2();g_data3 = calc3();g_flag = true; // Сигнализируем, что данные можно использовать.

А вот поток-потребитель, который извлекает и использует данные:

// Поток-потребительif (g_flag) {  DoSomething(g_data1, g_data1, g_data2, g_data3);

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

Основная проблема в том, что этот код предполагает, что данные будут записываться в три переменные g_data до флага, но этот код не может этого гарантировать. Если компилятор переставит местами инструкции записи, то флаг g_flag может получить значение true до того, как будут записаны все данные, и поток-потребитель увидит неверные значения.

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

Компиляторам разрешено переставлять местами инструкции записи, потому что есть правило as-if, которое гласит, что компилятор выполнил свою работу, если программа, которую он генерирует, ведет себя так, как если бы её не оптимизировали. Поскольку абстрактная машина C/C ++ долгое время допускала только однопоточное выполнение без внешних наблюдателей вся эта перестановка инструкций записи была правильной и разумной и использовалась десятилетиями.

Весь вопрос в том, что нужно сделать, чтобы компилятор не ломал наш красивый код? Давайте на минуточку представим себя программистом 2005 примерно года, который пытается сделать так, чтобы этот код сработал. Вот несколько не очень хороших идей:

1. Объявить g_flag как volatile. Это не позволит компилятору пропустить чтение/запись g_flag, но, к удивлению многих, не избавит от основной проблемы перестановки. Компиляторам запрещено переставлять инструкции чтения/записи volatile-переменных относительно друг друга, но разрешено переставлять их относительно обычных инструкций чтения/записи. То, что мы добавили volatile, никак не решает нашу проблему перестановок (/volatile:ms на VC ++ решает, но это нестандартное расширение языка, из-за которого код будет выполняться медленнее).
2. Если недостаточно объявить g_flag как volatile, тогда давайте попробуем объявить все четыре переменные как volatile! Тогда компилятор не сможет изменить порядок записи и наш код будет работать на некоторых компьютерах.

Оказывается, не только компиляторы любят переставлять инструкции чтения и записи. Процессоры тоже любят это делать. Не нужно путать это с out-of-order исполнением, всегда незаметным для вашего кода, к тому же на самом деле есть in-order процессоры, которые меняют порядок чтения/записи (Xbox 360), и есть out-of-order процессоры, которые в большинстве случаев не меняют местами чтение и запись (x86/x64).

Таким образом, если вы объявите все четыре переменные как volatile, вы получите код, который будет правильно исполняться только на x86/x64. И этот код потенциально неэффективен, потому что при оптимизации нельзя будет удалить никакие операции чтения/записи этих переменных, а это может привести к лишней работе (например, когда g_data1 дважды передается в DoSomething).

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

Чтобы предотвратить перестановку в x86/x64, нужно использовать компиляторный барьер памяти. Вот как это делается:

g_data1 = calc1();g_data2 = calc2();g_data3 = calc3();_ReadWriteBarrier(); // Только для VC++ и уже deprecated, но для 2005 это окей.g_flag = true; // Сигнализируем, что данные можно использовать.

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

Проблема в том, что этот код не будет работать на процессорах со слабой моделью памяти. Слабая модель памяти означает, что процессоры могут переставлять инструкции чтения и записи (для большей эффективности или простоты реализации). К таким процессорам относятся, например, процессоры с архитектурами: ARM, PowerPC, MIPS и практически все используемые сейчас процессоры, кроме x86/x64. Эту проблему решает тот же барьер памяти, но на этот раз это должна быть инструкция процессора, которая сообщает ему, что менять порядок не нужно. Что-то вроде этого:

g_data1 = calc1();g_data2 = calc2();g_data3 = calc3();MemoryBarrier(); // Дорогостоящий полный барьер памяти (full memory barrier). Только для Windows.g_flag = true; // Сигнализируем, что данные можно использовать.

Конкретная реализация MemoryBarrier зависит от процессора. На самом деле, как сказано в комментарии в коде, MemoryBarrier здесь не идеальный выбор, потому что нам просто нужен барьер между записями в память (write-write) вместо гораздо более дорогого полного барьера памяти (full memory barrier), который заставляет операции чтения ждать окончательного завершения операции записи. Но сейчас этого достаточно для наших целей.

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

#ifdef X86_OR_X64#define GenericBarrier _ReadWriteBarrier#else#define GenericBarrier MemoryBarrier#endifg_data1 = calc1();g_data2 = calc2();g_data3 = calc3();GenericBarrier(); // И почему мне пришлось самому это писать?g_flag = true; // Сигнализируем, что данные можно использовать.

Если у вас есть код 2005 приблизительно года, и он без этих барьеров памяти, то ваш код не работает и никогда не работал как надо, на всех процессорах, потому что компиляторам всегда разрешалось переставлять инструкции записи. С барьерами памяти, реализованными для разных компиляторов и платформ, ваш код будет красивым и портируемым.

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

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

// Поток-производительData_t g_data1, g_data2, g_data3;std::atomic<bool> g_flag // Обратите внимание!g_data1 = calc1();g_data2 = calc2();g_data3 = calc3();g_flag = true; // Сигнализируем, что данные можно использовать.

Небольшое изменение, которое легко не заметить. Я только изменил тип данных g_flag с bool на std :: atomic . Для компилятора это означает не игнорировать инструкции чтения и записи этой переменной (ну, в основном), не менять порядок чтения и записи между чтением и записью в эту переменную и, при необходимости, добавлять соответствующие процессорные барьеры памяти. Мы даже можем немного оптимизировать этот код:

// Поток-производительData_t g_data1, g_data2, g_data3;std::atomic<bool> g_flagg_data1 = calc1();g_data2 = calc2();g_data3 = calc3();g_flag.store(true, std::memory_order_release);

С помощью memory_order_release мы сообщаем компилятору, что именно мы делаем, чтобы он мог использовать соответствующий (менее затратный) тип инструкции барьера памяти или, наоборот, вообще не использовать барьер памяти (в случае x86/x64). Наш код теперь относительно чист и наиболее эффективен.

Теперь написать поток-потребитель очень просто. Фактически, с новым описанием g_flag исходная версия потока-потребителя теперь верна! Но мы можем ещё немного улучшить её:

// Поток-потребительif (g_flag.load(std::memory_order_acquire)) {  DoSomething(g_data1, g_data1, g_data2, g_data3);

Флаг std :: memory_order_acquire сообщает компилятору, что нам не нужен полный барьер памяти. Барьер чтения-захвата (read-acquire) гарантирует, что до g_flag нет чтения общих данных, не блокируя при этом другие перестановки.

Здесь я предоставлю читателю возможность потренироваться, и самому закончить пример так, чтобы потоки могли избежать работы вхолостую (Busy-Wait) и других проблем.

Если вы хотите научиться использовать этот подход, советую вам начать с внимательного изучения статей: Jeff Preshings introduction to lock-free programming или This is Why They Call It a Weakly-Ordered CPU. После этого подумайте, не лучше ли вам уйти в монастырь (мужской или женский). Lock-free programming это самое опасное оружие в арсенале C++ (а это о многом говорит) и применять его стоит лишь в редких случаях.

Примечание: Чтобы написать x86-эмулятор на ARM, придётся помучаться с этим подходом, потому что никогда не знаешь, в какой момент перестановка инструкций станет проблемой. Из-за этого приходится вставлять много барьеров памяти. Или можно следовать стратегии Apple, то есть добавить в CPU режим, который обеспечивает порядок доступов к памяти как в x86|x64 и включать его при эмуляции.

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

К сожалению, далеко не везде исключения можно задействовать. Во-первых, исключения не бесплатны и, во-вторых, не всякий код способен "пережить" возникновение исключений.

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

По большому счету, у нас в распоряжении есть только спецификатор noexcept. Штука полезная, конечно, но недостаточная.

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

Преамбула

В C++ есть спецификатор noexcept. Видя отметку noexcept в декларации функции/метода разработчик может понять, что вызывая эту функцию/метод исключений можно не ждать. Соответственно, используя noexcept функции/методы кода можно безопасно писать код для контекстов, в которых бросать исключения нельзя (деструкторы классов, операции swap, передаваемые в C-шный код callback-и и т.д.).

Однако, отметка noexcept хорошо видна лишь когда ты изучаешь декларации функций/методов. Но когда есть код, в котором вызывается какая-то функция/метод, то сразу не поймешь, ждать ли здесь исключений или нет. Вот, например:

void some_handler::on_read_result(    const asio::error_code & ec,    std::size_t bytes_transferred){    if(!ec)    {        m_data_size = bytes_transferred;        handle_data();    }    else    {...}}

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

Так что спецификатор noexcept решает только первую часть проблемы: позволяет понять при написании кода можно ли вызывать конкретную функцию/метод не ожидая вылета наружу исключения.

Тогда как вторая часть это убедится в том, бросает или не бросает исключения уже написанный ранее кусок кода, в котором вызываются те или иные методы. И вот тут лично мне не хватает наличия в C++ чего-то вроде noexcept-блока. Я бы хотел написать кусок кода и поместить этот кусок в noexcept-блок. Что-то типа:

void some_handler::on_read_result(    const asio::error_code & ec,    std::size_t bytes_transferred){    noexcept    {        if(!ec)        {            m_data_size = bytes_transferred;            handle_data();        }        else        {...}    }}

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

К сожалению, такого noexcept-блока в C++ пока нет. А раз нет, то приходится выкручиваться подручными средствами. Об одном таком самодельном средстве уже рассказывалось некоторое время назад. Сегодня же хочется рассказать о другом слепленном на коленке велосипеде, который несколько облегчил жизнь.

Проблема

Итак, есть недавно начатый свежий C++ проект, в котором исключения не только разрешены, но и используются для информирования о неожиданных проблемах. В этом проекте так же широко применяется механизм обратных вызовов (callback-ов).

Прежде всего это callback-и, которые выступают в роли completion-handler-ов для Asio. Выпускать исключения из таких callback-ов нельзя, т.к. Asio эти исключения не ловит и не обрабатывает. Соответственно, вылет исключения из completion-handler-а это крах приложения.

Так же есть callback-и, которые отдаются в библиотеку на чистом Си. И, соответственно, оттуда так же нельзя выбрасывать исключения.

Поэтому внутри callback-а, который отдается в Asio или в C-шную библиотеку, нужно сделать try/catch, внутри которого будут выполняться нужные приложению действия, а вот выброшенные исключения будут перехватываться:

void some_handler::on_read_result(    const asio::error_code & ec,    std::size_t bytes_transferred){    try    {        handle_read_result(ec, bytes_transferred); // Основные действия.    }    catch(...)    {        // Хотя бы просто "проглотить" исключение.    }}

Решение очевидное, но, к сожалению, ничто не мешает невнимательному (или уставшему) разработчику написать callback без try/catch и вызвать там метод handle_read_result. И компилятор тут нам ничем не поможет.

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

Решение в виде маркера can_throw

Решение было найдено в виде специального маркера can_throw, который передается аргументом во все прикладные функции/методы. Поэтому, если функция получает аргумент типа can_throw, то она может бросать исключения. А также вызывать другие функции/методы, которые получают can_throw.

Соответственно, если в каком-то callback-е нам приходится вызывать функцию/метод, которые требуют аргумента can_throw, то нам нужно позаботится о перехвате и обработке исключений.

А позаботится об этом нас заставит сам компилятор, т.к. маркер can_throw нельзя просто так создать и отдать в вызываемую функцию/метод. Т.е. мы не можем написать вот так:

void some_handler::handle_read_result(    can_throw_t can_throw,    const asio::error_code & ec,    std::size_t bytes_transferred){    ... // Прикладная обработка которая может бросать исключения.}void some_handler::on_read_result(    const asio::error_code & ec,    std::size_t bytes_transferred){    // Вот так быть не должно!    handle_read_result(can_throw_t{}, ec, bytes_transferred);}

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

class can_throw_t{    friend class exception_handling_context_t;    can_throw_t() noexcept = default;public:    ~can_throw_t() noexcept = default;    can_throw_t( const can_throw_t & ) noexcept = default;    can_throw_t( can_throw_t && ) noexcept = default;    can_throw_t &    operator=( const can_throw_t & ) noexcept = default;    can_throw_t &    operator=( can_throw_t && ) noexcept = default;};

Т.е. кто угодно может копировать и перемещать экземпляры типа can_throw_t, но вот создавать эти экземпляры "могут не только лишь все" (с). Для того, чтобы получить экземпляр can_throw_t следует сперва создать экземпляр типа exception_handling_context_t:

class exception_handling_context_t{public:    can_throw_t    make_can_throw_marker() const noexcept { return {}; }};

а затем воспользоваться методом make_can_throw_marker()

void some_handler::on_read_result(    const asio::error_code & ec,    std::size_t bytes_transferred){    try    {        exception_handling_context_t ctx;        handle_read_result(ctx.make_can_throw_marker(), ec, bytes_transferred);    }    catch(...)    {}}

Да, при этом ничто не запрещает создавать экземпляры exception_handling_context_t и без использования блоков try/catch. И можно было бы попробовать сделать более железобетонное решение. Например, функцию wrap_throwing_action, которая бы получала на вход лямбду, а внутри имела бы блок try, внутри которого бы лямбда и вызывалась. Что-то вроде:

class can_throw_t{    // Разрешаем создание can_throw только внутри    // шаблонной функции wrap_throwing_action.    template<typename Lambda>    friend void wrap_throwing_action(Lambda &&);    can_throw_t() noexcept = default;public:    ... // Все как показано выше.};template< typename Lambda >void wrap_throwing_action(Lambda && lambda){    try    {        lambda(can_throw_t{});    }    catch(...)    {}}

Можно было бы и так.

Но пока мы ограничились именно показанными выше тривиальными реализациями can_throw_t и exception_handling_context_t.

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

Отчасти потому, что какие-то функции/методы нужно вызывать не только из callback-ов, но и из конструкторов объектов. А в конструкторах исключения разрешены, посему и создавать внутри тела конструктора дополнительный try нет смысла. Гораздо проще внутри конструктора объявить временный exception_handling_context_t и вызывать нужную функцию:

some_handler::some_handler(    std::vector<std::byte> initial_data,    std::size_t initial_data_size)    : m_data{std::move(initial_data)}    , m_data_size{initial_data_size}{    exception_handling_context_t ctx;    handle_data(ctx.make_can_throw_marker());}...void some_handler::handle_read_result(    can_throw_t can_throw,    const asio::error_code & ec,    std::size_t bytes_transferred){    if(!ec)    {        m_data_size = bytes_transferred;        handle_data(can_throw);    }    else    {        ...    }}...void some_handler::handle_data(can_throw_t){    ... // Прикладная обработка данных.}

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

Общие впечатления

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

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

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

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

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

Поэтому, как минимум, два вышеозначенных момента нужно иметь в виду тем, кто захочет применить подход с маркерами can_throw в своем коде.

Заключение

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

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

Конечно же, было бы лучше иметь более продвинутые средства контроля за выбросом исключений в С++. Тогда бы не пришлось прибегать к велосипедам типа can_throw. Но пока есть лишь то, что есть :( И для повышения степени доверия к коду приходится собирать на коленке собственные велосипеды.

Стандарт С++ почти никогда не указывает, как именно должен быть реализован тот или иной 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 за замечание по статье и картинку.

Приветствую все читающих :)

О чём статья (или задача статьи): практический ответ на вопрос "возможно ли создать большой проект так, чтобы полностью отказаться от dynamic_cast на этапе выполнения?", где под большим проектом подразумевает такой в котором уже нет человека, что бы держал в голове всю кодовую базу проекта целиком.
Предварительный ответ: ДА, это возможно возможно создать механизм, позволяющий решить задачу dynamic_cast на этапе компиляции, но едва ли подобное будет применяться на практике по причинам как: (1) с самого начала целевой проект должен строиться согласно наперёд заданным правилам, в следствии чего взять и применить методику к существующему проекту, очень трудоёмко (2) существенное повышение сложности кода с точки зрения удобства его читаемости в определённых местах, где, собственно, происходит замена логики dynamic_cast на предложенную ниже (3) использование шаблонов, что может быть неприемлемым в некоторых проектах по идеологическим соображениям ответственных за него (4) интерес автора исключительно в том, чтобы дать ответ на поставленный вопрос, а не в том, чтобы создать универсальный и удобный механизм решения поставленной задачи (в конце-концов, не нужно на практике решать проблемы, которые не являются насущными).

Идея реализации

За основу была взята идея списка типов, описанная Андреем Александреску (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%B5%D1%81%D0%BA%D1%83,_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B9) и реализованная им же в библиотеке Loki (http://loki-lib.sourceforge.net/html/a00681.html). Данная идея была доработана по следующим пунктам (пункты помеченные * означают, что по данному пункту автор статьи не согласен с видением Александреску по поводу списков типов):

• добавлена возможность генерации произвольного по длине списка типов без использования макросов и/или шаблонных структур, с количеством шаблонных параметров равных длине создаваемого списка;
• добавлена возможность генерации списка типов на основе типа(ов) и/или существующего списка(ов) типов в их произвольной комбинации;
• *удалена возможность создавать списки типов элементы которых могут являться списками типов;
• *удалены функции MostDerived и DerivedToFront как и любая логика завязанная на наследовании классов, т.к. (1) логика её работы сильно зависит от порядка типов в списке типов, а потому требует бдительности от программиста при создании соответствующих списков и, что более важно, полного знания проекта программистом, который будет применять эту логику, что противоречит условиям задачи (2) распознавание наследования вниз по иерархии наследования, вообще говоря, простая задача не требующая какой-либо дополнительной логики этапа компиляции помимо уже имеющейся, тогда как автора статьи интересует в первую очередь логика распознавания наследования вверх на этапе компиляции, в чём выше обозначенные функции помочь не в силах;
• добавлены проверки через static_assert, что позволяет получать осмысленные сообщения об ошибках при компиляции списка типов, в случае возникновения таковых;
• добавлены функции как RemoveFromSize, CutFromSize позволяющие получать подсписки списков типов.
  Итоговый код библиотеки, для работы со списками типов, в полном виде вы можете посмотреть здесь (https://github.com/AlexeyPerestoronin/Cpp_TypesList), тогда как в статье будет присутствовать код, непосредственно использующий функционал данной библиотеки, необходимый для решения задачи.

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

#include <gtest/gtest.h>#include <TypesList.hpp>#include <memory>class A {    public:    using BASE_t = TL::Refine_R<TL::CreateTypesList_R<void>>;    A() {}    A(int a) {        buffer << ' ' << a;    }    virtual void F1() = 0;    protected:    std::stringstream buffer;};class B : public A {    public:    using BASE_t = TL::Refine_R<TL::CreateTypesList_R<A, A::BASE_t>>;    B() {}    B(int a, int b)        : A(a) {        buffer << ' ' << b;    }    virtual void F1() override {        std::cout << "class::B" << buffer.str() << std::endl;    }};class C : public B {    public:    using BASE_t = TL::Refine_R<TL::CreateTypesList_R<B, B::BASE_t>>;    C() {}    C(int a, int b, int c)        : B(a, b) {        buffer << ' ' << c;    }    virtual void F1() override {        std::cout << "class::C" << buffer.str() << std::endl;    }};class D : public C {    public:    using BASE_t = TL::Refine_R<TL::CreateTypesList_R<C, C::BASE_t>>;    D() {}    D(int a, int b, int c, int d)        : C(a, b, c) {        buffer << ' ' << d;    }    virtual void F1() override {        std::cout << "class::D" << buffer.str() << std::endl;    }};TEST(Check_class_bases, test) {    {        using TClass = A;        EXPECT_EQ(TClass::BASE_t::size, 1);        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));    }    {        using TClass = B;        EXPECT_EQ(TClass::BASE_t::size, 2);        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));    }    {        using TClass = C;        EXPECT_EQ(TClass::BASE_t::size, 3);        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, B>));    }    {        using TClass = D;        EXPECT_EQ(TClass::BASE_t::size, 4);        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, B>));        EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, C>));    }}// TT - Type to Typetemplate<class Type, class BASE_t>struct T2T {    std::shared_ptr<Type> value;    using PossibleTo_t = BASE_t;};template<class To, class From, class... Arguments>auto T2TMake(Arguments&&... arguments) {    T2T<To, TL::Refine_R<TL::CreateTypesList_R<From, From::BASE_t>>> result{};    result.value = std::make_shared<From>(arguments...);    return result;}template<class BASE_t>void AttemptUse(T2T<A, BASE_t> tb) {    static_assert(TL::IsInList_R<BASE_t, C>, "this function can to use only with C-derivative params");    tb.value->F1();}TEST(T2TMake, test) {    {        auto value = T2TMake<A, B>();        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 3);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        // AttemptUse(value); // compilation error    }    {        auto value = T2TMake<A, B>(1, 2);        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 3);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        // AttemptUse(value); // compilation error    }    {        auto value = T2TMake<A, C>();        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 4);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        EXPECT_TRUE((TL::IsInList_R<TClass, C>));        AttemptUse(value);    }    {        auto value = T2TMake<A, C>(1, 2, 3);        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 4);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        EXPECT_TRUE((TL::IsInList_R<TClass, C>));        AttemptUse(value);    }    {        auto value = T2TMake<A, D>();        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 5);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        EXPECT_TRUE((TL::IsInList_R<TClass, C>));        EXPECT_TRUE((TL::IsInList_R<TClass, D>));        AttemptUse(value);    }    {        auto value = T2TMake<A, D>(1, 2, 3, 4);        using TClass = decltype(value)::PossibleTo_t;        EXPECT_EQ(TClass::size, 5);        EXPECT_TRUE((TL::IsInList_R<TClass, void>));        EXPECT_TRUE((TL::IsInList_R<TClass, A>));        EXPECT_TRUE((TL::IsInList_R<TClass, B>));        EXPECT_TRUE((TL::IsInList_R<TClass, C>));        EXPECT_TRUE((TL::IsInList_R<TClass, D>));        AttemptUse(value);    }}int main(int argc, char* argv[]) {    ::testing::InitGoogleTest(&argc, argv);    return RUN_ALL_TESTS();}

1. Создание первого класса в иерархии class A

   
   

   class A {public:using BASE_t = TL::Refine_R<TL::CreateTypesList_R<void>>;A() {}A(int a) {    buffer << ' ' << a;}virtual void F1() = 0;protected:std::stringstream buffer;};
   

   
   

   class A это простой чисто-вирутуальный класс, главной особенностью которого является строка: using BASE_t = TL::Refine_R<TL::CreateTypesList_R<void>>;, которая определяет для класса список типов от которых наследуется класс.
   Здесь и далее:

   
   
   • TL::CreateTypesList_R структура, создающая список типов произвольной длинны.
   • TL::Refine_R структура, очищающая список типов от дубликатов, в случае наличия таковых.
     Т.к. класс А ни от кого не наследуется, то единственным типом к которому он может быть напрямую приведён является void.
   
   

2. Создание втрого класса в иерархии class B

   
   

   class B : public A {public:using BASE_t = TL::Refine_R<TL::CreateTypesList_R<A, A::BASE_t>>;B() {}B(int a, int b)    : A(a) {    buffer << ' ' << b;}virtual void F1() override {    std::cout << "class::B" << buffer.str() << std::endl;}};
   

   
   

   Как видим, класс В наследуется от класса А, а потому в его BASE_t списке типов к которым может быть приведёт класс В, содержится класс А и все базовые типы класса А.

   
   

3. Создание третьего класса в иерархии class C

   
   

   class C : public B {public:using BASE_t = TL::Refine_R<TL::CreateTypesList_R<B, B::BASE_t>>;C() {}C(int a, int b, int c)    : B(a, b) {    buffer << ' ' << c;}virtual void F1() override {    std::cout << "class::C" << buffer.str() << std::endl;}};
   

   
   

   Класс С, является наследником класса В, следовательно в его BASE_t содержится класс В, и все базовые типы класса В.

   
   

4. Создание четвёртого класса в иерархии class D

   
   

   class D : public C {public:using BASE_t = TL::Refine_R<TL::CreateTypesList_R<C, C::BASE_t>>;D() {}D(int a, int b, int c, int d)    : C(a, b, c) {    buffer << ' ' << d;}virtual void F1() override {    std::cout << "class::D" << buffer.str() << std::endl;}};
   

   
   

   Аналогично предыдущему классу, класс D наследуется от класса С и его BASE_t содержит класс С и все его базовые типы.

   
   
5. Проверка базовых типов классов
   Здесь и далее, структура TL::IsInList_R<TypesList, Type> возвращает true когда и только тогда, когда тип Type входит в список типов TypesList, и false в противном случае.
   

   TEST(Check_class_bases, test) {{    using TClass = A;    EXPECT_EQ(TClass::BASE_t::size, 1);    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));}{    using TClass = B;    EXPECT_EQ(TClass::BASE_t::size, 2);    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));}{    using TClass = C;    EXPECT_EQ(TClass::BASE_t::size, 3);    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, B>));}{    using TClass = D;    EXPECT_EQ(TClass::BASE_t::size, 4);    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, void>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, A>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, B>));    EXPECT_TRUE((TL::IsInList_R<TClass::BASE_t, C>));}}
   

   
   

   Как видно из фрагмента кода, каждый из созданных классов: class A, class B, class C и class D, содержит в своём BASE_t типы к которым этот класс может быть приведён вниз по иерархии наследования.

   
   Создание структуры с информацией о наследовании вверх по иерархии
   

   // T2T - Type to Typetemplate<class Type, class BASE_t>struct T2T {std::shared_ptr<Type> value;using PossibleTo_t = BASE_t;};
   

   
   

   Данная структура предназначена для хранения указателя на экземпляр value типа Type и списка типов PossibleTo_t к которым value может быть приведён, включая типы выше по иерархии от (унаследованные от) Type.

   
   Создание функции для создания структуры T2T
   

   template<class To, class From, class... Arguments>auto T2TMake(Arguments&&... arguments) {T2T<To, TL::Refine_R<TL::CreateTypesList_R<From, From::BASE_t>>> result{};result.value = std::make_shared<From>(arguments...);return result;}
   

   
   

   Шаблонные параметры функции T2TMake имеют следующее предназначение:
   

   • From истинный тип объекта, создаваемого для хранения в структуре T2T;
   • To тип под которым созданный объект хранится в структуре T2T;
   • Arguments типы аргументов для создания целевого объекта.
     Как видно, данная фукнция будет компилироваться только в случае, если тип From является наследником типа To, а запись TL::Refine_R<TL::CreateTypesList_R<From, From::BASE_t>> создаёт список типов для структуры T2T по которому в дальнейшем можно будeт однозначно определить всё множество типов к которым может быть приведён указатель на объект value.
   
   Создание функции для проверки корректности работы структуры T2T
   

   template<class BASE_t>void AttemptUse(T2T<A, BASE_t> tb) {static_assert(TL::IsInList_R<BASE_t, C>, "this function can to use only with C-derivative params");tb.value->F1();}
   

   
   

   По придуманным условиям, данная функция может работать с объектами класса А, являющимися приведёнными от объектов не ниже класса С по иерархии типов, причём, и это самое важное, данное условие проверяется ещё на этапе компиляции.

   
   Итоговое тестирование созданной логики
   

   TEST(T2TMake, test) {{    auto value = T2TMake<A, B>();    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 3);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    // AttemptUse(value); // compilation error}{    auto value = T2TMake<A, B>(1, 2);    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 3);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    // AttemptUse(value); // compilation error}{    auto value = T2TMake<A, C>();    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 4);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    EXPECT_TRUE((TL::IsInList_R<TClass, C>));    AttemptUse(value);}{    auto value = T2TMake<A, C>(1, 2, 3);    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 4);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    EXPECT_TRUE((TL::IsInList_R<TClass, C>));    AttemptUse(value);}{    auto value = T2TMake<A, D>();    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 5);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    EXPECT_TRUE((TL::IsInList_R<TClass, C>));    EXPECT_TRUE((TL::IsInList_R<TClass, D>));    AttemptUse(value);}{    auto value = T2TMake<A, D>(1, 2, 3, 4);    using TClass = decltype(value)::PossibleTo_t;    EXPECT_EQ(TClass::size, 5);    EXPECT_TRUE((TL::IsInList_R<TClass, void>));    EXPECT_TRUE((TL::IsInList_R<TClass, A>));    EXPECT_TRUE((TL::IsInList_R<TClass, B>));    EXPECT_TRUE((TL::IsInList_R<TClass, C>));    EXPECT_TRUE((TL::IsInList_R<TClass, D>));    AttemptUse(value);}}
   

   
   
   

   Выводы

   
   

   dynamic_cast на этапе компиляции это реально.
   Однако, вопрос о целесообразности остаётся насущным.

   
   

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