Skip to content

Instantly share code, notes, and snippets.

@AlexEne

AlexEne/vector_insert_bug.cpp

Last active February 4, 2016 11:54
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save AlexEne/2d25aa0f1d3a39dcb27d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save AlexEne/2d25aa0f1d3a39dcb27d to your computer and use it in GitHub Desktop.
Download ZIP
STL vector bug
Raw
vector_insert_bug.cpp
#include <chrono>
#include <vector>
using namespace std;
class Timer
{
public:
Timer() : beg_(clock_::now()) {}
void reset() { beg_ = clock_::now(); }
double elapsed() const {
return std::chrono::duration_cast<ms_>
(clock_::now() - beg_).count();
}
private:
typedef std::chrono::high_resolution_clock clock_;
typedef std::chrono::duration<double, std::milli> ms_;
std::chrono::time_point<clock_> beg_;
};
struct EpicStruct
{
#define EpicStruct_SIZE 4
char m_memory[EpicStruct_SIZE];
EpicStruct()
{
}
explicit EpicStruct(size_t val)
{
memset(m_memory, val % 127, sizeof(m_memory));
}
void print()
{
for( int i = 0; i < EpicStruct_SIZE; ++i)
printf("%d", m_memory[i]);
}
};
#define COUNT 100000
double insert_stl_version_rvalueref()
{
Timer tmr;
vector<EpicStruct> vec;
for(size_t i = 0; i < COUNT; ++i)
{
vec.insert(vec.begin(), EpicStruct(i));
}
return tmr.elapsed();
}
double insert_normal()
{
Timer tmr;
vector<EpicStruct> vec;
for(size_t i = 0; i < COUNT; ++i)
{
EpicStruct tmp = EpicStruct(i);
vec.insert(vec.begin(), tmp);
}
return tmr.elapsed();
}
int main()
{
double t = insert_stl_version_rvalueref();
printf("RValueRef insert:%.2f ms\n", t);
t = insert_normal();
printf("Normal insert:%.2f ms\n", t);
}
@AlexEne
Copy link
Author

AlexEne commented Feb 4, 2016

This is because the insert(iterator, T&& value) version does the following:
push_back(value);
rotate(it, end()-1, end())

In VS2015 rotate does the following:
template inline
_RanIt _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
random_access_iterator_tag)
{ // rotate [_First, _Last), random-access iterators
_STD reverse(_First, _Mid);
_STD reverse(_Mid, _Last);
_STD reverse(_First, _Last);
return (_First + (_Last - _Mid));
}

// TEMPLATE FUNCTION reverse
template inline
void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
{ // reverse elements in [_First, _Last), bidirectional iterators
for (; _First != _Last && _First != --_Last; ++_First)
_STD iter_swap(_First, _Last);
}

The reverse function is not cache friendly and that is why the time difference appears :)
More info and tests can be found here:
https://github.com/AlexEne/Presentations-2016/blob/master/Memory/list_vs_vector.cpp

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment