Pull to refresh

Comments 64

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

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


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, и даже, простигосподи, полиморфные объекты в коде свидетельствуют о "плохой архитектуре".

Не могу понять при чем здесь порядок вычисления в динамике функций без повторений и динамический неоднородный плотно упакованный контейнер? Вы пишете код, в котором присутствуют ветвления (if конструкция), возможно циклы возможно еще что то в динамике, после чего результат передаете в функцию d.

Этих функций сотни. Какие именно будут выполняться — заранее неизвестно.
Предложите "хорошую" архитектуру.


Варианты "позвать пару ифчиков" по очевидным причинам не канают.

Тогда по каким критериям у вас вызываются сотни функций и без «ифчиков»? Вызов этих функций и вся бизнес логика которая их вызывает собственно похоже ни как не влияет на способ хранения информации как видно из коментария выше. И у вас контейнер компайл — тайм, это значит что и флоу бизнес логики тоже компайл тайм.

У меня куча вычислений. Я знаю входные аргументы и выход каждого.


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


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


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

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

Я хотел начать статью с этого примера, но быстро выяснилось, что тогда статья будет о примере, а не о структуре данных.

И да, использование boost::any свидетельствует о плохой или не продуманной архитектуре. Необходимо использовать boost с умом, и в любых даже самых хороших фреймворках и библиотеках разработчики будут добавлять механизмы для того чтобы в плохо продуманную архитектуру можно было вставлять костыли и не рушить её совсем. До сих пор не могу придумать use case-а по использованиею так же boost::variant или boost::any.

Пожалуйста, обоснуйте утверждение "использование boost::any свидетельствует о плохой или не продуманной архитектуре".

До сих пор не могу придумать use case-а по использованиею так же boost::variant или boost::any.

Да, вот интересен мне use case в продакшене, а не в каком либо тестовом или академическом коде.

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


Ещё раз.
Атеист не должен доказывать верующему отсутствие бога.
Вы выдвинули утверждение. Обойснуйте его, пожалуйста.

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

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

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

Вернее, так: на этапе компиляции известно только всё множество F доступных мне функций и, соответственно, множество R типов результатов этих функций.


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

Да, вот интересен мне use case в продакшене, а не в каком либо тестовом или академическом коде.

Например Variant активно используется в Qt. В том же самом Model-View программировании.
UFO just landed and posted this here
Нужно распарсить json. На выходе получаем древовидную структуру, где элемент может быть числом, строкой, массивом или объектом которые опять могут содержать массивы, объекты и тд. Вот этот самый элемент можно сделать boost variant
не надо далеко ходить, обработка и реконструкция экспериментальных данных. Когда необходимо работать с коллекциями и векторами совершенно разных типов с совершенно разными атрибутами (времена, размеры...) и т.д.

Мы, конечно, по старинке городим кучумалу по первому варианту, надо будет попробовать всё таки boost.
В общем-то любая одноуровневая объектная иерархия может быть заменена простым типом-суммой (см. про алгебраические типы), причём более эффективно и с меньшим количеством бойлерплейта. boost::variant – это наиболее точная их имитация-реализация, которую только можно изобразить на C++.
Делает ли то же самое модификатор constexpr из нового для многих стандарта c++0x?

Не понял вопроса. Что — "то же самое"?

