Можете, пожалуйста, пояснить более подробно? Я исхожу из того, что вызов функции make_person происходит из другого программного модуля, из-за чего copy elision - невозможно.
Если делать взызов этой функции из того же модуля, то и RVO и NRVO, конечно же, сработает, что верно иллюстрирует ваш пример из godbolt.
Спасибо за статью! Понимаю, что статья - для новичков. Но, говоря про подводные камни распараллеливания, хотелось бы, чтобы тема так же была рассмотрена с точки зрения инвалидации хешей, false cache sharing, и как с этим бороться.
Я очень подозреваю UB с dangling reference в специализации X::X<int>(int &&), потому что в списке инициализации X(int &&l) : val(l) член класса val (lvalue ссылка) ссылается на локальную переменную l
У меня тоже есть подобные подозрения, но полагаю, что точно выяснить как должно работать не получится. Потому что:
Теоретические методы завязаны анализе и синтезе стандарта и расплывчатой формулировки, от которой зависит истинность: the initializer expression is used to initialize the destination object
Эмпирический подход даёт разные результаты на разных компиляторах (+ вариациях оптимизаций), на основе которых сложно делать однозначные выводы.
Да и выяснять это, судя по всему, имеет смысл только в рамках теоретических изысканий, поскольку на практике этот механизм ведёт себя слишком нестабильно на разных компиляторах, чтобы его использовать.
Поэтому я рекомендую интерпретировать такой код (и его вариации), как ведущий в висячим ссылкам и UB, и выпиливать его при встрече.
Всегда можно реализовать CLI обёртку, которая будет проксировать вызовы C# <-> C++. И тогда можно будет часть функционала писать на С++, а часть на C#, пользуясь преимуществами обоих языков и при этом не переписывая всё с нуля.
Пример: часто видел как делают UI на WPF, а бизнес логику на C++.
В общем случае подойдет любая задача, в рамках которой:
Требуется реализовать отображение одного множества на другое по более чем 1 критерию.
И при этом вам не нужно(не требуется или накладно или избыточно) втаскивать только ради решения этой задачи интеграцию с БД.
осталось впечатление, что решение задачи - БД, а вот такая структура данных - какой-то странный велосипед.
В частности подойдут задачи, в рамках которых функционала обычного STL-ного контейнера уже не хватает, но трудозатратно пересесть сразу на БД. Или же если требуется что-то вроде in-memory БД, но с функционалом, который покрывает boost::multi_index::multi_index_container(т.е. как минимум без транзакционной модели из коробки).
Если говорить конкретнее, то лично мне данный контейнер пригодился в реализации:
Биржевого стакана(в оперативном контейнере заявок и в снапшоте текущего состояния стакана).
Фильтрации tcp пакетов по нескольким признакам.
Фильтрации записей при парсе файлов разных форматов.
Меня также смущает, что предложенная структура данных требует обозначить индексацию при создании контейнера, хотя из условия задачи у меня сложилось впечатление, что этот критерий динамический
Способ индексации динамический с точки зрения изменения требований, а не с точки зрения runtime исполнения кода программы. То есть в данной статье не рассматривается механизм наиболее гибкого способа выпускать и применять патчи к программе(имею ввиду ситуацию, в которой новые требования к индексации появляются и должны быть учтены в уже выпущенной версии программы, в частности во время её исполнения на машине).
Возможно я неверно понял вашу проблему про линейный поиск, но предположу, что речь про то, что не получается придумать как искать элементы в вашем самопальном индексе быстрее. Конкретно насчёт вашей реализации, в ней каждый 'индекс', это аналог ordered_unique индекса из Boost.MultiIndex. Хоть и используется std::multiset, но специфика его элементов(указателей на значения из другого контейнера) такова, что два указателя на один и тот же объект точно не попадут в этот контейнер. Поэтому, если использовать std::multiset<T>::find то можно добиться логарифмического времени поиска.
Если же хочется реализовать аналоги для всех видов индексов, то для каждого из индексов в статье я привёл в аналогию STL-ный контейнер, и именно при помощи указанного контейнера можно реализовать аналог того или иного индекса.
Но в любом случае, ограничения по скорости поиска элемента по индексу всегда будут ограничены внутренним устройством аналогичного STL-ного контейнера. Поэтому, если вы хотите более быстрого поиска, то возможно вам нужен аналог hashed_unique индекса на основе std::unordered_set, с его средним константным временем поиска (чем меньше коллизий, тем вероятнее оно будет таким).
В принципе, для себя можно было бы обойтись подобием в виде нескольких unordered_map
Вероятнее всего, решение на основе нескольких STL-ных контейнеров будет проигрывать multi_index_container как по производительности, так и по сложности поддержки и расширения функциональности. Но если мы говорим про что-то не требовательное к этим параметрам, то почему-бы и нет :)
Не до конца понял что именно вы имеете ввиду. Предположу, что вы говорите про специфику внутреннего представления ключей в multi_index_container. Если так то, судя по всему, эта специфика либо не влияет на производительность, либо же влияет недостаточно чтобы решение стало хуже эквивалента на STL-ном контейнере.
В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что multi_index_container превосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.
Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что multi_index_container превосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.
Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
Как оказалось, я действительно неверно понял механизм работы std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).
transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе operator()(Person const &, Person const &), это поле name. То есть is_transparent не решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).
Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
mscv2019 программа падает, если заменить в find(41) из примера значение 41 на 40 или 60.
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
Как оказалось, я неверно понял механизм работы std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).
transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе operator()(Person const &, Person const &), это поле name. То есть is_transparent не решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).
Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
mscv2019 программа падает, если заменить в find(41) из примера значение 41 на 40 или 60.
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
Я, возможно, понимаю о чём вы говорите, про компенсацию недостатков макросами. В моём понимании, их ещё можно компенсировать метапрограммированием. Но, с моей точки зрения, оба этих решения спорные, потому что в неумелых руках могут принести больше вреда, чем пользы. Среди рисков, использование таких механизмов языка с достаточной вероятностью может увеличить сложность разработки, отладки и может резко увеличить порог входа в решения на её основе.
Да и даже если обозначенные проблемы решаются, то всё-равно частично.
Это действительно решает почти все обозначенные проблемы. Говорю почти все потому что, чтобы применить такое решение нужно:
Использовать минимум C++14, если нужен гетерогенный поиск по упорядоченным контейнерам.
Использовать минимум С++20, если нужен гетерогенный поиск по неупорядоченным контейнерам.
Писать отдельные от объявления контейнера хэш-функции(для неупорядоченного контейнера) и компараторы(для упорядоченного), что размазывает логику по коду, тем самым затрудняя его понимание.
Ещё, если я вас верно понял, то стоит учитывать, что такое решение потребует написать намного больше кода и потребует больше ручной работы. Поскольку:
Нужно будет определять по структуре тэга с конструктором, принимающим один параметр(если только это не POD), потому что нам надо будет передавать через объект этой тэга значение ключа.
Нужно будет создавать реализацию operator() в компараторе для каждого из тегов вручную. При этом стоит учитывать, что всегда нужно по 2 реализации: когда тег - первый параметр, и когда второй.
Масштаб этой проблемы незначителен на маленьком количестве тэгов. Но на маленьком наборе и не получится проверить насколько такое решение гибкое. Если добавить много разных тегов, в т.ч. и композитных, то даже на небольшом множестве из 3 полей может получится уже до 6 структур тегов и 12 реализаций operator() для каждой структуры, и весь этот код придётся писать вручную. Соответственно, в более сложных системах всё будет более печально.
Поэтому я не считаю такое решение достаточно гибким.
Пожалуйста, ознакомьтесь с https://stackoverflow.com/questions/23777863/do-rvo-and-copy-elision-only-work-within-one-compilation-unit-or-not.
RVO возможна только в одной единице трансляции (если брать в расчёт специальные опции линковщика). Поэтому, в общем случае, RVO и NRVO при пересечении бинарной границы между разными модулями - невозможны.
Чтобы прояснить ситуацию с умными указателями, пожалуйста, ознакомьтесь с пунктом 2.2 Конструирование объекта
Можете, пожалуйста, пояснить более подробно?
Я исхожу из того, что вызов функции
make_personпроисходит из другого программного модуля, из-за чего copy elision - невозможно.Если делать взызов этой функции из того же модуля, то и RVO и NRVO, конечно же, сработает, что верно иллюстрирует ваш пример из godbolt.
Почему не происходит?Спасибо за статью! Понимаю, что статья - для новичков. Но, говоря про подводные камни распараллеливания, хотелось бы, чтобы тема так же была рассмотрена с точки зрения инвалидации хешей, false cache sharing, и как с этим бороться.
Спасибо вам за уточнения и проявленный к статье интерес!
Можете, пожалуйста, уточнить какая формулировка из п. 3.7 натолкнула на такую мысль?
Спасибо за обратную связь!
У меня тоже есть подобные подозрения, но полагаю, что точно выяснить как должно работать не получится. Потому что:
Теоретические методы завязаны анализе и синтезе стандарта и расплывчатой формулировки, от которой зависит истинность:
the initializer expression is used to initialize the destination objectЭмпирический подход даёт разные результаты на разных компиляторах (+ вариациях оптимизаций), на основе которых сложно делать однозначные выводы.
Да и выяснять это, судя по всему, имеет смысл только в рамках теоретических изысканий, поскольку на практике этот механизм ведёт себя слишком нестабильно на разных компиляторах, чтобы его использовать.
Поэтому я рекомендую интерпретировать такой код (и его вариации), как ведущий в висячим ссылкам и UB, и выпиливать его при встрече.
Спасибо, что помогаете улучшить статью! Действительно, чтобы пример заработал придётся создавать массив немного хитрее (cppinsights):
Рекомендация не использовать такой трюк из п. 3.9 в таком свете становится ещё более актуальной.
Всегда можно реализовать CLI обёртку, которая будет проксировать вызовы C# <-> C++. И тогда можно будет часть функционала писать на С++, а часть на C#, пользуясь преимуществами обоих языков и при этом не переписывая всё с нуля.
Пример: часто видел как делают UI на WPF, а бизнес логику на C++.
Спасибо за обратную связь!
В общем случае подойдет любая задача, в рамках которой:
Требуется реализовать отображение одного множества на другое по более чем 1 критерию.
И при этом вам не нужно(не требуется или накладно или избыточно) втаскивать только ради решения этой задачи интеграцию с БД.
В частности подойдут задачи, в рамках которых функционала обычного STL-ного контейнера уже не хватает, но трудозатратно пересесть сразу на БД.
Или же если требуется что-то вроде in-memory БД, но с функционалом, который покрывает
boost::multi_index::multi_index_container(т.е. как минимум без транзакционной модели из коробки).Если говорить конкретнее, то лично мне данный контейнер пригодился в реализации:
Биржевого стакана(в оперативном контейнере заявок и в снапшоте текущего состояния стакана).
Фильтрации tcp пакетов по нескольким признакам.
Фильтрации записей при парсе файлов разных форматов.
Способ индексации динамический с точки зрения изменения требований, а не с точки зрения runtime исполнения кода программы. То есть в данной статье не рассматривается механизм наиболее гибкого способа выпускать и применять патчи к программе(имею ввиду ситуацию, в которой новые требования к индексации появляются и должны быть учтены в уже выпущенной версии программы, в частности во время её исполнения на машине).
Возможно я неверно понял вашу проблему про линейный поиск, но предположу, что речь про то, что не получается придумать как искать элементы в вашем самопальном индексе быстрее. Конкретно насчёт вашей реализации, в ней каждый 'индекс', это аналог
ordered_uniqueиндекса из Boost.MultiIndex. Хоть и используетсяstd::multiset, но специфика его элементов(указателей на значения из другого контейнера) такова, что два указателя на один и тот же объект точно не попадут в этот контейнер. Поэтому, если использоватьstd::multiset<T>::findто можно добиться логарифмического времени поиска.Если же хочется реализовать аналоги для всех видов индексов, то для каждого из индексов в статье я привёл в аналогию STL-ный контейнер, и именно при помощи указанного контейнера можно реализовать аналог того или иного индекса.
Но в любом случае, ограничения по скорости поиска элемента по индексу всегда будут ограничены внутренним устройством аналогичного STL-ного контейнера. Поэтому, если вы хотите более быстрого поиска, то возможно вам нужен аналог
hashed_uniqueиндекса на основеstd::unordered_set, с его средним константным временем поиска (чем меньше коллизий, тем вероятнее оно будет таким).Вероятнее всего, решение на основе нескольких STL-ных контейнеров будет проигрывать
multi_index_containerкак по производительности, так и по сложности поддержки и расширения функциональности. Но если мы говорим про что-то не требовательное к этим параметрам, то почему-бы и нет :)Не до конца понял что именно вы имеете ввиду. Предположу, что вы говорите про специфику внутреннего представления ключей в
multi_index_container. Если так то, судя по всему, эта специфика либо не влияет на производительность, либо же влияет недостаточно чтобы решение стало хуже эквивалента на STL-ном контейнере.В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что
multi_index_containerпревосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
В сравнении производительности, предоставленном в документации Boost.MultiIndex, авторы утверждают, что
multi_index_containerпревосходит как по пространственной, так и по временной эффективности эквивалентные структуры данных, полученные через ручное комбинирование STL контейнеров. Это становится более заметно, когда количество индексов увеличивается.Если же говорить про частный случай, когда мы используем только один индекс, то производительность Boost.MultiIndex сравнима с производительностью протестированных реализаций STL и даже может привести к некоторым улучшениям как в потреблении памяти, так и во времени выполнения.
Как оказалось, я действительно неверно понял механизм работы
std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе
operator()(Person const &, Person const &), это поле name. То естьis_transparentне решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
Как оказалось, я неверно понял механизм работы
std::set<T>::is_transparent. Прошу прощения. Таким решением нельзя решить проблему [4](индексации по другим полям).transparent компаратор позволяет сравнивать только по тому полю структуры, которое используется для определения отношения порядка в контейнере. В нашем случае, в методе
operator()(Person const &, Person const &), это поле name. То естьis_transparentне решает проблему поиска по нескольким полям, а только позволяет выполнять поиск по значению, не создавая промежуточного пустого объекта Person (решает проблему [1]).Если же говорить о том, что произойдёт если попробовать сделать индексацию по нескольким полям в transparent компараторе, то @0o00oo00o0 выяснил эмпирически, что поиск по контейнеру с таким компаратором ведёт себя нестабильно и может привести к падению:
Поэтому решение на основе transparent компаратора становится не таким привлекательным.
Я, возможно, понимаю о чём вы говорите, про компенсацию недостатков макросами. В моём понимании, их ещё можно компенсировать метапрограммированием. Но, с моей точки зрения, оба этих решения спорные, потому что в неумелых руках могут принести больше вреда, чем пользы. Среди рисков, использование таких механизмов языка с достаточной вероятностью может увеличить сложность разработки, отладки и может резко увеличить порог входа в решения на её основе.
Да и даже если обозначенные проблемы решаются, то всё-равно частично.
Это действительно решает почти все обозначенные проблемы. Говорю почти все потому что, чтобы применить такое решение нужно:
Использовать минимум C++14, если нужен гетерогенный поиск по упорядоченным контейнерам.
Использовать минимум С++20, если нужен гетерогенный поиск по неупорядоченным контейнерам.
Писать отдельные от объявления контейнера хэш-функции(для неупорядоченного контейнера) и компараторы(для упорядоченного), что размазывает логику по коду, тем самым затрудняя его понимание.
Ещё, если я вас верно понял, то стоит учитывать, что такое решение потребует написать намного больше кода и потребует больше ручной работы. Поскольку:
Нужно будет определять по структуре тэга с конструктором, принимающим один параметр(если только это не POD), потому что нам надо будет передавать через объект этой тэга значение ключа.
Нужно будет создавать реализацию
operator()в компараторе для каждого из тегов вручную. При этом стоит учитывать, что всегда нужно по 2 реализации: когда тег - первый параметр, и когда второй.В итоге придётся написать так:
Вместо in-place объявления в типе контейнера
boost::multi_index::tag<struct PersonsByName>:Масштаб этой проблемы незначителен на маленьком количестве тэгов. Но на маленьком наборе и не получится проверить насколько такое решение гибкое. Если добавить много разных тегов, в т.ч. и композитных, то даже на небольшом множестве из 3 полей может получится уже до 6 структур тегов и 12 реализаций
operator()для каждой структуры, и весь этот код придётся писать вручную. Соответственно, в более сложных системах всё будет более печально.Поэтому я не считаю такое решение достаточно гибким.