Faster, Easier, Simpler Vectors - David Stone

Faster, Easier, Simpler Vectors - David Stone - CppCon 2021

Рет қаралды 29,007

Күн бұрын

cppcon.org/
github.com/CppCon/CppCon2021
---
The standard library has the type `std::vector`. It is used ubiquitously as a high-performance container. However, it was standardized in the mid 90s and C++ has seen many changes since then. It has been extended with allocators, move semantics, initializer_list, and much more. Can we do better?
We can. It is possible to write a container and a set of algorithms that are more efficient at run time, have simpler implementations, and have easier, more intuitive APIs. Not only that, but we can also make it easy for users to write their own vector-like containers that make slightly different trade-offs for when you need even more performance, and this presentation includes discussion of several such vectors.
We will go through specific examples of these vector-like types and the algorithms that operate on them, and then take from that general principles of software design. We'll look into how we're limited in what we can do by C++ as it exists today and what up-and-coming proposals can make things even better.
---
David Stone
David Stone has worked on autonomous vehicles, large-scale distributed systems, and now works developing software for high-frequency trading. He is a member of the C++ Standardization Committee, where he chairs the Modules Study Group (SG2) and is the vice chair of the Evolution Working Group (EWG).
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
KZfaq Channel Managed by Digital Medium Ltd events.digital-medium.co.uk
*--*

Пікірлер: 26

@pingkai 6 ай бұрын

At this point, C++ is always solving problem that created by itself, which created so much opportunities for the standard!

@DerekWoolverton 8 ай бұрын

The issue with relocate vs move is whether we should take control as programmers, or lean on the compilers to get smart enough to optimize the move-delete idiom.

@TarikZakariaBenmerar 2 жыл бұрын

How the append has been converted into a set of low level instructions and no function calls ?

@cemgecgel4284 Жыл бұрын

compiler magic

@broken_abi6973 2 жыл бұрын

where did he find the "stable vector" he referred to? His description seems to be different than boost::stable_vector

@pervognsen_bitwise 2 жыл бұрын

I think he was referring to the concept more so than any particular implementation. The idea is to reserve a memory range with VirtualAlloc/mmap based on the max capacity and then growing the capacity extends the commit range in place rather than reallocating. Both allocation/deallocation and first-time page access incurs kernel mode transitions (syscalls and page faults, respectively), so it's not something you want for short lived or high churn vectors. But it can be useful if your application has a relatively small handful of big vectors where you need stability and/or performance. (Of course, if you just want stability and performance is not an issue, you can allocate and store the elements outside of the vector itself, as std::unordered_map has to do. The vector would still own those out-of-line elements, so the value semantics would be preserved.)

@barakap2372 2 жыл бұрын

@@pervognsen_bitwise Do you know any stable vector implementation which has just 1 memory chunk and uses mmap or VirtualAlloc and os-specific functions?

2 жыл бұрын

Why there is no call to operator delete in the compiled code from the alternative implementation of vector? (At least in the insert example.)

@joy1710 2 жыл бұрын

I don't get it why allocator is not part of vector interface. Do all these vector types assume std::allocator?

@anthonynjoroge5780 2 жыл бұрын

What do you mean? The allocator type is the second template type parameter. For example you can specify your own custom allocator as follows: vector v.

@JohnDlugosz 2 жыл бұрын

Look for some of the talks from John Lacos. He explains why it is good for types to implement the allocator feature, for enterprise scale software.

@Bbdu75yg Жыл бұрын

Why cant we just malloc an element , and have vector of pointers ? No need of move ,emplace_back ?

@StanleyPinchak 10 ай бұрын

Cache locality? No need for additional indirection? Ability to memcpy contents?

@Roibarkan 2 жыл бұрын

On simple optimizations: m.kzfaq.info/get/bejne/qZqnodiaqN24d4k.html

@mr_waffles_the_dog 2 жыл бұрын

thanks!

@ragnarlothbrok367 2 жыл бұрын

Sometimes I don't understand a shit

@__hannibaalbarca__ Жыл бұрын

Good Programming Language Designed by aGood Mathematicians and to do such good thing like programming in mathematics headaches of assembling many mathematical field in one. Proofing process like in Topology, and we have to separate very close cases when we stadying vectorial spaces and topological spaces after Category theory and abstract algebra and algebraic geometry… this gave to programming designer more conceptual analysis of language.

@llothar68 Жыл бұрын

Mathematicians are more often than not terrible programmers.

@Bolpat 2 жыл бұрын

I had a really hard time to understand _append_from_capacity._ It has a horrible name. It’s not perfect, but _assume_values_in_cpacity_ would even be a better name and that’s not even that great.

@pervognsen_bitwise 2 жыл бұрын

I've seen this kind of thing called append_uninitialized(size_t n) which just does ensure_capacity(size + n); size += n. You'll find something akin to this in many non-std vector implementations. In Unreal Engine, for example, it's TArray::AddUninitialized.

@David-fn1rd Жыл бұрын

Presenter here, and I agree, the name is horrible. There is work to add this to std::vector, and part of that will include coming up with a (hopefully) great name.

@passerby4507 2 жыл бұрын

Welp, the talk didn't deliver what it promised in the title. I'm not sure what I learnt, and I'm not sure in what situation I would recommend someone listen to this.