Этот модификатор всего лишь вычисляет то, что можно вычислить на уровне компиляции без динамически пришедших данных, т.е. константы.
Супер! У меня точно такая же задача возникла, но я решал через абстрактный тип Result, а результаты вычислений храню в cuckoo_map<Key,unique_ptr>, получается, конечно не так производительно :(. Перешел бы на ваш контейнер, но мне нужен параллельный доступ, т.к. вычисления сильно многопоточные, потому пользуюсь libcuckoo.

Что вы понимаете под параллельным доступом?

Concurrent: операции вставки, чтения и удаления элементов из контейнера должны быть потокобезопасными, что бы результат вычислений мог быть прочитан/сохранён прямо из потока вычисления. Конечно, любой контейнер можно сделать concurrent, если добавить lock, но тогда производительность хуже, чем у однопоточного кода. Libcuckoo обеспечивает производительность на уровне std::unordered_map на каждый поток. Я когда-то сравнивал cuckoohash_map с lock-free (libcds) контейнерами — libcuckoo выиграла с отрывом по производительности и удобству использования.

Посмотрел libcuckoo.


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


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


Но это будет уже совершенно другая структура данных.
А вообще, идея интересная...

Всё верно. Я имел ввиду, что, как Вы и отметили, любой контейнер можно превратить в неоднородный с помощью полиморфного Result и
hashmap<Key,unique_ptr <Result> >

именно этот вариант я для себя и выбрал. Но, если контейнер при этом ещё и последовательный, — вообще отлично, производительность задаром не помешает.
«Пример use case-а из жизни»
Автонавигация VDO Dayton — именно таким образом хранятся данные карт и навигации.
Каким образом хранятся там? boost::variant? boost::any? Или все же структуры данных. Прошу не путать назначения типов.
Как реализовано в исходниках — сие мне не известно.
Формат закрытый, нигде не описываемый, инструментарий для работы с данными есть только у производителя.
Именно поэтому карты для этой навигации практически все только официальные, по платной ежегодной подписке.

Сами же данные карт и навигации — один сплошной файл, по структуре разбит на 2к блоки. Логический блок — несколько 2к блоков после первого, в заголовке которого явно указывается их число. Сами данные атомарно хранятся в невыровненном виде. Например, самые первые 3 байта в первом логическом 2к блоке — его адрес-смещение, следующий байт — размер логического блока. Далее насколько помню байт признака-ключа шифрования данных, байт типа блока и т.д.
00 00 02 03 — блок со смещением 2*2048, размером 3*2048 байт.
Структура данных 2к внутри зависит от типа блока, но сделана явно в полиморфных наследуемых структурах. Матрешки, в которых так же описывается размер содержимого.

Если ставить задачу чтения такого, без описываемых динамических неоднородных контейнеров обойтись можно и несложно.
Если поставить задачу компиляции таких данных, из OSM, например, то мне предлагаемый подход нравится настолько, что я статью себе в избранное занес.
Эх, где вы были пару лет назад?!!! Пришлось городить свои костыли. А так вещь нужная — мне потребовалсь для того чтобы сделать Entity-Component-System. вот для того чтобы в Entity хранить массив разнородных компонентов это решение в самый раз.
где вы были пару лет назад?

Шифровался!

Кстати есть мнение, что компоненты лучше хранить отдельно, каждый тип в однородном контейнере, а из entity ссылаться на содержащиеся в ней компоненты по id/индексам.

А можно как то получить тип (std::type_index) из вашего dynamic_tuple по индексу? Ну то-есть получить элемент по индексу, а потом в зависимости от его типа по своему обработать (как с std::vector< std::variant<...> >).

А можно как то получить тип (std::type_index) из вашего dynamic_tuple по индексу?

Легко. Нужно только написать код :) .


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

А можете привести участок кода где вы его используете как есть? Мне не понятно как можно получать 150 000й элемент массива и при этом наперёд знать его тип.

Физически тип элемента в контейнере определяет только ф-ция manager.
можно предположить 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 — наверное подойдет как есть.

Набор хранимых типов заранее неизвестен. Именно поэтому я и говорю, что ДК — это развитие идеи с any.

1. Не увидел упоминания memory alignment. Если этот аспект пропущен, то можно неожиданно получить серьезный удар по производительности.
2. Какие преимущества использования набора указателей на ф-ции (manager_t) перед виртуальными классами? На мой взгляд, именно для этого классы идеально и подходят.
Не увидел упоминания memory alignment

Очень странно. Я два раза упоминал про выравнивание.
А сам код есть в файле, на который я дал ссылку в конце статьи.


Какие преимущества использования набора указателей на ф-ции (manager_t) перед виртуальными классами?

  1. Очевидно, отсутствие лишнего уровня косвенности. Вы же понимаете, как происходят виртуальные вызовы в языке C++?


  2. Отсутствие аллокаций.
    Указатель на функцию глобален. А для класса нужно выделять память. Более того, это позволяет в процессе доступа проводить тривиальную проверку на то, что объект, который мы пытаемся достать, действительно имеет требуемый тип.
Выравнивание я просто сначала не заметил. Все ок.

Насчет уровня косвенности — спорно. В вашей реализации — вызов ф-ции по указателю (manage) + switch. Вызов виртуальной ф-ции = вызов ф-ции по указателю на указатель. Не думаю, что можно без замеров утверждать что будет быстрее в реальной жизни.
Не вижу, откуда взяться дополнительным аллокациям. Размер объекта без полей, реализующего виртуальный интерфейс, равен (surprise!) размеру manager_t. Размещающий new позволит отлично обойтись без доп. аллокаций.
Не думаю, что можно без замеров утверждать что будет быстрее в реальной жизни

