How to Design a Slimmer Vector of Variants in C++ - Christopher Fretz - CppCon 2024

cppcon.org​
---
How to Design a Slimmer Vector of Variants in C++ - Christopher Fretz - CppCon 2024
---
Heterogeneous containers ("vectors of variants") are an extremely flexible and useful abstraction across many data domains, but std::vector＜std::variant＜...＞＞ can exhibit extremely bad memory characteristics for mixed types of disparate size, especially if the largest types are relatively uncommon in practice. Variants always have to be at least as large as their largest contained type, and vector implicitly requires all of its members to be the same size, leading to significant bloat in such cases. Motivated by real-world use-cases, this talk explores the design of a bit-packed replacement data structure that can achieve massive improvements in memory usage, and the impacts that these optimizations have on its API.
---
Slides: github.com/Cpp...
Sponsored by JetBrains: www.jetbrains....
---
Christopher Fretz
---
CppCon is the annual, week-long face-to-face gathering for the entire C++ community. The conference is organized by the C++ community for the community. You will enjoy inspirational talks and a friendly atmosphere designed to help attendees learn from each other, meet interesting people, and generally have a stimulating experience. Taking place this year in Aurora, Colorado, near the Denver airport, and including multiple diverse tracks, the conference will appeal to anyone from C++ novices to experts.
Annual CppCon Conference - www.cppcon.org
/ cppcon
x.com/cppcon
/ cppconference
/ cppcon
mastodon.socia...
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
KZbin Channel Managed by Digital Medium Ltd: events.digital...
---
#vector #vectors #cpp #cplusplus #cppcon #cppprogramming #cplusplusprogramming #softwaredevelopment #softwareengineering #coding #code #technews #programming #programmer

[@JohnDlugosz]

The very end: Having separate arrays for each type would still be constant lookup time. The offset list is actually an index list, and the index is in the array of the proper type, which you are also looking up anyway.

[@JohnDlugosz]

I think it's important to note for your use case that you don't change the type of an element once it has been pushed back.

[@chefnyc]

Yeah, that would be as difficult as removing an item. All the sunsequent items would be moved and potentially require realignment.

[@pyajudeme9245]

Very good!

[@hydn]

This seems unnecessarily convoluted. It would be much simpler to store a std::tuple of std::vectors, one for each type. You would still have insertion, deletion, in-place mutation (which requires knowing the type in advance, just like the approach in the video), resizing for a specific type (much more efficiently than the method shown in the video), and the ability to visit each element. This approach offers simplicity and much more efficient resizing and pushing. Cache coherence would remain virtually the same, provided the number of elements is far greater than the number of types. The only thing that would be lost is ordering. But what is the point of maintaining ordering if doing anything meaningful requires knowing the type at a specific index in advance?

[@Febbe1]

Since when and why, a proxy class is an antipattern?

[@almightysapling]

I feel like you should reanalyze the final suggestion. Youre already storing offsets to each item, I dont see why splitting the items into Struct of Arrays wouldnt still maintain the same time characteristics for lookup and insert and pushback.

[@PanzerschrekCN]

Using vector-like interface for a collection of heterogeneous isn't good because of its random access nature. It's much better to store all elements in one chunk of memory one by another, prefixing them by type index and not using separate offset table. Doing so eliminates necessity to support such offset table (which consumes extra memory), but limits vector operations only to push_back and iteration, which isn't so good, but enough for many cases.

[@Mr7Shane]

stop saying um

[@JohnDlugosz]

It's not Linux that does mis-aligned loads. It's the x86 CPU.

[@fuxorfly]

um

[@jonatanlind5408]

Uhmmm...