我天，vector竟然成了性能瓶颈

程序员的园

发布于 2024-07-18 13:02:11

6300

代码可运行

文章被收录于专栏：程序员的园——原创文章程序员的园——原创文章

运行总次数：0

代码可运行

如果知道我会死在哪里，那我将永远不去那个地方 -查理芒格

背景介绍

今天朋友遇到这样一个问题，周期性的CPU占比飙升，尽管已经使用了线程池，CPU占比仍旧很高，并且是周期性的。

最后通过VS的诊断工具，通过CPU使用率定位到，如下的代码，占了50%的CPU，问题代码简化如下

void init_vector()
{
  std::vector<float> v;
  for (int i =0; i< 4800; i++)
  {
    v.push_back(float(i)/4800);
  }
}

突然想起来了，面试中常问的数据结构的知识，突然发现面试不再是“面试造航母工作拧螺丝”了，面试中的知识在工作中是会遇到的。

问题分析

理论知识如下：std::vector涉及到内存动态分配，凡是涉及到向std::vector中添加元素或修改std::vector大小时，只要现有的capacity不再满足内存大小时便涉及到重新分配内存。

01、开辟新内存

 _CONSTEXPR20_CONTAINER size_type _Calculate_growth(const size_type _Newsize) const {
    // given _Oldcapacity and _Newsize, calculate geometric growth
    const size_type _Oldcapacity = capacity();
    const auto _Max              = max_size();

    if (_Oldcapacity > _Max - _Oldcapacity / 2) {
        return _Max; // geometric growth would overflow
    }

    const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

    if (_Geometric < _Newsize) {
        return _Newsize; // geometric growth would be insufficient
    }

    return _Geometric; // geometric growth is sufficient
}

由如上源码可知：std::vector每次以1.5倍扩张

02、拷贝/移动旧内存

 _CONSTEXPR20_CONTAINER void _Umove_if_noexcept(pointer _First, pointer _Last, pointer _Dest) {
// move_if_noexcept [_First, _Last) to raw _Dest, using allocator
_Umove_if_noexcept1(_First, _Last, _Dest,
    bool_constant<disjunction_v<is_nothrow_move_constructible<_Ty>, negation<is_copy_constructible<_Ty>>>>{});
}

旧内存到新内存取决于是否存在noexcept型的移动构造函数，当存在noexcept型的移动构造函数时，使用移动构造函数，否则使用拷贝构造函数。

03、释放旧内存

_CONSTEXPR20_CONTAINER void _Change_array(
const pointer _Newvec, const size_type _Newsize, const size_type _Newcapacity) 
{
    // orphan all iterators, discard old array, acquire new array
    auto& _My_data    = _Mypair._Myval2;
    pointer& _Myfirst = _My_data._Myfirst;
    pointer& _Mylast  = _My_data._Mylast;
    pointer& _Myend   = _My_data._Myend;

    _My_data._Orphan_all();

    if (_Myfirst) { // destroy and deallocate old array
        _Destroy(_Myfirst, _Mylast);
        _Getal().deallocate(_Myfirst, static_cast<size_type>(_Myend - _Myfirst));
    }

    _Myfirst = _Newvec;
    _Mylast  = _Newvec + _Newsize;
    _Myend   = _Newvec + _Newcapacity;
}

释放旧内存。

解决问题

综合如上分析，当涉及到重新分配内存时会导致运算量的增加，那么如何减少如上操作呢，分配足够大的内存即可。修改方案如下：

std::vector<Person> v;
v.resize(10);
std::cout << "\n";
for (int i =0; i< 10; i++)
{
    std::cout << "\n";
    Person p;
    v[i]=p;
}

附录

针对如上问题分析环节可以自己书写代码进行验证性测试

class Person
{
public:
  Person()
  {
    std::cout<<"construct" << "\t";
  }

  ~Person()
  {
    std::cout << "destruct" << "\t";
  }
  Person& operator=(const Person&)
  {
    return *this;
  }

  Person& operator=(const Person&&)noexcept
  {
    return *this;
  }

  Person(const Person& p)
  {
    std::cout << "copy" <<"\t";
  }

  Person(const Person&& p)noexcept
  {
    std::cout << "move"  <<"\t";
  }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除

vector