Во-первых, разумеется, замеры я проводил.
Более того, первый вариант у меня был как раз на виртуальных вызовах. Потом я попробовал вариант со структурой с указателями, и всё стало "летать".


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


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


Не вижу, откуда взяться дополнительным аллокациям

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


Размещающий new позволит отлично обойтись без доп. аллокаций

Вы предлагаете ещё и обработчиками вручную управлять?
И это только ради того, чтобы написать побольше кода, который ещё и работать будет медленнее?




Итак, имеющиеся варианты:


  1. Много кода и медленная программа.
  2. Мало кода и быстрая программа.

Нелёгкий выбор ждёт нас.

Совершенно бессмысленный shared_ptr в версии с виртуальными вызовами, конечно, подрывает доверие к вашей оценке.

Механизм управления временем жизни указателя не влияет на доступ к элементу, на который он указывает.


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

Вот исходник тестового примера (замеры времени Windows-only).
Я слишком спешу сейчас, чтобы проанализировать подробно, но на первый взгляд виртуальные ф-ции убедительно выигрывают на VS2015 x86 и x64.

Вы не то замерили.
Обработчиков много, а не один. Куча обращений к одному и тому же объекту замечательно кешируется. А вот когда их много и они разбросаны по памяти — это совершенно другая ситуация.


Но.
Вы меня натолкнули на интересную мысль как можно одновременно:


  1. Ещё сильнее всё ускорить.
  2. Сделать красивые вызовы без обобщённой сигнатуры.

Напишу попозже.

Мастер дискуссии уровня Бог:
А: Виртуальный вызов дольше прямого!
В: Вот замеры. В вашем случае (с switch) наоборот.
А: Так вы меряли на каком-то необычном процессоре с кэшами и предсказаниями переходов! На моей воображаемой системе без этих бесовских ухищрений все как я сказал. И вообще у меня голова разболелась.

В общем, мысль моя не оправдалась, улучшить не удалось.


Тем не менее, я ради интереса померил производительность обработчиков на живом ДК размера от 10 до 1000 элементов.


Вывод: чем меньше элементов в контейнере, тем меньше разница между указателем на функцию (УФ) и полиморфными объектами (ПО).


  • 10 элементов:


    УФ: 2.9 попугаев.
    ПО: 5.7 попугаев.


    Разница в ~2 раза.


  • 100 элементов:


    УФ: 0.8 попугаев
    ПО: 3.5 попугаев.


    Разница в ~4 раза.


  • 1000 элементов:


    УФ: 0.29 попугаев.
    ПО: 2.9 попугаев


    Разница на порядок.



Структуру с указателями на функцию тоже мерил, результат практически идентичен УФ, но даже немного медленнее.


Дальнейшее обсуждение этой темы считаю нецелесообразным.

И shared_ptr там, естественно, не бессмысленный.


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

А правильно ли я понимаю, что ваш контейнер будет работать только на x86 архитектуре, где пофигу на выравнивание. Иначе, я не вижу где выравнивается адрес начала объекта? Попробую пояснить:
Допустим data_size() = 0. sizeof(uint8_t) = 1. Кладем в кортеж байт. sizeof(uint32_t)=4. При попытке положить целое его начало уже не будет выравнено, т.к. адрес будет data_size() + 1.
Да, похоже выравнивание есть. Просто сбил с толку термин — «плотная» упаковка. Всегда думал что плотно можно упаковать только по-байтово, наподобие сериализации.

А почему нельзя было вместо структуры использовать union? Удобство варианта со структурами (для каждой функции своя сигнатура) и потребление памяти, как у обощенного варианта.

Поясните, пожалуйста, ваш вариант.


Объединение в каждый момент времени хранит только одно значение. Значит, в нём будет лежать какой-то один обработчик. А мне требуется иметь одновременно все обработчики для каждого объекта в ДК.


Или я что-то упускаю?

UFO just landed and posted this here
Своих данных у меня нет, но случайный результат с первой страницы гугла, говорит, что это верно скорее для новых серий Intel. А современная библиотека, конечно, должна быть готова и на ARM работать.
Sign up to leave a comment.

Articles