c++ - std::vector 的 std::lower_bound 比 std::map::find 慢

Question

我编写了一个类来充当顺序容器( std::vector/std::queue/std::list )的包装器，以具有 std::map 的接口(interface)，用于使用少量小对象时的性能。考虑到已经存在的算法，编码非常简单。这段代码显然是高度从我的完整代码中删减的，但显示了问题。

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 进行了测试, 以及 4 到 128 字节的 POD，使用 MSVC10 的元素范围从 8 到 2000 个。

我希望 (1) 从范围内创建小对象，(2) 随机插入/删除少量小对象，以及 (3) 查找所有对象具有更高的性能。令人惊讶的是，从一个范围内创建所有测试的 vector 明显更快，随机删除速度更快，具体取决于高达约 2048 字节的大小(512 个 4 字节对象或 128 个 16 字节对象， ETC)。然而，最令人震惊的是，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 中)？

[编辑] 我已经确认 std::lower_bound在 std::vector<std::pair<4BYTEPOD,4BYTEPOD>>平均使用比较少于std::map<4BYTEPOD,4BYTEPOD>::find (0-0.25)，但我的实现速度仍然慢了 26%。

[POST-ANSWER-EDIT] 我在 http://ideone.com/41iKt 做了一个 SSCCE去除所有不需要的绒毛，并清楚地表明 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_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> 好很多我觉得调查还没有结束。

附录:

重新思考一下这个练习，我发现了为什么我对谓词类的实现感到不舒服:它是方式复杂的!这可以通过 not 使用 std::enable_if 更简单地完成。更改:这很好地将代码简化为更易于阅读的内容。关键是拿到 key :

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>对象。