станд :: LOWER_BOUND медленнее станд :: вектор, чем станд :: карта :: найти

Question

я написал класс, чтобы действовать в качестве обертки вокруг последовательного контейнера (std::vector/std::queue/std::list), чтобы иметь интерфейс с std::map, для при использовании небольшого количества небольших объектов. Кодирование было чрезвычайно простым с учетом уже существующих алгоритмов. Этот код, очевидно, высокий урезанный из моего полного кода, но показывает проблему.

template <class key_, 
      class mapped_, 
      class traits_ = std::less<key_>, 
      class undertype_ = std::vector<std::pair<key_,mapped_> > 
     > 
class associative 
{ 
public: 
    typedef traits_ key_compare; 
    typedef key_ key_type; 
    typedef mapped_ mapped_type; 
    typedef std::pair<const key_type, mapped_type> value_type; 
    typedef typename undertype_::allocator_type allocator_type; 
    typedef typename allocator_type::template rebind<value_type>::other value_allocator_type; 
    typedef typename undertype_::const_iterator const_iterator; 

    class value_compare { 
     key_compare pred_; 
    public: 
     inline value_compare(key_compare pred=key_compare()) : pred_(pred) {} 
     inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);} 
     inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);} 
     inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);} 
     inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);} 
     inline key_compare key_comp() const {return pred_;} 
    }; 
    class iterator { 
    public:  
     typedef typename value_allocator_type::difference_type difference_type; 
     typedef typename value_allocator_type::value_type value_type; 
     typedef typename value_allocator_type::reference reference; 
     typedef typename value_allocator_type::pointer pointer; 
     typedef std::bidirectional_iterator_tag iterator_category; 
     inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {} 
    inline reference operator*() const { return reinterpret_cast<reference>(*data);} 
     inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));} 
     operator const_iterator&() const {return data;} 
    protected: 
     typename undertype_::iterator data; 
    }; 

    template<class input_iterator> 
    inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
    {if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);} 

inline iterator find(const key_type& key) { 
    iterator i = std::lower_bound(internal_.begin(), internal_.end(), key, comp_); 
    return (comp_(key,*i) ? internal_.end() : i); 
} 

protected: 
    undertype_ internal_; 
    value_compare comp_; 
}; 

SSCCE в http://ideone.com/Ufn7r, полный код на http://ideone.com/MQr0Z (примечание: в результате раз IdeOne весьма беспорядочным, вероятно, из-за нагрузки на сервер, и не ясно показывают результаты в вопросе)

Я протестированные с std::string , и POD от 4 до 128 байтов, от 8 до 2000 элементов с MSVC10.

Я ожидал более высокой производительности для (1) создания из диапазона для небольших объектов, (2) случайного ввода/стирания для небольшого числа мелких объектов и (3) поиска для всех объектов. Удивительно, но вектор был значительно быстрее для создания из диапазона для всех тестов и быстрее для случайного стирания в зависимости от размера до примерно 2048 байт (512 4-байтовых объектов или 128 16-байтовых объектов и т. Д.). Однако самым шокирующим было то, что std::vector с использованием std::lower_bound был медленнее, чем std::map::find для всех POD. Разница была минимальной для 4 и 8-байтовых POD, но для 128-байтовых POD std::vector был на 36% медленнее! Однако, для std::string, std::vector был в среднем на 6% быстрее.

Я чувствую std::lower_bound на отсортированный std::vector должен обогнал std::map из-за лучший кэш локальности/меньший объем памяти, а так как map может быть несовершенным сбалансирован, или в худшем случае он должен матчstd::map, но не может для жизни меня думать о какой-либо причине, что std::map должен быть быстрее. Моя единственная мысль - предикат как-то замедляет его, но я не могу понять, как это сделать. Так что вопрос: Как могло случиться так, что std::lower_bound на сортированном std::vector превзойдет std::map (в MSVC10)?

[EDIT] Я подтвердил, что std::lower_bound на std::vector<std::pair<4BYTEPOD,4BYTEPOD>> использует меньше сравнений чем в среднем std::map<4BYTEPOD,4BYTEPOD>::find (по 0-0,25), но моя реализация еще до 26% медленнее.

[ПОСТ-ОТВЕТ-EDIT] Я сделал SSCCE в http://ideone.com/41iKt, который удаляет весь ненужный пух, и ясно показывает, что find на отсортированном vector медленнее, чем у map, на ~ 15%.

Answer 1

Это несколько более интересный орех, чтобы взломать! Прежде чем обсуждать мои выводы до сих пор, позвольте мне указать, что функция associative::find() ведет себя по-разному с std::map::find(): если ключ не найден, он возвращает нижнюю границу, а последний возвращает end(). Чтобы это исправить, associative::find() необходимо изменить, чтобы стать чем-то вроде этого:

auto rc = std::lower_bound(this->internal_.begin(), this->internal_.end(), key, this->comp_); 
return rc != this->internal_.end() && !this->comp_(key, rc->first)? rc: this->internal_.end(); 

