c – 为什么std :: vector更快？

概述当我实施Eratosthenes筛选时,我遇到了std :: vector< bool>的问题. ：无法访问原始数据. 所以我决定使用自定义简约实现,我可以访问数据指针. #ifndef LIB_BITS_T_H#define LIB_BITS_T_H#include <algorithm>template <typename B>class bits_t{public: 当我实施Eratosthenes筛选时,我遇到了std :: vector< bool>的问题. ：无法访问原始数据.

所以我决定使用自定义简约实现,我可以访问数据指针.

#ifndef liB_BITS_T_H#define liB_BITS_T_H#include <algorithm>template <typename B>class bits_t{public:    typedef B block_t;    static const size_t block_size = sizeof(block_t) * 8;    block_t* data;    size_t size;    size_t blocks;    class bit_ref{    public:        block_t* const block;        const block_t mask;        bit_ref(block_t& block,const block_t mask) noexcept : block(&block),mask(mask){}        inline voID operator=(bool v) const noexcept{            if(v) *block |= mask;            else  *block &= ~mask;        }        inline operator bool() const noexcept{            return (bool)(*block & mask);        }    };    bits_t() noexcept : data(nullptr){}    voID resize(const size_t n,const bool v) noexcept{        block_t fill = v ? ~block_t(0) : block_t(0);        size = n;        blocks = (n + block_size - 1) / block_size;        data = new block_t[blocks];        std::fill(data,data + blocks,fill);    }    inline block_t& block_at_index(const size_t i) const noexcept{        return data[i / block_size];    }    inline size_t index_in_block(const size_t i) const noexcept{        return i % block_size;    }    inline bit_ref operator[](const size_t i) noexcept{        return bit_ref(block_at_index(i),block_t(1) << index_in_block(i));    }    ~bits_t(){        delete[] data;    }};#endif // liB_BITS_T_H

代码与/usr/include / c /4.7/bits/stl_bvector.h中的代码几乎相同,但速度较慢.

我尝试过优化,

#ifndef liB_BITS_T_H#define liB_BITS_T_H#include <algorithm>template <typename B>class bits_t{const B mask[64] = {    0b0000000000000000000000000000000000000000000000000000000000000001,0b0000000000000000000000000000000000000000000000000000000000000010,0b0000000000000000000000000000000000000000000000000000000000000100,0b0000000000000000000000000000000000000000000000000000000000001000,0b0000000000000000000000000000000000000000000000000000000000010000,0b0000000000000000000000000000000000000000000000000000000000100000,0b0000000000000000000000000000000000000000000000000000000001000000,0b0000000000000000000000000000000000000000000000000000000010000000,0b0000000000000000000000000000000000000000000000000000000100000000,0b0000000000000000000000000000000000000000000000000000001000000000,0b0000000000000000000000000000000000000000000000000000010000000000,0b0000000000000000000000000000000000000000000000000000100000000000,0b0000000000000000000000000000000000000000000000000001000000000000,0b0000000000000000000000000000000000000000000000000010000000000000,0b0000000000000000000000000000000000000000000000000100000000000000,0b0000000000000000000000000000000000000000000000001000000000000000,0b0000000000000000000000000000000000000000000000010000000000000000,0b0000000000000000000000000000000000000000000000100000000000000000,0b0000000000000000000000000000000000000000000001000000000000000000,0b0000000000000000000000000000000000000000000010000000000000000000,0b0000000000000000000000000000000000000000000100000000000000000000,0b0000000000000000000000000000000000000000001000000000000000000000,0b0000000000000000000000000000000000000000010000000000000000000000,0b0000000000000000000000000000000000000000100000000000000000000000,0b0000000000000000000000000000000000000001000000000000000000000000,0b0000000000000000000000000000000000000010000000000000000000000000,0b0000000000000000000000000000000000000100000000000000000000000000,0b0000000000000000000000000000000000001000000000000000000000000000,0b0000000000000000000000000000000000010000000000000000000000000000,0b0000000000000000000000000000000000100000000000000000000000000000,0b0000000000000000000000000000000001000000000000000000000000000000,0b0000000000000000000000000000000010000000000000000000000000000000,0b0000000000000000000000000000000100000000000000000000000000000000,0b0000000000000000000000000000001000000000000000000000000000000000,0b0000000000000000000000000000010000000000000000000000000000000000,0b0000000000000000000000000000100000000000000000000000000000000000,0b0000000000000000000000000001000000000000000000000000000000000000,0b0000000000000000000000000010000000000000000000000000000000000000,0b0000000000000000000000000100000000000000000000000000000000000000,0b0000000000000000000000001000000000000000000000000000000000000000,0b0000000000000000000000010000000000000000000000000000000000000000,0b0000000000000000000000100000000000000000000000000000000000000000,0b0000000000000000000001000000000000000000000000000000000000000000,0b0000000000000000000010000000000000000000000000000000000000000000,0b0000000000000000000100000000000000000000000000000000000000000000,0b0000000000000000001000000000000000000000000000000000000000000000,0b0000000000000000010000000000000000000000000000000000000000000000,0b0000000000000000100000000000000000000000000000000000000000000000,0b0000000000000001000000000000000000000000000000000000000000000000,0b0000000000000010000000000000000000000000000000000000000000000000,0b0000000000000100000000000000000000000000000000000000000000000000,0b0000000000001000000000000000000000000000000000000000000000000000,0b0000000000010000000000000000000000000000000000000000000000000000,0b0000000000100000000000000000000000000000000000000000000000000000,0b0000000001000000000000000000000000000000000000000000000000000000,0b0000000010000000000000000000000000000000000000000000000000000000,0b0000000100000000000000000000000000000000000000000000000000000000,0b0000001000000000000000000000000000000000000000000000000000000000,0b0000010000000000000000000000000000000000000000000000000000000000,0b0000100000000000000000000000000000000000000000000000000000000000,0b0001000000000000000000000000000000000000000000000000000000000000,0b0010000000000000000000000000000000000000000000000000000000000000,0b0100000000000000000000000000000000000000000000000000000000000000,0b1000000000000000000000000000000000000000000000000000000000000000};public:    typedef B block_t;    static const size_t block_size = sizeof(block_t) * 8;    block_t* data;    size_t size;    size_t blocks;    class bit_ref{    public:        block_t* const block;        const block_t mask;        bit_ref(block_t& block,mask[index_in_block(i)]);    }    ~bits_t(){        delete[] data;    }};#endif // liB_BITS_T_H

