AMadeus (C++) Containers

<details><summary>Sections</summary> <p>

• AMadeus (C++) Containers
  • Brief
  • Contents
  • Benefits
    • Performance optimizations
      • Vectors
      • Sets
    • Other benefits
      • For vector types
      • For FlatSet
  • What is a trivially relocatable type?
  • Build with CMake
    • Options
    • As a main project
    • As a sub-project with cmake
      • With FetchContent
      • By installing amc
    • Tested environments
  • Usage examples
    • Vectors
      • amc::vector
      • SmallVector
      • FixedCapacityVector
    • Sets
      • FlatSet
      • SmallSet (c++17)

</p> </details>

Brief

Collection of high performance C++ containers, drop-in replacements for std::vector and std::set, used in Amadeus pricing and shopping engines instead of standard ones.

Contents

This header based library (to be more precise, cmake interface) provides the following containers:

| Container Name | STL equivalent | Brief | Why? | | ------------------- | -------------- | ------------------------------------------------------------------- | ------------------------------------------------------------ | | FixedCapacityVector | std::vector | Vector-like which cannot grow, max capacity defined at compile time | No dynamic memory allocation | | SmallVector | std::vector | Vector-like optimized for small sizes | No dynamic memory allocation for small sizes | | vector | std::vector | Vector optimized for trivially relocatable types | Optimized for trivially relocatable types | | FlatSet | std::set | Set-like implemented as a sorted vector | Alternate structure for sets optimized for read-heavy usages | | SmallSet (*) | std::set | Set-like optimized for small sizes | No dynamic memory allocation and unsorted for small sizes |

*: C++17 compiler only (uses std::variant & std::optional)

Benefits

Performance optimizations

• For types taking an integral N as template parameter, container does not allocate dynamic memory as long as its capacity does not exceed N
• Vectors (and FlatSet, as it uses amc::vector by default) are all optimized for trivially relocatable types (definition below).

Example of possible performance gains (directly extracted from the provided benchmarks, compiled with GCC 10.1 on Ubuntu 18:)

Vectors

Sets

For sets, time axis is in logarithmic scale.

Other benefits

• All 3 vector flavors share the same code / algorithms for vector operations.
• Templated code generation is minimized thanks to the late location of the integral N template parameter
• Optimized emulations of standard library features for older C++ compilers are provided when C++ version < C++17

A set of non standard methods and constructors are defined for convenience, provided that amc is compiled with AMC_PEDANTIC disabled (default, see Options). Here is a brief summary of these extras (compared to their STL equivalents):

For vector types

For all vectors (FixedCapacityVector, SmallVector, vector) | Method | Description | | -------------- | ------------------------------------------------------------ | | pop_back_val | Same as pop_back, returning popped value. | | append | Same as insert(vec.end(), ...) | | swap2 | Swap with all other flavors of vectors, not just this type |

For SmallVector only, there is a constructor from a rvalue of a amc::vector that allows stealing of its dynamic storage.

For FlatSet

| Method | Description | | --------------- | ------------------------------------------------------------------------------------------ | | data | Returns data const pointer from underlying vector | | operator[n] | Access to the underlying value at position 'n' for the FlatSet | | at(n) | Access to the underlying value at position 'n' for the FlatSet, throwing if our of range | | capacity | Calls underlying vector capacity method | | reserve | Calls underlying vector reserve method | | shrink_to_fit | Calls shrink_to_fit of underlying vector |

There is an additional constructor and assignment operator from a rvalue of the underlying vector type, stealing its dynamic storage.

What is a trivially relocatable type?

It describes the ability of moving around memory a value of type T by using memcpy (as opposed to the conservative approach of calling the copy constructor and the destroying the old temporary). It is a type trait currently not (yet?) present in the standard, although is has been proposed (more information here). No need to use a modified compiler to benefit from trivially relocatibilty optimizations: you can use helper type traits provided by this library to mark explicitely types that you know are trivially relocatable. The conservative approach assumes that all trivially copyable types are trivially relocatable, so no need to mark them as such. With trivially relocatable types, performance gains are easily measurable for all operations of the Vector like container involving relocation of elements (grow, insert in middle, etc).

Fortunately, most types are trivially relocatable. amc::vector itself is trivially relocatable (as well as FixedCapacityVector and SmallVector if T is). Types containing pointers to parts of themselves are typically not trivially relocatable, because moving them would require to update the internal pointers they hold to parts of themselves (std::list, std::set, std::map are for instance). std::string is not trivially relocatable in some implementations, but some open source equivalents are (for instance, folly::fbstring). More information here.

The most convenient way to mark a type as trivially relocatable is to declare in the public part of the class:

using trivially_relocatable = std::true_type;

This is only necessary for non trivially copyable types, because trivially copyable types are trivially relocatable by default.

Build with CMake

Options

| CMake flag | Description | | --------------------- | ------------------------------------------------------------------------------------------------------------------ | | AMC_ENABLE_TESTS | Build amc with unit tests (default if main project) | | AMC_ENABLE_BENCHMARKS | Build amc with benchmarks against STL (default if main project and Release mode) | | AMC_ENABLE_ASAN | Build with Address Sanitizer mode (only GCC and Clang) | | AMC_PEDANTIC | If OFF, non standard methods and constructors are added for containers (see Other benefits) |

As a main project

This library is header only library, with one file to be included per container.

Vectors and FlatSet containers require a C++11 compiler. SmallSet however, needs a C++17 compiler because it uses std::variant and std::optional, although boost::variant could be used as a workaround if a C++17 compiler is not available.

Unit tests and benchmarks are provided. They can be compiled with cmake.

By default, both will be compiled only if 'amc' is instantiated as the main project. You can manually force the build of the t