-
-
Save AlexEne/2d25aa0f1d3a39dcb27d to your computer and use it in GitHub Desktop.
#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); | |
} |
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
Visual Studio 2015 Update1:
RValueRef vector insert: 4305.17 ms
Normal vector insert:2975.44 ms
Visual Studio 2012 Update 5:
RValueRef insert:9463.95 ms
Normal insert:3287.33 ms