std :: lower_bound对于std :: vector比std :: map :: find慢

Question

我编写了一个类来充当顺序容器(std::vector/ std::queue/ std::list)的包装器std::map,以便在使用少量小对象时具有a的接口.鉴于已有的算法,编码非常简单.这段代码显然是从我的完整代码高度修剪,但显示问题.

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,范围从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应该已经超出了排序,但是在我的生活中不能想到任何理由应该更快.我唯一的想法是谓词在某种程度上减慢了它,但我无法弄清楚如何.所以问题是:如何在一个排序上表现得优于(在MSVC10中)？std::mapmap std::mapstd::mapstd::lower_boundstd::vectorstd::map

[编辑]我已经证实,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的速度慢于map15%.

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>with 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>就是对象的情况下起作用.