/tight_pair

A compressed pair for C++17

Primary LanguageC++MIT LicenseMIT

Latest Release Code Coverage Pitchfork Layout

This experimental project is a small single-header header-only C++17 library providing a single tight_pair class template and associated functions. It is not meant to be anywhere near serious, but it was a fun little project to try to design a C++17-only component, and to optimize it as possible despite the underlying layers of abstraction :)

cruft::tight_pair is a C++17 compressed pair class. Unlike Boost.Compressed_Pair it is modelled after std::pair, with only a few additions and a few deletions. First, a short list of what is similar to the standard library's std::pair, then we will have a look at what makes them different:

  • It supports the same set of constructors, and most notably the EXPLICIT ones.
  • It also handles piecewise construction, which allows to build non-copyable, non-movable types.
  • It has a tuple-like interface through std::tuple_size, std::tuple_element, and and ADL-found get.
  • It works with structured bindings.
  • Its get function also accepts types, unless the pair stores two elements of the same type.
  • It is trivially destructible when both elements are trivially destructible.
  • It unwraps an std::reference_wrapper<T> as a T&.
  • It supports comparison when its elements support comparison.

Differences from std::pair

Now is the time to look at what actually makes this tight_pair different from the standard library's std::pair:

  • As its name implies, it is what is known as a compressed pair: a pair that privately inherits from the elements to take advantage of empty base class optimization (EBCO) and thus reduce the size of the pair. This kind of optimization is mostly used when storing empty function objects.

    #include <functional>
#include <iostream>
#include <utility>
#include <tight_pair.h>

// Store a comparison and a projection (see C++20)
auto p1 = std::pair(std::less{}, std::identity{});
auto p2 = cruft::tight_pair(std::less{}, std::identity{});

// prints "2 1" on my computer
std::cout << sizeof(p1) << ' ' << sizeof(p2);

    Recent std::pair implementations might rely on the C++20 [[no_unique_address]] attribute to compress empty objects. However not all compilers currently implement the compressing semantics of that attribute in order to avoid ABI surprises.

  • Full EBCO requires to inherit privately from the empty base members in order to pack the pair as much as possible, even when holding instances of other empty pairs. However, this causes a problem with structured bindings: the lookup looks for a class-member get before looking for a get function with ADL. Therefore, if we privately inherit from an empty class with a conforming get function, the structured bindings lookup will find it first but will trigger an error because it is inaccessible.

    To bypass this potential bug without losing its compressing abilities, cruft::tight_pair has in-class get functions equivalent to those that can be found thanks to ADL.

    Note: this issue was partially mitigated in C++20 by P0961 which ensures that the compiler will only look for a member function template, which avoid tripping on a non-template member get() like the one available with smart pointers. That solution is however incomplete, and our own mitigation still solves potential issues.

  • Unlike std::pair, it doesn't have first and second members nor does it provide first_type or second_type type aliases. The members can only be accessed through the get function template, and the member types can only be retrieved through std::tuple_element. It was a choice to only provide a minimal tuple-like interface.

  • Since it is a C++17-only library, I decided not to provide an equivalent to std::make_pair: the type deduction is done through deduction guides. Unlike std::pair, the deduction guides are the ones that handle the decaying of array and reference parameters as well as the unwrapping of std::reference_wrapper<T> to T&. Of course it is still possible to store arrays or raw std::reference_wrapper instances by manually specifying the types.

    int a = 5;
// Creates a cruft::tight_pair<int const&, const char*>
auto pair = cruft::tight_pair(std::cref(a), "welcome");

  • I borrowed a libc++ extension which allows cruft::tight_pair to be constructed from any pair-like type. A pair-like type is any type T for which std::tuple_size_v<T> == 2 and a get function template can be found through ADL. This notably allows to directly construct a cruft::tight_pair from std::pair<T, U>, std::tuple<T, U> or std::array<T, 2>, as well as other conforming types from third-party libraries.

  • Piecewise construction accepts tuple-like classes instead of just instances of std::tuple to pass arguments to initialize the pair members.

  • When possible the comparison and relational operators are optimized with bit tricks to be branchless, and hopefully faster than their std::pair equivalents. They are currently optimized for a subset of the unsigned types. Here are some benchmarks results I obtained by feeding instances of std::pair and cruft::tight_pair to comparison sorts from another of my libraries:

    Benchmark sorting std::pair and cruft::tight_pair

    Of course those benchmarks are biased: you may not always get results that good if you replace unsigned short by unsigned int, but you get the idea. The benchmarks can be found in the bench directory of the project, and the results have been obtained with MinGW g++ 7.1.0 with the options -O3 -march=native.

  • Most of the constructors are conditionally noexcept (at the time of writing, only the piecewise constructor and the one that takes a pair-like object are not noexcept).

  • Comparison and relational operators are hidden friends.

cruft::tight_pair also implements features library defects resolutions that were added to the standard after C++17 was published:

  • P1032 (C++20): make operator=, swap and the piewise constructor constexpr.
  • P1951 (C++23): default arguments for the forwarding constructor (see paper for rationale).
  • LWG2510: make the default constructor conditionally explicit.

Compiler support and tooling

Ubuntu builds status Windows builds status MacOS builds status

tight_pair requires C++17 support, and should work with the following compilers:

  • g++7 or more recent.
  • clang++6.0 or more recent.
  • Visual Studio 2019 version 16.8.3 or more recent, only with /permissive-.
  • The versions of MinGW-w64 and AppleClang equivalent to the compilers mentioned above.
  • Clang is notably tested with both libstdc++ and libc++.

The compilers listed above are the ones used by the CI pipeline, and the library is also tested with the most recent versions of those compilers on a regular basis. All the other compiler versions in-between are untested, but should also work. Feel free to open an issue if it isn't the case.

There might still be compiler errors with some corner cases that the library doesn't try to work around. The known ones are documented in a small knowledge base on the GitHub wiki.

WARNING: while the library works with MSVC, the codegen tends to be pretty poor.

Acknowledgements

I can't finish a project without stealing code around, so here are the main sources of the code that can be found in this project when I didn't write it by myself:

  • A great deal of code originally comes from the libc++ implementation of std::pair and std::tuple utilities.

  • Additional small bits of code are inspired by Microsoft STL.

  • All the tests that can be found in tests/libcxx have been ported from the libc++ testsuite and modified so that they can work with the minimal tuple-like interface of the library.

  • The tests in tests/cppreference.cpp were preliminary tests adapted from the examples on cppreference.com to check that the basic features worked correctly.

  • The algorithm used to detect whether unsigned integer types have padding bits originally comes from the WG14 paper N1899 - Integer Precision Bits Update by David Svoboda.

  • The enumeration used to check the integer byte order of scalar types originally comes from the WG21 proposal P0463 - endian, Just endian by Howard Hinnant.

  • I also want to thank the Godbolt online compiler explorer as well as people from Lounge<C++> who helped me optimize the small details down to assembly while still striving to remain standard-compliant :)