производительность emplace хуже проверки с последующей emplace
у меня есть std::unordered_map с тип ценности это не имеет конструктор по умолчанию, поэтому я не могу сделать следующее
auto k = get_key();
auto& v = my_map[k];
В итоге я написал вспомогательную функцию
value_type& get_value(key_type& key)
{
return std::get<0>(my_map.emplace(
std::piecewise_construct,
std::forward_as_tuple(key),
std::forward_as_tuple(args_to_construct_value)
))->second;
}
но производительность была заметно хуже (т.е. конструктор value_type обнаружился в perf), чем следующая версия.
value_type& get_value(key_type& key)
{
auto it = my_map.find(key);
if (it == my_map.end())
return std::get<0>(my_map.emplace(
std::piecewise_construct,
std::forward_as_tuple(key),
std::forward_as_tuple(args_to_construct_value)
))->second;
else
return it->second;
}
Я читаю из std :: unordered_map :: emplace создание объекта это emplace должно создать объект, чтобы увидеть, существует ли он. Но emplace проверяет, существует ли эта пара значений ключа на карте, прежде чем она вернется.
Я использую emplace неправильный путь? Есть ли лучший шаблон, которому я должен следовать:
- Не будет конструировать мой value_type при каждом поиске (как в моем первом методе)
- Не буду проверять, существует ли значение value_type на моей карте дважды (как во втором методе)
Спасибо
Решение
Ваш код, к сожалению, оптимален для стандартной библиотеки, какой она есть в настоящее время.
Проблема в том, что emplace операция предназначена, чтобы избежать копирование, не избежать ненужной конструкции отображаемого типа. С практической точки зрения, что происходит, так это то, что реализация выделяет и создает узел, содержащий карту value_type то есть pair<const Key, T>, а также затем хеширует ключ, чтобы определить, может ли созданный узел быть связан с контейнером; если это сталкивается, то узел удаляется.
Пока hash а также equal_to не слишком дороги, ваш код не должен делать слишком много дополнительной работы.
Альтернативой является использование пользовательского распределителя, который перехватывает конструкцию с 0 аргументами вашего сопоставленного типа; проблема в том, что обнаружить такую конструкцию довольно сложно:
#include <unordered_map>
#include <iostream>
using Key = int;
struct D {
D() = delete;
D(D const&) = delete;
D(D&&) = delete;
D(std::string x, int y) { std::cout << "D(" << x << ", " << y << ")\n"; }
};
template<typename T>
struct A {
using value_type = T;
using pointer = T*;
using const_pointer = T const*;
using reference = T&;
using const_reference = T const&;
template<typename U> struct rebind { using other = A<U>; };
value_type* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
void deallocate(T* c, std::size_t n) { std::allocator<T>().deallocate(c, n); }
template<class C, class...Args> void construct(C* c, Args&&... args) { std::allocator<T>().construct(c, std::forward<Args>(args)...); }
template<class C> void destroy(C* c) { std::allocator<T>().destroy(c); }
std::string x; int y;
A(std::string x, int y): x(std::move(x)), y(y) {}
template<typename U> A(A<U> const& other): x(other.x), y(other.y) {}
template<class C, class...A> void construct(C* c, std::piecewise_construct_t pc, std::tuple<A...> a, std::tuple<>) {
::new((void*)c)C(pc, a, std::tie(x, y)); }
};
int main() {
using UM = std::unordered_map<Key, D, std::hash<Key>, std::equal_to<Key>, A<std::pair<const Key, D>>>;
UM um(0, UM::hasher(), UM::key_equal(), UM::allocator_type("hello", 42));
um[5];
}
Другие решения
Вы могли бы использовать boost::optional<T> для того, чтобы иметь возможность по умолчанию построить сопоставленный тип, а затем назначить инициализированный T к этому позже.
#include <cassert>
#include <unordered_map>
#include <boost/optional.hpp>
struct MappedType
{
explicit MappedType(int) {}
};
int main()
{
std::unordered_map<int, boost::optional<MappedType>> map;
boost::optional<MappedType>& opt = map[0];
assert(!opt.is_initialized());
opt = MappedType(2);
assert(opt.is_initialized());
MappedType& v = opt.get();
}
Джеймс, ты в основном ответил на свой вопрос.
Вы не делаете ничего плохого в любой реализации. emplace просто делает больше работы, чем findособенно когда ключ уже существует в вашем unordered_map,
Если твой get_value вспомогательная функция в основном получает дубликаты, затем вызывает emplace каждый раз, как вы уже заметили, вы получите горячую точку производительности.