-
-
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