Hello, World

  #include <iostream>

  int main()
  {
      std::cout << "Hi, I'm Borislav!\n";
      std::cout << "These slides are here: https://is.gd/beyondvec\n";
      return 0;
  }
        

Borislav Stanimirov

• I mostly write C++
• 2006-2018: game development
• From 2019 on: medical software
• Open source software
• github.com/iboB

Feature Set

• std::string_view arrived in C++17
• std::span arrived in C++20.
• map/set of string pre-C++14 is useless
• unordered_map/set of string pre-C++20 is useless
• The language of bad defaults: constness, moving, copying
• ...
• How Boost came to be

Performance

• iostream: a notoriously bad offender
• flat_map/set in contiguous memory
• std::hash (this is a documented extension point)
• ...

Allocations

• They are bad for performance
• map, set, list allocate every node
• this is somewhat understandable
• unoredered_map/set also allocate every node
• No allocator for function
• ...
• Allocators are notoriously hard to use

Predictability

• The land of "implementation defined"
• sizeof std::<pretty-much-anything>
• Small std::string size
• Iterators are who-knows-what
• std::filesystem::path::c_str() returns whatever
• ...

Compliance

• 64-bit unsigned size_t
• std::move_if_noexcept The Great Divider
• std::function must be copyable
• std::map::map is not noexcept
• ...

A Warning

• In most cases the standard library is acceptable
• Make sure you know what you're doing and why
• Test religiously
• Use sanitizers
• Always benchmark

This Talk

• A deeper dive in std::vector
• Likely the most fundamental standard library type
• Use cases for altetnatives
• Examples of alternatives
• Demos

Basic Characteristics

• Holds a contiguous block of memory
• Allocates memory
• Owns the memory
• Owns the objects
• Mutable container
• ...of mutable objects
• Has a bunch of implementation defined tidbits

Trivial to Challenge

• Contiguous memory - well, don't use std::vector
• Owns memory - use a reference
• Owns objects - use std::reference_wrapper
• Mutable container - use const std::vector

Where it Helps

• Predictability
• Growth factor
• Iterators
• shrink_to_fit is not required to shrink
• Feature set
• emplace returns a ref since C++17
• noexcept move since C++17
• Compliance: std::move_if_noexcept
• Debug performance: not to be underestimated

std::move_if_noexcept Drama

• Moving elements as a whole is a problem
• It's impossible to maintain coherency if move throws
• Only MS STL deals somewhat gracefully with moves
• Demo

Allocations

• Obvious cost
• The allocator has to do a bunch of stuff.
• Potentially make a syscall
• Physical memory: pages
• Free chunk of consecutive pages
• Sync between threads and processes
• Commit size - it's very helpful
• Not-so-obvious cost
• Zeroing/clearing of memory
• Fragmentation

Custom Allocators

• Usually very hard to use
• std::pmr helps, but not much
• Some kind of management is still needed
• std::pmr is not zero cost
• Work is being done to improve this
• ... for C++26

std::array

• The size always equals N
• The size is fixed
• What if we use a helper number for actual size?
• We still have to construct all elements
• What if the element is a POD and there are no constructors?
• When copying we still have to copy all elements
• Demo

static_vector

• A fixed capacity vector
• boost::static_vector - a powerful implementation
• itlib::static_vector
• 90% of the work with 10% of the code
• No std::move_if_noexcept
• No exceptions in at
• No allocations
• We copy only what we need
• Demo

small_vector

• A vector with a small-buffer optimization
• boost::small_vector - a poweful implementation
• itlib::small_vector
• 90% of the work with 10% of the code
• No std::move_if_noexcept
• No exceptions in at
• Vectors which have a size smaller than N the majority of the time
• ...in which case, there are no allocations
• Demo

realloc

We have a block of memory:

_expand (Windows only)

We have a block of memory (on Windows):

std::vector and realloc

• memcpy disregards constructors and destructors
• _expand can actually work
• It's sad that expanding is not more popular
• _expand can be implemented for any allocator
• C++23's allocate_at_least is a poor attempt to help
• But what if we dont care about constructors and destructors?

itlib::pod_vector

• When we don't care about constructors and destructors
• gh/iboB/itlib/pod_vector.hpp
• There are likely other implementations
• Memory is transferred realloc, memcpy, memmove...
• ... and _expand if available
• Also the other things: Debug performance, no exceptions on at
• Recast
• Demo

More Thoughts

• optimal_alloc_vector: uses _expand
• uber_vector: can be any of these
• std::vector is still quite powerful
• std::pmr::vector is awesome
• Much of this can be done via allocators with a small cost

std::span

• Packs pointer and size
• It's a trivial idea
• Allows ranged for loops
• Allows template algorithms
• An idea that's been around from the dawn of C++

my::span

• C++20 std::span
• boost::span
• itlib::span
• ... and likely hundreds more
• Demo

Ranges

Bonus

• gh/iboB/itlib
• ufunction - capture non-copyable (like unique_ptr)
• flat_map, flat_set - map with cache locality
• sentry - finally-type blocks
• Other, more niche stuff
• gh/iboB/mscharconv - charconv for cavemen