Reply-to: Allan Deutsch <[email protected]>
Audience: LEWG, SG14
Document Number: P0661r2 - DRAFT
November 13, 2017
This is a proposal to make an addition to the containers library, slot_map. slot_map is an container adapter which creates an associative container with a map-like interface, except users insert only values and a unique key to access it is returned. This is done with the use of slots - a stable, reusable indirection between keys and values. This allows the stored data to be moved in memory such that it is always packed at the front of the backing container for excellent performance when iterating over the stored data.
slot_map is the ideal container for two primary use cases:
- The user wishes to have good traversal performance for unordered data, and would like to have stable keys to access specific elements.
- The user would otherwise use an unordered_map, but the keys have no meaning other than being uniquely associated with a value. In this case slot_map is a performance improvement that handles the task of generating unique keys for each inserted value.
Assuming it is adapting a vector-like container, slot_map has the following time complexities:
| operation | Average case | Best case | Worst case |
|---|---|---|---|
| insert | O(1) | O(1) | O(n) |
| find | O(1) | O(1) | O(1) |
| erase | O(1) | O(1) | O(1) |
| traversal | O(n) | O(n) | O(n) |
The worst case for insert occurs only when size() == capacity() and a reallocation is required.
To understand slot_map conceptually, it may help to think of it as a pool allocator with a map-like interface. Unique features:
- Consistent constant time operations – keys include index information which is used to avoid expensive modulo or hashing operations. Since operations are all index based, the performance variance is minimized.
- Contiguous element storage – whenever an element is erased, the element at the end is moved into the memory location of the erased element. With an array-like underlying storage type, this means all elements are stored contiguously.
- Stable access – the return value of any insert or emplace operation can be used to access the inserted element or fail in constant time.
- Slots – to power most of its other unique features, this adapter utilizes an additional container instance for slots – fixed, reusable indices – which serve as a lightweight indirection layer that can convert between a stable slot and an unstable array element.
A reference implementation which tracks changes to the proposal is provided by the proposal author on github. It is available here. (Since revision 1) A reference implementation implemented by Arthur O'Dwyer for the SG14 repo based on this proposal can be found here. (Since revision 2)
| Revision 0 | Revision 1 |
|---|---|
template<typename Key, typename Value, Key Max_Elements, typename Container = std::vector<Value>> class slot_map; |
template<typename T, typename Key = std::pair<unsigned, unsigned>, template<typename...> typename Container = std::vector > class slot_map; |
| Generation counter overflow may silently fail | |
| Key is an integer type containing 2 bit fields | Key is any type decomposable into 2 integer-like types using std::get<>. |
std::get<0>(key) must result in a type at most the size of Container::size_type. |
| Revision | Question | Answer | Answered by |
|---|---|---|---|
| R1 | Keep the name slot_map? |
| Revision | Question | Answer | Answered by |
|---|---|---|---|
| R1 | Should a supplementary key type be provided equal to default but throwing on generation overflow? | Yes. | SG14 & LEWG |
| R1 | Should clear() reset generation counters and the free list? | Yes. | SG14 |
| R1 | Should raw access to the underlying container be provided? | No. | SG14 |
| R1 | Are insert_at() and emplace_at() interfaces desired? | No. | SG14 |
| R1 | Should the template parameters remain as suggested in R1? | Yes. | SG14 |
constexpr slot_map( );
constexpr slot_map( const slot_map & ) = default;
constexpr slot_map( slot_map && ) = default;
constexpr ~slot_map( ) = default;constexpr slot_map& operator=( const slot_map & ) = default;
constexpr slot_map& operator=( slot_map && ) = default;The at() functions have both generation counter checking and bounds checking, and throw a std::out_of_range exception if either check fails. O(1) time and space complexity.
constexpr reference at( const key_type& key );
constexpr const_reference at( const key_type& key ) const; The bracket operator[] has a generation counter check. If the check fails it is undefined behavior. O(1) time and space complexity.
constexpr reference operator[]( const key_type& key );
constexpr const_reference operator[]( const key_type& key ) const;The find() functions have generation counter checking. If the check fails, the result of end() is returned. O(1) time and space complexity.
constexpr iterator find( const key_type& key );
constexpr const_iterator find( const key_type& key ) const;The find_unchecked() functions perform no checks of any kind. O(1) time and space complexity.
constexpr reference find_unchecked( const key_type& key );
constexpr const_reference find_unchecked( const key_type& key ) const;All begin() and end() variations have O(1) time and space complexity.
constexpr iterator begin( );
constexpr iterator end( );
constexpr const_iterator begin( ) const;
constexpr const_iterator end( ) const;
constexpr const_iterator cbegin( ) const;
constexpr const_iterator cend( ) const;
constexpr reverse_iterator rbegin( );
constexpr reverse_iterator rend( );
constexpr const_reverse_iterator rbegin( ) const;
constexpr const_reverse_iterator rend( ) const;
constexpr const_reverse_iterator crbegin( ) const;
constexpr const_reverse_iterator crend( ) const; Functions for checking the size and capacity of the adapted container have the same complexity as the adapted container.
reserve(n) has the complexity of the adapted container, and uses additional time which is linear on the increase in size. This is caused by adding the new slots to the free list.
constexpr bool empty( ) const;
constexpr size_type size( ) const;
constexpr size_type max_size( ) const;
constexpr size_type capacity( ) const;
constexpr void reserve( size_type n );Functions for accessing and modifying the capacity of the slots container. These are beneficial as allocating more slots than values will cause the generation counter increases to be more evenly distributed across the slots.
constexpr void reserve_slots( size_type n );
constexpr size_type capacity_slots( ) const;These operations have O(1) time and space complexity. When size() == capacity() an allocation is required which has O(n) time and space complexity.
constexpr key_type insert( const value_type& value );
constexpr key_type insert( value_type&& value );
template<typename... Args>
constexpr key_type emplace( Args&&... args ); Each erase() version has an O(1) time complexity per value and O(1) space complexity.
constexpr iterator erase( iterator pos );
constexpr iterator erase( iterator first, iterator last );
constexpr iterator erase( const_iterator pos );
constexpr iterator erase( const_iterator first, const_iterator last );
constexpr size_type erase( const key_type& key );clear() has O(n) time complexity and O(1) space complexity. It also has semantics differing from erase(begin(), end()) in that it also resets the generation counter of every slot and rebuilds the free list.
constexpr void clear( );using key_size_type = std::remove_reference_t<decltype( std::get<0>( std::declval<Key>( ) ) )>;
using key_generation_type = std::remove_reference_t<decltype( std::get<1>( std::declval<Key>( ) ) )>;
using value_type = typename Container<T>::value_type;
using key_type = Key;
using size_type = typename Container<T>::size_type;
using reference = typename Container<value_type>::reference;
using const_reference = typename Container<value_type>::const_reference;
using pointer = typename Container<value_type>::pointer;
using const_pointer = typename Container<value_type>::const_pointer;
using container_type = Container<value_type>;It also provides the following iterator type aliases. Note that the adapted container must provide iterators satisfying the constraints of RandomAccessIterator.
using iterator = typename Container<value_type>::iterator;
using const_iterator = typename Container<value_type>::const_iterator;
using reverse_iterator = typename Container<value_type>::reverse_iterator;
using const_reverse_iterator = typename Container<value_type>::const_reverse_iterator;It is a common problem in software development that mutable data needs a stable way to be accessed. slot_map provides a solution with excellent performance for lookup, insert, erase, and traversal operations which are close to the performance of a vector and far exceeding that of unordered_map. The proposal has garnered interest from a wide variety of domains, ranging from games and trading to compilers and scientific computing. Containers akin to what is proposed in this paper are very widespread throughout the games industry, and this proposal seeks to standardize that existing practice in a form which can benefit the c++ community more broadly.
This adapter addresses several problems present in other containers; inconsistent execution time, unstable element location, poor cache utilization, and high overhead for find.
It also solves the ABA-like problem caused by an element being deleted and replaced with a new element using the same key. This is accomplished using the generation counter of the key.
This container is meant for use by anyone who believes C++ is the right tool for what they are doing. People from a variety of software categories have expressed interested: compilers, virtualization, simulations, web browsers, scientific computing, high frequency trading, and more.
There are two primary kinds of users:
- Users who have needs which are met by the basic guarantees and properties of the adapter, with no need to modify it from the default settings.
- User from domains such as games and high frequency trading for whom it is worthwhile to invest a great deal of time into optimizing for better performance.
The proposal suggests sane defaults that should sufficiently meet the needs of 99% of users. For those remaining in the other category, powerful knobs for fine-tuning the container are provided, but there are other properties which are currently not modifiable that these users would benefit from having.
As a standard container it should be accessible to anyone who understands how associative containers work. The ideal interface and behavior will be as close to those of other containers in the STL as possible.
The container is a pure extension. It can be implemented without any modifications to existing language or library features.
As with all other standard containers, it should have its own header. The suggestion is that the header have the same name as the container as that is what is done for other containers.
The name slot_map does not have consensus. One argument against the name is that “map” has meaning in C++ which is different from how slot_map works, particularly the APIs for inserting and accessing elements are quite different, and could lead to wrong assumptions. This also applies with the unordered_* prefix.
Some other suggestions:
- slot<> - names the container after its most unique feature, and remains concise. One downside is that the concept of a slot already exists in C++ terminology because of the "signals and slots" from Qt.
- slot_store<> - this version is more verbose, opting to include both the most unique feature and what its purpose is. The name is longer, but avoids being confused with the kind of slot use to receive a signal.
- valet<> - This version is the most descriptive of the behavior of the container. A valet receives your car and returns a ticket which can be used to access it, then goes and stores your car in a parking lot adjacent to other cars, likely filled near the front. This is strikingly similar to the behavior of the container described in this proposal which receives a user's data and returns a key which can be used to access it, and stores the data near the front adjacent to the other data.
Question for the committee: Should the name slot_map be used?
Strong suggestion: Yes, but only until another name is able to achieve consensus. Changing the name more than once makes it much more difficult to follow changes.
| R0 | R1 |
|---|---|
| Any integer type, with a bit count specified for indexing and the rest use for generation counting. | Any type decomposable into two integer-like types. Defaulted to std::pair<unsigned, unsigned> |
Based on feedback from LEWG in Toronto, this change was made to make the container both more beginner friendly and more customizable for advanced usage. The new default type is reasonable for most use cases. Users desiring customization could provide a bitfield struct that packs the bits, a generation counter type which throws on overflow, or something else with behavior that better suits their needs.
Note: The first type of the key must be at most the size of the underlying container’s size_type.
| R0 | R1 |
|---|---|
template<typename Key, typename Value, Key Max_Elements, template<typename> typename Container = std::vector> class slot_map; |
template<typename Value, typename Key = std::pair<unsigned, unsigned>, template<typename...> typename Container = std::vector > class slot_map; |
The change from R0 to R1 makes the basic use case much easier. Compare these two declarations of approximately the same slot_map under the two versions:
| R0 | R1 |
|---|---|
slot_map<unsigned long long, T, (1<<31) > |
slot_map<T> |
This is much more approachable for beginners and reduces the likelihood they will shoot themselves in the foot by not understanding how the container works. Advanced users get much more flexibility with the key type, and don’t have to think about bit packing unless they need the performance from it.
In the Toronto 2017 meeting, LEWG agreed that silent failure on overflow is good default behavior. Users desiring something else can provide a custom key type with the behavior they want. This was later reconfirmed by SG14 at CppCon 2017.
Depending on the underlying container type, certain guarantees may be broken. The container as a customization point is intended for advanced users. As examples, advanced users may wish to use other vector-like backing containers such as llvm::SmallVector, boost::static_vector, or a block-based container such as std::deque. In order to support this, the container is proposed as an adapter rather than a stand-alone container.
When clear() is called, it could clear all the elements, reset all slot generation counters to 0, and order the free list from front to back. It could alternatively preserve the slot generation counters and free list ordering, which would give it the same behavior as erase(begin(), end()).
At CppCon 2017, SG14 voted that it should reset the generation counter of every slot and rebuild the free list sequentially from front to back.
Access to the adapted container can be useful for advanced users. It has downsides though – users can easily break adapter correctness by modifying element order in any way while they have access. It is unclear what the value of immutable access to the adapted container would be.
At CppCon 2017, SG14 voted against providing this.
Note that these examples assume all previous example blocks are above them in the same scope.
slot_map<int> sm;
auto key{ sm.insert(5) };
assert(sm[key] == 5);
assert(sm[key] == sm.at(key));
assert(sm[key] == *sm.find(key));sm.erase(key);
assert( sm.find(key) == end(sm) );std::vector<slot_map<int>::key_type> keys;
for(int i{0}; i <= 10; ++i)
keys.emplace_back( sm.insert(i) );
int sum{ std::accumulate(begin(sm), end(sm), 0) };
// summation of 1..n = n*(n+1)/2.
assert( sum == (10*11)/2 );