This is the type of talks I very much like. Not just telling you what to do or show you end result/product. But actually explaining the iterative process and design evolution clearly. Wonderful talk. Thanks.
Just don't put big types in std::variant, it has the 500x padding all on its own. You can put those types behind unique_ptr (similar to the small object optimization suggestion) or separate the logic for them with overloads/templates/polymorphism. Interesting points on heterogeneous containers generally though. It's not too different from the double-indirection version, with `offset` storing pointers into `array` a bump allocator
Chipping in, you only really need to form vectors* for different alignments, then because accesses need type information and offset/index/alignment information store those as a tuple or a trivial type of integers (or a single uint64_t where the top bits are used to distinguish the type and alignment).
I believe the C++ standard guarantees elements of a vector be stored contiguously and sequentially in memory, so that, for example, any library function which expects a pointer to the start of an array can work with data from a vector
An interesting talk. But also a cautionary tale about how C++ programmers over-engineer everything. I would just have slapped the 5000 byte struct inside a unique_ptr and called it a day.
Wonder if the idea was considered to have one vector for each type. The type array would then give which array to look at. And the index instead of bytes would store the index in that specific array. That would make the internal implementation quite a bit simpler, while adding a bit more stack space. Heap storage and performance characteristics should be similar.
Personally my first choice would be a struct of vectors instead of vector of variants. No problems with alignment, minimal storage, and minimal complexity(unless there are additional constraints like keeping the "variants" ordered, but that can be solved with just an additional indirection)
For the type/offset storage, I think it could be combined together, since you're already using bitfields for your type indices, i.e. store the type information in the LSB of an unsigned integer and store the offset in the MSB.
I have another idea: Store an tuple of std::vectors in the vv type alongside a similar type/offset storage that index into the tuple of vectors. This will bloat the stack size of the actual vv type significantly but it solves all the problems w.r.t. alignment or insertions, since you can just manipulate the underlying normal std::vector of the corresponding type. The heap memory usage of this approach will be the same as that of your proposed implementation.
To avoid alignment issues, I think that we can store different types inside different vectors. I am not sure which operation will be more complex in comparison to proposed approach, but maybe something to look into..
the operator [] could return const variant, thus making assigning a compiler error. however, this could lead to unintended copies where people spell out the actual type instead of auto.
I just learned something new! I considered this, but I mistakenly thought that const qualifiers were discarded by the language on return by value. However, testing it myself, your suggestion does actually appear to work! Yeah, that would be my next concern, auto always deducing const, even when you don't want it, and it also wouldn't behave as expected with binding to rvalue references, but this is very interesting, thank you! If I ever give this talk again I will present the pros/cons of this idea.
great talk! quick question though: how exactly does vv::vector::visit figure out the type of the thing it's looking at? You're storing the type metadata in an array on the heap, so you can't use those runtime values to index into a type list or call the std::in_place_index_t constructor of std::variant. How do you map the runtime index to an actual type?
This is the type of talks I very much like. Not just telling you what to do or show you end result/product. But actually explaining the iterative process and design evolution clearly.
Wonderful talk. Thanks.
Just don't put big types in std::variant, it has the 500x padding all on its own. You can put those types behind unique_ptr (similar to the small object optimization suggestion) or separate the logic for them with overloads/templates/polymorphism. Interesting points on heterogeneous containers generally though. It's not too different from the double-indirection version, with `offset` storing pointers into `array` a bump allocator
Why not store each of the possible types in the variant in separate vectors of each type? So a vector
You would have too much cache locality and performance issue I think.
Chipping in, you only really need to form vectors* for different alignments, then because accesses need type information and offset/index/alignment information store those as a tuple or a trivial type of integers (or a single uint64_t where the top bits are used to distinguish the type and alignment).
I believe the C++ standard guarantees elements of a vector be stored contiguously and sequentially in memory, so that, for example, any library function which expects a pointer to the start of an array can work with data from a vector
Perhaps, to satisfy ContiguousContainer requirement, as std::vector does.
@@romanzelenyi982 Contiguous Container requires all elements to be the same size.
An interesting talk. But also a cautionary tale about how C++ programmers over-engineer everything. I would just have slapped the 5000 byte struct inside a unique_ptr and called it a day.
Wonder if the idea was considered to have one vector for each type. The type array would then give which array to look at. And the index instead of bytes would store the index in that specific array. That would make the internal implementation quite a bit simpler, while adding a bit more stack space. Heap storage and performance characteristics should be similar.
Why not use something like std::vector?
Personally my first choice would be a struct of vectors instead of vector of variants. No problems with alignment, minimal storage, and minimal complexity(unless there are additional constraints like keeping the "variants" ordered, but that can be solved with just an additional indirection)
For the type/offset storage, I think it could be combined together, since you're already using bitfields for your type indices, i.e. store the type information in the LSB of an unsigned integer and store the offset in the MSB.
I have another idea: Store an tuple of std::vectors in the vv type alongside a similar type/offset storage that index into the tuple of vectors. This will bloat the stack size of the actual vv type significantly but it solves all the problems w.r.t. alignment or insertions, since you can just manipulate the underlying normal std::vector of the corresponding type. The heap memory usage of this approach will be the same as that of your proposed implementation.
To avoid alignment issues, I think that we can store different types inside different vectors. I am not sure which operation will be more complex in comparison to proposed approach, but maybe something to look into..
the operator [] could return const variant, thus making assigning a compiler error. however, this could lead to unintended copies where people spell out the actual type instead of auto.
I just learned something new! I considered this, but I mistakenly thought that const qualifiers were discarded by the language on return by value. However, testing it myself, your suggestion does actually appear to work!
Yeah, that would be my next concern, auto always deducing const, even when you don't want it, and it also wouldn't behave as expected with binding to rvalue references, but this is very interesting, thank you! If I ever give this talk again I will present the pros/cons of this idea.
great talk!
quick question though: how exactly does vv::vector::visit figure out the type of the thing it's looking at? You're storing the type metadata in an array on the heap, so you can't use those runtime values to index into a type list or call the std::in_place_index_t constructor of std::variant. How do you map the runtime index to an actual type?
got a basic version working with some magic fold expressions ✌thanks again for the cool talk 😄
Just wrap the largest variant T in unique_ptr?
stop teaching me more C++ I'm already fully insane
lol
Great talk. Learned a lot. Though, so many “umm”s..