Теперь, когда мы более склонны сравнивать яблоки с яблоками (я не проверял, если логика действительно правильно сейчас), пойдем чтобы исследовать работу. Я не совсем уверен, что подход, используемый для тестирования производительности, действительно удерживает воду, но я придерживаюсь этого на данный момент, и я мог бы определенно улучшить производительность контейнера associative. Я не думаю, что я полностью нашел все проблемы производительности в коде, но, по крайней мере, добился определенного прогресса. Самое большое - заметить, что функция сравнения, используемая в associative, довольно плоха, потому что она продолжает делать копии. Это помещает этот контейнер в невыгодное положение. Если вы сейчас проверяете компаратор, вы, вероятно, не видите его, потому что похоже, что этот компаратор -, проходящий по ссылке! Проблема на самом деле довольно тонкая: базовый контейнер имеет value_typestd::pair<key_type, mapped_type>, но компаратор принимает std::pair<key_type const, mapped_type> в качестве аргумента! Фиксация этого, похоже, придает ассоциативному контейнеру довольно много повышения производительности.

Чтобы реализовать класс компаратор, который не имеет возможности потерпеть неудачу сопоставляя аргументы именно я использую простой помощник для обнаружения, если тип является std::pair<L, R>:

template <typename>    struct is_pair     { enum { value = false }; }; 
template <typename F, typename S> struct is_pair<std::pair<F, S>> { enum { value = true }; }; 

...и затем я заменил компаратор таким, немного более сложным: один из них:

class value_compare { 
    key_compare pred_; 
public: 
    inline value_compare(key_compare pred=key_compare()) : pred_(pred) {} 
    template <typename L, typename R> 
    inline typename std::enable_if<is_pair<L>::value && is_pair<R>::value, bool>::type 
    operator()(L const& left, R const& right) const { 
     return pred_(left.first,right.first); 
    } 
    template <typename L, typename R> 
    inline typename std::enable_if<is_pair<L>::value && !is_pair<R>::value, bool>::type 
    operator()(L const& left, R const& right) const { 
     return pred_(left.first,right); 
    } 
    template <typename L, typename R> 
    inline typename std::enable_if<!is_pair<L>::value && is_pair<R>::value, bool>::type 
    operator()(L const& left, R const& right) const { 
     return pred_(left,right.first); 
    } 
    template <typename L, typename R> 
    inline typename std::enable_if<!is_pair<L>::value && !is_pair<R>::value, bool>::type 
    operator()(L const& left, R const& right) const { 
     return pred_(left,right); 
    } 
    inline key_compare key_comp() const {return pred_;} 
}; 

Как правило, эти два подхода приближаются друг к другу. Учитывая, что я ожидаю, что подход std::vector<T> с lower_bound() должен быть намного лучше, чем с использованием std::map<K, T>. Я считаю, что расследование еще не закончено.

Добавление:

Переосмысление упражнения немного больше я пятнистый, почему я чувствовал себя неуютно с реализацией класса предикатов: это путь к сложному! Это можно сделать намного проще на не с использованием std::enable_if для изменения: это красиво уменьшает код до чего-то, что намного легче читать. Ключ, чтобы получить ключ:

template <typename Key> 
Key const& get_key(Key const& value)     { return value; } 
template <typename Key, typename Value> 
Key const& get_key(std::pair<Key, Value> const& pair) { return pair.first; } 

С этой реализации, чтобы заполучить «ключ» от любого значения или пары значений, объект предикат может только определить один очень простой оператор вызова функции:

template <typename L, typename R> 
bool operator()(L const& l, R const& r) 
{ 
    return this->pred_(get_key<key_type>(l), get_key<key_type>(r)); 
} 

Существует небольшая хитрость в этом, а также, хотя: ожидаемые key_type потребности должны быть переданы функции get_key(). Без этого предикат не будет работать в тех случаях, когда key_type сам по себе является объектами std::pair<F, S>.

Answer 2

У меня есть предположение. Во-первых, lower_boundобязательно do log2 (n) сравнение, независимо. Это означает, что никогда не будет времени (например, для find), когда он может остановиться раньше. Во-вторых, для типов данных, которые больше определенного размера, должна быть операция умножения, задействованная в любой арифметике указателя для вектора. В то время как для карты это просто нагрузка указателя на 4 (или 8 на 64-разрядное) значение байта из памяти.

В x86 есть несколько полезных инструкций по очень быстрому умножению по степеням двух во время индексирующих вычислений. Но они работают только для малых мощностей по два, поскольку они предназначены для индексирования массивов целочисленных объектов. Для больших чисел он должен фактически использовать инструкцию умножения с целым числом, которая значительно медленнее.

Когда вы делаете lower_bound, вы должны сделать ровно log2 (n) из этих множителей. Но для find его можно обрезать меньшим числом для половины значений. Это означает, что их эффект будет намного больше для lower_bound, чем любой другой метод.

Как в стороне ... по-моему, ::std::map должен быть реализован как B-дерево, где каждый узел является страницей по размеру. Виртуальная память устанавливает это так, что в основном каждая программа, имеющая значительно большую структуру данных, будет иметь части этой структуры, выгружаемые под давлением памяти. Если каждый узел хранит только одно значение, рискует создать почти худший случай, когда вы должны размещать страницу на всей странице для каждого сравнения для глубины log2 (n) , где, если вы использовали b-дерево, ваш худший пейджинговый случай be logx (n) страниц, где x - это количество значений для каждого узла.

Это также имеет хороший побочный эффект уменьшения плохих последствий границ линии кэша. Будет LCM размера (ключа, значения) кортежа и размера кеша. Наличие нескольких пар (ключ, значение) в узле устанавливает его таким образом, чтобы этот LCM был гораздо более вероятным, и X-пары будут принимать ровно Y строк кеша. Но если каждый узел содержит только одну пару, это в принципе никогда не произойдет, если размер узла не будет точно кратным размеру кеш-строки.