Comments 64
Представьте, что у вас есть большое количество функций, которые друг от друга зависят. Зависимость заключается в том, что для каждой функции на этапе компиляции известно, результаты каких других функций требуются для вычисления этой функции. К примеру, для функций
int a ();
double b ();
bool c (int, double);
char d (int, bool);
известно, что функция c
вычисляется именно по тем данным, которые возвращают функции a
и b
, а функция d
вычисляется по результатам функций a
и c
(именно этих конкретных функций, а не любых функций, возвращающих нужный тип).
Эти зависимости можно изобразить в виде графа:
Теперь представьте, что таких функций очень много и между ними куча зависимостей (но без циклов, разумеется), так что граф получается достаточно большим и сложным.
Далее, в динамике — во время исполнения программы — поступает информация о том, что нужно вычислить некоторое — заранее неизвестное — подмножество этих функций. При этом требуется избежать повторных вычислений. В примере выше функции c
и d
обе зависят от результата функции a
, но функция a
должна быть вычислена только один раз.
Допустим, нужно вычислить значение функции d
. Это значит, что нужно собрать весь граф, ведущий к d
, произвести все промежуточные вычисления (а нашем примере для вычисления функции d
требуется вычислить и a
, и b
, и c
) в правильном порядке и без повторений, а затем передать полученные результаты в функцию d
, чтобы получить искомый результат.
А поскольку обращения на чтение и запись результатов промежуточных вычислений может быть очень много, желательно положить их радом, чтобы они почаще попадали в строчку кэша.
В свою очередь, прошу обосновать утверждение "если необходимы такие конструкции это прежде всего говорит о плохой архитектуре приложения".
А то получается, что и boost::variant
, и boost::any
, и даже, простигосподи, полиморфные объекты в коде свидетельствуют о "плохой архитектуре".
Этих функций сотни. Какие именно будут выполняться — заранее неизвестно.
Предложите "хорошую" архитектуру.
Варианты "позвать пару ифчиков" по очевидным причинам не канают.
У меня куча вычислений. Я знаю входные аргументы и выход каждого.
Во время исполнения мне приходит информация о том, что нужно посчитать. Промежуточные вычисления могут повторяться, поэтому нужно где-то запоминать результаты всех вычислений, чтобы не производить их заново каждый раз.
Для этого я топологически сортирую граф вычислений, в результате чего чётко определяется порядок вычислений. И в соответствии с этим порядком я и завожу динамический кортеж для хранения результатов. А поскольку обращений к результатам может быть очень много, я хочу положить их максимально близко друг к другу, чтобы было меньше промахов кэша.
Итак, получается, что я знаю типы, которые мне нужны, но не знаю места, где они лежат. В результате и получается контейнер, к которому можно обратиться по индексу в динамике, но взять оттуда заранее известный тип.
Пожалуйста, обоснуйте утверждение "использование boost::any свидетельствует о плохой или не продуманной архитектуре".
До сих пор не могу придумать use case-а по использованиею так же boost::variant или boost::any.
Да, вот интересен мне use case в продакшене, а не в каком либо тестовом или академическом коде.
То, что лично вам что-либо не понадобилось, не значит, что это не нужно. Например, если пользоваться ассоциативными массивами размером не более 10 элементов, то даже std::map
прекрасно подойдёт. Но это не повод говорить, что использование хеш-таблицы свидетельствует о плохой архитектуре.
Ещё раз.
Атеист не должен доказывать верующему отсутствие бога.
Вы выдвинули утверждение. Обойснуйте его, пожалуйста.
На этапе компиляции известны только типы значений, которые я хочу туда класть или доставать. Но места, на которых лежат эти значения, выясняются только во время исполнения.
Вернее, так: на этапе компиляции известно только всё множество F
доступных мне функций и, соответственно, множество R
типов результатов этих функций.
На этапе исполнения выясняется подмножество функций, которые мне нужно вычислить, F
0
, и соответствующее подмножество их результатов R
0
, а также места, на которых будут лежать эти результаты в моём динамическом кортеже.
Да, вот интересен мне use case в продакшене, а не в каком либо тестовом или академическом коде.
Например Variant активно используется в Qt. В том же самом Model-View программировании.
Мы, конечно, по старинке городим кучумалу по первому варианту, надо будет попробовать всё таки boost.
Result
, а результаты вычислений храню в cuckoo_map<Key,unique_ptr>, получается, конечно не так производительно :(. Перешел бы на ваш контейнер, но мне нужен параллельный доступ, т.к. вычисления сильно многопоточные, потому пользуюсь libcuckoo.
Что вы понимаете под параллельным доступом?
std::unordered_map
на каждый поток. Я когда-то сравнивал cuckoohash_map
с lock-free (libcds) контейнерами — libcuckoo выиграла с отрывом по производительности и удобству использования.Посмотрел libcuckoo
.
В общем-то, я совершенно иную задачу решал. Я хотел создать, в терминах статьи, динамический неоднородный плотный контейнер, причём последовательный.
А у них — ассоциативный контейнер (хеш-таблица), да ещё и оптимизированный для многопоточного доступа.
Наверное, можно сделать неоднородную хеш-таблицу. Возможно, можно даже сделать её плотной и многопоточной.
Но это будет уже совершенно другая структура данных.
А вообще, идея интересная...
Result
иhashmap<Key,unique_ptr <Result> >
именно этот вариант я для себя и выбрал. Но, если контейнер при этом ещё и последовательный, — вообще отлично, производительность задаром не помешает.
Автонавигация VDO Dayton — именно таким образом хранятся данные карт и навигации.
Формат закрытый, нигде не описываемый, инструментарий для работы с данными есть только у производителя.
Именно поэтому карты для этой навигации практически все только официальные, по платной ежегодной подписке.
Сами же данные карт и навигации — один сплошной файл, по структуре разбит на 2к блоки. Логический блок — несколько 2к блоков после первого, в заголовке которого явно указывается их число. Сами данные атомарно хранятся в невыровненном виде. Например, самые первые 3 байта в первом логическом 2к блоке — его адрес-смещение, следующий байт — размер логического блока. Далее насколько помню байт признака-ключа шифрования данных, байт типа блока и т.д.
00 00 02 03 — блок со смещением 2*2048, размером 3*2048 байт.
Структура данных 2к внутри зависит от типа блока, но сделана явно в полиморфных наследуемых структурах. Матрешки, в которых так же описывается размер содержимого.
Если ставить задачу чтения такого, без описываемых динамических неоднородных контейнеров обойтись можно и несложно.
Если поставить задачу компиляции таких данных, из OSM, например, то мне предлагаемый подход нравится настолько, что я статью себе в избранное занес.
А можно как то получить тип (std::type_index
) из вашего dynamic_tuple по индексу? Ну то-есть получить элемент по индексу, а потом в зависимости от его типа по своему обработать (как с std::vector< std::variant<...> >
).
А можно как то получить тип (std::type_index) из вашего dynamic_tuple по индексу?
Легко. Нужно только написать код :) .
На самом деле, это делается элементарно, просто у меня банально пока не было в этом интереса.
Поставил себе задачку.
А можете привести участок кода где вы его используете как есть? Мне не понятно как можно получать 150 000й элемент массива и при этом наперёд знать его тип.
К сожалению, не могу. Попробуйте представить его при реализации примера, описанного выше: https://habrahabr.ru/post/302372/#comment_9640418
можно предположить 2 сценария:
1. в operation_t добавить type (цена — виртуальный вызов, уже сделано)
2. сравнивать текущий manager с заданным. Например,
bool is_type<T>(int index) { return m_objects[index].manager == &management::manage<T>; }
второй вариант быстрый, но даёт только бинарный ответ.
Всё так.
Только я бы не стал называть первый сценарий виртуальным вызовом.
А второй сценарий у меня тоже используется, только не для индикации типа, а для проверки типа при доступе: https://github.com/izvolov/burst/commit/af23c847e63c0b4cc8119e6978728e245cfeaab2
Возможно. Единственное но, std::type_index занимает 8 байт. Если набор хранимых типов заранее известен, то можно тип хранить в unsigned char. Разница становится ощутимой если хранить что то вроде std::optional (даже в обычном std::vector). Если же хранить как any — наверное подойдет как есть.
2. Какие преимущества использования набора указателей на ф-ции (manager_t) перед виртуальными классами? На мой взгляд, именно для этого классы идеально и подходят.
Не увидел упоминания memory alignment
Очень странно. Я два раза упоминал про выравнивание.
А сам код есть в файле, на который я дал ссылку в конце статьи.
Какие преимущества использования набора указателей на ф-ции (manager_t) перед виртуальными классами?
Очевидно, отсутствие лишнего уровня косвенности. Вы же понимаете, как происходят виртуальные вызовы в языке C++?
- Отсутствие аллокаций.
Указатель на функцию глобален. А для класса нужно выделять память. Более того, это позволяет в процессе доступа проводить тривиальную проверку на то, что объект, который мы пытаемся достать, действительно имеет требуемый тип.
Насчет уровня косвенности — спорно. В вашей реализации — вызов ф-ции по указателю (manage) + switch. Вызов виртуальной ф-ции = вызов ф-ции по указателю на указатель. Не думаю, что можно без замеров утверждать что будет быстрее в реальной жизни.
Не вижу, откуда взяться дополнительным аллокациям. Размер объекта без полей, реализующего виртуальный интерфейс, равен (surprise!) размеру manager_t. Размещающий new позволит отлично обойтись без доп. аллокаций.
Не думаю, что можно без замеров утверждать что будет быстрее в реальной жизни
Во-первых, разумеется, замеры я проводил.
Более того, первый вариант у меня был как раз на виртуальных вызовах. Потом я попробовал вариант со структурой с указателями, и всё стало "летать".
Вот уже между структурой и обобщённым обработчиком заметной разницы в скорости нет. Но структура, очевидно, занимает больше места. Поэтому окончательный выбор пал именно на обобщённый вариант.
Я не ставил своей целью рассказать про каждую мелочь, с которой я сталкивался в процессе разработки. И уж тем более не могу привести каждый замер, который я когда-либо производил.
Не вижу, откуда взяться дополнительным аллокациям
Нам нужно завести массив указателей на классы-обработчики. А сколько они занимают памяти — в данном случае не важно, потому что память под каждый из них будет выделяться в куче.
Размещающий new позволит отлично обойтись без доп. аллокаций
Вы предлагаете ещё и обработчиками вручную управлять?
И это только ради того, чтобы написать побольше кода, который ещё и работать будет медленнее?
Итак, имеющиеся варианты:
- Много кода и медленная программа.
- Мало кода и быстрая программа.
Нелёгкий выбор ждёт нас.
Механизм управления временем жизни указателя не влияет на доступ к элементу, на который он указывает.
Вообще, мне казалось очевидным, что виртуальный вызов дольше прямого.
Будет великолепно, если вы сделаете свои, хорошие, правильные замеры и покажете их обществу. Если я окажусь неправ, то я публично покаюсь.
Вы не то замерили.
Обработчиков много, а не один. Куча обращений к одному и тому же объекту замечательно кешируется. А вот когда их много и они разбросаны по памяти — это совершенно другая ситуация.
Но.
Вы меня натолкнули на интересную мысль как можно одновременно:
- Ещё сильнее всё ускорить.
- Сделать красивые вызовы без обобщённой сигнатуры.
Напишу попозже.
А: Виртуальный вызов дольше прямого!
В: Вот замеры. В вашем случае (с switch) наоборот.
А: Так вы меряли на каком-то необычном процессоре с кэшами и предсказаниями переходов! На моей воображаемой системе без этих бесовских ухищрений все как я сказал. И вообще у меня голова разболелась.
В общем, мысль моя не оправдалась, улучшить не удалось.
Тем не менее, я ради интереса померил производительность обработчиков на живом ДК размера от 10 до 1000 элементов.
Вывод: чем меньше элементов в контейнере, тем меньше разница между указателем на функцию (УФ) и полиморфными объектами (ПО).
10 элементов:
УФ: 2.9 попугаев.
ПО: 5.7 попугаев.
Разница в ~2 раза.
100 элементов:
УФ: 0.8 попугаев
ПО: 3.5 попугаев.
Разница в ~4 раза.
1000 элементов:
УФ: 0.29 попугаев.
ПО: 2.9 попугаев
Разница на порядок.
Структуру с указателями на функцию тоже мерил, результат практически идентичен УФ, но даже немного медленнее.
Дальнейшее обсуждение этой темы считаю нецелесообразным.
И shared_ptr
там, естественно, не бессмысленный.
Обработчик зависит только от типа объекта, ему не важно его значение. Поэтому для того, чтобы получить обработчик объекта при копировании, не нужно его пересоздавать (и опять лезть в кучу), а нужно только скопировать указатель на него.
Допустим data_size() = 0. sizeof(uint8_t) = 1. Кладем в кортеж байт. sizeof(uint32_t)=4. При попытке положить целое его начало уже не будет выравнено, т.к. адрес будет data_size() + 1.
Послушайте, ну только что же обсуждали, что выравнивание есть.
https://github.com/izvolov/burst/blob/master/burst/container/dynamic_tuple.hpp#L335
А почему нельзя было вместо структуры использовать union? Удобство варианта со структурами (для каждой функции своя сигнатура) и потребление памяти, как у обощенного варианта.
Динамический неоднородный плотно упакованный контейнер