Std:: lower_bound медленнее для std::vector, чем std:: map:: find

Ответ 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_type std::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> объектов.

Ответ 2

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

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

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

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

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