(用g 4.7 -O3编译)

Eratosthenes筛分算法(33.333.333位)

的std ::矢量< BOol> 19.1s bits_t的<为size_t> 19.9s bits_t的<为size_t> (使用查找表)19.7s ctor调整大小(33.333.333位)dtor 的std ::矢量< BOol> 120毫秒 bits_t的<为size_t> 150毫秒 问题：减速从何而来？

解决方法@H_502_21@ 除了其他一些用户指出的所有问题之外,每次达到当前块限制时,调整大小都会分配更多内存来添加一个块. std :: vector将使缓冲区的大小加倍(所以如果你已经有16个块,那么现在你有32个块).换句话说,他们会做的比你少.

话虽这么说,你没有做必要的删除&复制,这可能会对您的版本产生“积极的”影响……(“正面”影响速度明智,您不会删除旧数据,也不会将其复制到新缓冲区中.)

此外,std :: vector将正确放大缓冲区,从而复制可能已存在于cpu缓存中的数据.对于您的版本,该缓存将丢失,因为您只是忽略每个resize()上的旧缓冲区.

此外,当一个类处理内存缓冲区时,由于某些原因,通常会实现复制和赋值运算符……您也可以考虑使用shared_ptr<>().然后隐藏删除,并且类是一个模板,因此它非常快(它不会添加您自己的版本中没有的任何代码.)

===更新

还有一件事.你是operator []的实现：

inline bit_ref operator[](const size_t i) noexcept{    return bit_ref(block_at_index(i),mask[index_in_block(i)]);}

(旁注：内联不是必需的,因为你在类中编写代码已经意味着你已经确定了内联功能.)

您只提供一个“非常慢”的非const版本,因为它创建了一个子类.您应该尝试实现一个返回bool的const版本,看看它是否会导致您看到的差异大约为3％.

bool operator[](const size_t i) const noexcept{    return (block_at_index(i) & mask[index_in_block(i)]) != 0;}

此外,使用mask []数组也可以减慢速度. (1LL<<(index& 0x3F))应该更快(具有0存储器访问的2个cpu指令).

总结

以上是内存溢出为你收集整理的c – 为什么std :: vector更快？全部内容，希望文章能够帮你解决c – 为什么std :: vector更快？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。