벡터 <T> :: 미리 정의 된 생성자에 push_back이 사용됩니까?

Question

나는 내 인식이 실제로 사실인지 묻기 위해 여기에있다. 원래 vector<T> v(size_t someSize, T init_value)을 정의하는 것이 vector<T>::push_back 대신 vector<T>::reserve과 같은 함수를 호출한다고 생각했습니다. 이것에 관한 몇 가지 토론을 여기에서 보았습니다 : std::vector push_back is bottleneck, 그러나 이것은 약간 다른 아이디어입니다.

일부 실험을 실행하면 vector<T> v(size_t someSize, T init_value)이 모두 ::push_back입니다. 사실입니까? uftrace (https://github.com/namhyung/uftrace)을 사용하는 다음 보고서가 있습니다. vector<T>::reserve도 결국 vector<t>::push_back에

 Avg total Min total Max total Function 
========== ========== ========== ==================================== 
858.323 ms 858.323 ms 858.323 ms main 
618.245 ms 618.245 ms 618.245 ms sortKaway 
234.795 ms 234.795 ms 234.795 ms std::sort 
72.752 us 72.752 us 72.752 us std::vector::_M_fill_initialize 
65.788 us 49.551 us 82.026 us std::vector::vector 
20.292 us 11.387 us 68.629 us std::vector::_M_emplace_back_aux 
18.722 us 17.263 us 20.181 us std::equal 
18.472 us 18.472 us 18.472 us std::vector::~vector 
17.891 us 10.002 us 102.079 us std::vector::push_back // push_back?! 

를 호출합니까? vector에 대한 더 빠른 버전이 있습니까?

---

위의 글은 원래 게시물이었습니다. 몇 가지 코멘트를 한 후, 나는 간단한 버전을 테스트했고, 나는 완전히 착각되었다는 것을 깨달았다.

#include <vector> 
#include <functional> 
#include <queue> 
#include <cassert> 
using namespace std; // for the time being 

int main() { 
    vector<int> v(10, 0); 

    return 0; 
} 

이 실제로 std::vector<T>::push_back을 포함하지 않는 다음에 발생합니다.

# Function Call Graph for 'main' (session: 9ce7f6bb33885ff7) 
    =============== BACKTRACE =============== 
    backtrace #0: hit 1, time 12.710 us 
    [0] main (0x4009c6) 

    ========== FUNCTION CALL GRAPH ========== 
    12.710 us : (1) main 
    0.591 us : +-(1) std::allocator::allocator 
    0.096 us : | (1) __gnu_cxx::new_allocator::new_allocator 
       : | 
    6.880 us : +-(1) std::vector::vector 
    4.338 us : | +-(1) std::_Vector_base::_Vector_base 
    0.680 us : | | +-(1) std::_Vector_base::_Vector_impl::_Vector_impl 
    0.445 us : | | | (1) std::allocator::allocator 
    0.095 us : | | | (1) __gnu_cxx::new_allocator::new_allocator 
       : | | | 
    3.294 us : | | +-(1) std::_Vector_base::_M_create_storage 
    3.073 us : | | (1) std::_Vector_base::_M_allocate 
    2.849 us : | | (1) std::allocator_traits::allocate 
    2.623 us : | | (1) __gnu_cxx::new_allocator::allocate 
    0.095 us : | |  +-(1) __gnu_cxx::new_allocator::max_size 
       : | |  | 
    1.867 us : | |  +-(1) operator new 
       : | | 
    2.183 us : | +-(1) std::vector::_M_fill_initialize 
    0.095 us : |  +-(1) std::_Vector_base::_M_get_Tp_allocator 
       : |  | 
    1.660 us : |  +-(1) std::__uninitialized_fill_n_a 
    1.441 us : |  (1) std::uninitialized_fill_n 
    1.215 us : |  (1) std::__uninitialized_fill_n::__uninit_fill_n 
    0.988 us : |  (1) std::fill_n 
    0.445 us : |  +-(1) std::__niter_base 
    0.096 us : |  | (1) std::_Iter_base::_S_base 
       : |  | 
    0.133 us : |  +-(1) std::__fill_n_a 

죄송합니다. 예, 라이브러리 구현은 예상대로 작동하지만 initial size으로 생성 된 경우 push_back은 포함되지 않습니다.

Answer 1

너는 너 자신의 질문에 대답 한 것처럼 보입니다! 나는 잠시 혼란 스러웠다. 그냥 가설 적으로, 과 push_backs을 사용하는 vector's 채우기 생성자의 다소 모호한 경우를 상상할 수 있지만, GNU 표준 라이브러리의 GCC와 함께 제공되는 것과 같은 고품질 구현을 좋아하지는 않습니다. 나는 가상의 방법으로, 애매한 벡터 구현이 이런 식으로 구현 될 수는 있지만, 괜찮은 구현을 위해서는 실제로는 거의 불가능하다고 말하고 싶다.

반대로 이것은 거의 20 년 전 이었지만 성능을 맞추기 위해 std::vector 버전을 구현하려고했습니다. 이것은 약간의 멍청한 운동이 아니었지만 유혹은 소프트웨어 개발 키트가 있었고 기본 C++ 컨테이너를 사용하기를 원했기 때문에 유인은 사람들이 다른 소프트웨어를 사용하여 플러그인을 작성하도록 허용했습니다. 컴파일러 (그리고 다른 표준 라이브러리 구현체)를 사용하는 것보다 훨씬 쉽습니다. 따라서 우리 버전이 플러그인 작성자와 일치하지 않을 수 있으므로 std::vector을 안전하게 사용할 수 없습니다. 우리는 마지 못해 SDK 용 자체 컨테이너를 굴려야했습니다.

대신에 특히 std::vector은 매우 어려웠습니다. 특히 사소한 ctors와 dtors가있는 일반 오래된 데이터 유형의 경우에는 매우 효율적이었습니다. 다시 이것은 10 년 전 이었지만 MSVC 5 또는 6에서 vector<int>으로 채우기 생성자를 사용하는 것이 실제로는 동일한 분해로 번역 된 것으로 보았습니다. 즉, 순진한 버전을 그냥 반복하고 배치를 사용하는 방식으로 memset을 사용했습니다. POD인지 아닌지에 관계없이 새로운 기능을 선보였습니다. 범위 ctor는 또한 효과적으로 POD에 대해 매우 빠른 memcpy으로 변환됩니다. 그리고 바로 그게 바로 저에게 적어도 저를 위해 이길 수있는 벡터를 만들었던 이유입니다. 유형 특성 및 특수 케이스 POD에 깊이 관여하지 않고서도 POD에 대한 벡터의 성능을 실제로 일치시킬 수 없었습니다. UDT와 일치시킬 수는 있지만 성능에 중요한 코드의 대부분은 POD를 사용하는 경향이있었습니다.

오늘의 인기있는 벡터 구현은 내가 그 테스트를 수행했을 때만 큼 효율적일뿐 아니라 벡터 구현이 가장 저주받을 수 있다는 확신을 주려고합니다. 마지막으로해야 할 일은 push_backs을 사용하여 fill ctors 또는 range ctors를 구현하는 것입니다.