Как можно избежать расточительного копирования ключей в ST-подобной карте на основе B-дерева?
Я заменяю использование std::map в горячем пути с CPP-ВТКЕЕ«s btree_map, Но с включенной оптимизацией GCC и Clang жалуются на строгое нарушение псевдонимов. Проблема сводится к следующему:
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;
// ...
}
};
Это заставило меня задуматься, есть ли способ сделать это настолько эффективно, чтобы не полагаться на неопределенное поведение? Ключи, которые я использую, эффективно перемещаются, но копировать их довольно медленно, поэтому я бы хотел избежать копирования большого количества ключей при каждой вставке. Я считал
- С помощью
value_type values[N], затемconst_cast<Key&>(values[i].first) = std::move(key)переместить ключ, но я уверен, что это все еще не определено - возврате
std::pair<const Key&, Value&>вместоstd::pair<const Key, Value>&когда это уместно, но я не уверен, что это все равно удовлетворит требованиям контейнера (слышу...::referenceдолжен быть действительно ссылочным типом) - Не заботясь. Код работает как есть, но мне любопытно, можно ли это сделать стандартным образом. Также есть шанс, что будущие компиляторы будут делать разные вещи с UB, и я не знаю, как применить
-fno-strict-aliasingтолько в одном классе.
Есть другие идеи?
Решение
Цитировать из строгие правила алиасинга,
Если программа пытается получить доступ к сохраненному значению объекта через значение lvalue, отличное от одного из следующих типов, поведение не определено:
…
тип агрегата или объединения, который включает в себя один из вышеупомянутых типов среди своих членов (включая, рекурсивно, член субагрегата или автономного объединения), …
Следовательно происходит от std :: pair<Key, Value> в std :: pair<Ключ const, Значение> через промежуточное приведение к объединению или структуре, содержащей оба типа в качестве членов, не будет нарушать строгие правила псевдонимов.
Предостережение: std :: pair в объединении не разрешено до C ++ 11, вместо этого можно использовать структуру.
Предостережение: предположение, что два типа пар имеют совместимые макеты, может не соответствовать действительности. Представьте себе реализацию, которая упорядочивает первое и второе по-разному в зависимости от константности типа Key.
Другие решения
Модифицировано: расширено move_backward(...) в цикл for с явным вызовом деструктора и новым размещением, чтобы избежать ошибки присваивания.
Размещение нового можно использовать вместо простого назначения.
Примечание: эта реализация ниже не является безопасной для исключения. Дополнительный код требуется для исключительной безопасности.
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);
// ...
}
};
Вы не используете BTREE как сбалансированное двоичное дерево для замены без причины: обычно это происходит из-за того, что у вас физическое хранилище, которое намного медленнее и работает как блочное устройство, вам необходимо использовать массив в узле, который «несколько» представляет блок устройства. Поэтому попытка оптимизировать циклы, затрачиваемые на обработку внутреннего массива, довольно незначительна.
Тем не менее, я подозреваю, что N является ключевым фактором в:
struct node_type {
mutable_value_type values[N];
// ...
};
Если он достаточно мал, вам может не понадобиться вставлять / искать / удалять элемент в порядке следования ключей. Производительность может быть лучше, чем пытаться упорядочить их в небольшом массиве. Чтобы избежать какого-либо перемещения в функции Remove, вы также можете определить пустой слот, так что Remove просто заменит элемент пустым слотом, а Insert заменит первый встреченный пустой слот элементом.
Для большего массива вы можете использовать два массива: один будет содержать в качестве элемента пару, состоящую из ключа и индекса / итератора, указывающего на значение, хранящееся во втором массиве. Таким образом, вы можете быстро отсортировать первый массив независимо от типа value_type, Тем не менее, вам все равно нужно обрабатывать второй массив при вставке или удалении элемента. Первый массив также может содержать специальные пары с предварительно выделенными индексами во втором массиве при создании узла. Специальная пара также устанавливается при удалении элемента (сохраняя индекс для последующей вставки другого элемента). При сортировке первого массива эти специальные пары будут помещены в конец. И, зная количество вставленных элементов, вы можете использовать его в качестве индекса для выделения первой специальной пары для вставки элемента (размещения во втором массиве) в точке O (1). При удалении элемента специальная пара может заменить нормальную пару (сохраняя индекс) в первом массиве непосредственно перед сортировкой. И вам просто нужно использовать новый вызов размещения или вызов деструктора текущего элемента (вставка или удаление).
detector