How can I avoid wasteful copying of keys in a B-tree based STL-like map?

Question

I'm replacing a use of std::map in a hot path with cpp-btree's btree_map. But with optimization enabled, GCC and Clang complain about a strict aliasing violation. The problem boils down to this:

template <typename Key, typename Value>
class btree_map {
public:
    // In order to match the standard library's container interfaces
    using value_type = std::pair<const Key, Value>;

private:
    using mutable_value_type = std::pair<Key, Value>;

    struct node_type {
        mutable_value_type values[N];
        // ...
    };

public:
    class iterator {
        // ...

        value_type& operator*() {
            // Here we cast from const std::pair<Key, Value>&
            // to const std::pair<const Key, Value>&
            return reinterpret_cast<value_type&>(node->values[i]);
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // At this point, we have to insert into the middle of a node.
        // Here we rely on nodes containing mutable_value_type, because
        // value_type isn't assignable due to the const Key member
        std::move_backward(node->values + i, node->values + j,
                           node->values + j + 1);
        node->values[i] = value;
        // ...
    }
};

This got me thinking, is there a way to do this as efficiently that doesn't rely on undefined behaviour? The keys I'm using are efficiently moveable but fairly slow to copy, so I'd love to avoid copying many keys on every insertion. I've considered

• Using value_type values[N], then const_cast<Key&>(values[i].first) = std::move(key) to move the key around, but I'm pretty sure that's still undefined
• Returning std::pair<const Key&, Value&> instead of std::pair<const Key, Value>& when appropriate, but I'm not sure this would still satisfy the container requirements (I hear ...::reference is supposed to really be a reference type)
• Not caring. The code works as-is, but I'm curious if it can be done in a standard-compliant way. There's also the chance that future compilers do different things with the UB, and I don't know of a way to apply -fno-strict-aliasing to only a single class.

Any other ideas?

Answer 1

Quoting from strict aliasing rules,

If a program attempts to access the stored value of an object through an lvalue of other than one of the following types the behavior is undefined:

• ...

• an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), ...

Hence going from std::pair<Key,Value> to std::pair<const Key, Value> via intermediate cast to a union or a struct containing both types as members won't break strict aliasing rules.

Caveat: std::pair in a union is not permited until C++11, can use a structure instead.

Caveat: assumption that the two pair types have compatible layouts may not hold true. Imagine an implementation that orders first and second differently depending on the constness of the Key type.

Answer 2

Modified: expanded move_backward(...) into for-loop with explicit destructor call and placement new to avoid assignment error.

Placement new can be used instead of simple assignment.

Note: this implementation below is not exception-safe. Additional code is required for exception-safety.

template <typename Key, typename Value>
class btree_map {
// ...
private:
    struct node_type {
        // Declare as value_type, not mutable_value_type.
        value_type values[N];
        // ...
    };

    class iterator {
        // ...

        value_type& operator*() {
            // Simply return values[i].
            return node->values[i];
        }
    };

    std::pair<iterator, bool> insert(const value_type& value) {
        // ...
        // expand move_backward(...)
        for(size_t k = j + 1; k > i; k--) {
            // Manually delete the previous value prior to assignment.
            node->values[k].~value_type();
            // Assign the new value by placement new.
            // Note: it goes wrong if an exception occurred at this point.
            new(&node->values[k]) value_type(node->values[k - 1]);
        }
        // Matual delete and placement new too.
        node->values[i].~value_type();
        // Note: it goes wrong if an exception occurred at this point.
        new (&node->values[i]) value_type(value);
        // ...
    }
};

Answer 3

You do not use BTREE as a replacement balanced binary tree with no reason: usually it is because you have a physical storage which is much slower and works as block-device that you need to use an array in a node which "somewhat" represents the device block. So trying to optimize the cycles spent in handling internal array is pretty marginal.

However, I suspect N is the key factor in :

struct node_type {
    mutable_value_type values[N];
    // ...
};

If it is small enough, you may not need to insert/lookup/remove an element in key order. The performance could be better than trying to order them in a small array. To avoid any move in Remove function, you could also define an empty slot so that Remove will just replace an element with an empty slot and Insert will replace the first met empty slot with an element.

For bigger array, you could use two arrays : one will contain as element a pair consisting of a key and an index/iterator pointing to the value stored in the second array. That way, you can still sort the first array fast regardless the type of value_type. That said, you still need to handle the second array when inserting or removing an element. The first array may also contain special pairs with pre-allocated indices in the second array when creating a node. A special pair is also set at removal of an element (keeping the index for later insertion of another element). When sorting the first array those special pairs will be put at the end. And knowing the count of inserted elements, you could use it as an index to allocate the first special pair to insert an element (allocating in second array) at O(1). At removal of an element, a special pair can replace the normal pair (keeping the index) in the first array just before sorting it. And you just need to use a placement new call or a destructor call on the current element (insertion or removal).