Simple vector efficiency question

Discussion in 'C++' started by crea, May 6, 2011.

  1. crea

    crea Guest

    Simple question: Is STL vector always as efficient way as using normal
    c-dynamical arrays?

    So is

    vector<int> ve1;
    ve1.reserve(100);

    always as fast/efficient than

    int* ve2 = new int[100];

    ?

    and other operations as well?

    Do you always use vector instead of normal c-arrays? in what situations not?
    crea, May 6, 2011
    #1
    1. Advertising

  2. On Fri, 6 May 2011 17:53:32 +0100, "crea" <> wrote:
    > Simple question: Is STL vector always as efficient way as using

    normal
    > c-dynamical arrays?
    > So is
    > vector<int> ve1;
    > ve1.reserve(100);
    > always as fast/efficient than
    > int* ve2 = new int[100];
    > ?
    > and other operations as well?
    > Do you always use vector instead of normal c-arrays? in what

    situations not?
    I use either vector or std/boost::array depending on whether the
    length is constant or not. I don't know that it is always as
    efficient, but it is safer and the efficiencies should be close.
    Garrett Hartshaw, May 6, 2011
    #2
    1. Advertising

  3. crea

    Kai-Uwe Bux Guest

    crea wrote:

    > Simple question: Is STL vector always as efficient way as using normal
    > c-dynamical arrays?
    >
    > So is
    >
    > vector<int> ve1;
    > ve1.reserve(100);
    >
    > always as fast/efficient than
    >
    > int* ve2 = new int[100];
    >
    > ?
    >
    > and other operations as well?


    The operations to consider allocation/construction and element access. As
    for element access, this a compiler issue: the compiler has to inline the
    call to operator[], but I have yet to see a case where the compiler does not
    do that.

    For allocation/construction, the case is more involved since vector<> is
    templated on an allocator type. Hence, it does not necessarily use the same
    allocation function as new. Whether it is more, less, or equally efficient
    cannot be said in general. If it turns out to that allocation of vector
    objects is a bottleneck, I would tamper with the allocator and not switch to
    dynamically allocated arrays: after all, with the infrastructure of vector<>
    in place, trying out various allocators is easy. Also, replacing vector<> by
    deque<> (often possible) is easy (usually just changing a typedef); but
    rewriting the code to use raw arrays is more work.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, May 6, 2011
    #3
  4. On May 6, 6:53 pm, "crea" <> wrote:
    > Simple question: Is STL vector always as efficient way as using normal
    > c-dynamical arrays?
    >
    > So is
    >
    > vector<int> ve1;
    > ve1.reserve(100);
    >
    > always as fast/efficient than
    >
    > int* ve2 = new int[100];
    >
    > ?
    >
    > and other operations as well?
    >
    > Do you always use vector instead of normal c-arrays? in what situations not?


    I found that for very large arrays of built-in types, the default
    initialization can be very time consuming. If all you need is an
    uninitialized array, maybe to pass as an output buffer to a C style
    function, then raw arrays may be much more efficient. I tried to make
    a custom allocator that doesn't default initialize but that was not
    possible given the interface between a container and its allocator.

    I then made a dynamic_array STL-style container that's just a wrapper
    for new T[]/delete with appropriate copy semantics and begin()/end()/
    size() etc. This gives me the convenience of the STL containers with
    the low level efficiency of raw arrays.

    Gert-Jan
    Gert-Jan de Vos, May 6, 2011
    #4
  5. crea

    Pavel Guest

    Gert-Jan de Vos wrote:
    > On May 6, 6:53 pm, "crea"<> wrote:
    >> Simple question: Is STL vector always as efficient way as using normal
    >> c-dynamical arrays?
    >>
    >> So is
    >>
    >> vector<int> ve1;
    >> ve1.reserve(100);
    >>
    >> always as fast/efficient than
    >>
    >> int* ve2 = new int[100];
    >>
    >> ?
    >>
    >> and other operations as well?
    >>
    >> Do you always use vector instead of normal c-arrays? in what situations not?

    >
    > I found that for very large arrays of built-in types, the default
    > initialization can be very time consuming. If all you need is an
    > uninitialized array, maybe to pass as an output buffer to a C style
    > function, then raw arrays may be much more efficient. I tried to make
    > a custom allocator that doesn't default initialize but that was not
    > possible given the interface between a container and its allocator.
    >
    > I then made a dynamic_array STL-style container that's just a wrapper
    > for new T[]/delete with appropriate copy semantics and begin()/end()/
    > size() etc. This gives me the convenience of the STL containers with
    > the low level efficiency of raw arrays.
    >
    > Gert-Jan

    The code in the example does not initialize the elements. Of course, they can't
    be used either before initialization as opposed to native array (ve1.size()
    after the code fragment above is still 0). In this regard, native array is less
    prohibitive which usually help performance but leaves more opportunities to err
    (a trade-off, as it often is in programming).

    To answer the original question: it depends. For the case where one uses many
    small vectors, the overhead (in both size and space) may be significant. For
    working with big arrays that are to be filled up sequentially, it is often
    negligible. When the final array size is known before it has to be created but
    is not a compile-time constant and can be significant, vector may be the only
    reasonable choice (using array may still be possible but involve significant
    memory overhead for allocating the maximum possible size).

    HTH
    -Pavel
    Pavel, May 7, 2011
    #5
  6. Gert-Jan de Vos <> wrote:
    > I found that for very large arrays of built-in types, the default
    > initialization can be very time consuming.


    That seems to indeed be the case.

    You could, of course, use just reserve() instead of actually
    resizing the vector and then access it, in which case there's no
    initialization overhead. Of course that presents a multitude of
    problems, such as size() not giving the proper value and most
    compilers giving you an assertion failure in debug mode. (It might
    probably even be UB as per the standard.)
    Juha Nieminen, May 7, 2011
    #6
  7. crea

    Öö Tiib Guest

    On May 6, 11:00 pm, Gert-Jan de Vos <gert-
    > wrote:
    > On May 6, 6:53 pm, "crea" <> wrote:
    >
    >
    >
    >
    >
    > > Simple question: Is STL vector always as efficient way as using normal
    > > c-dynamical arrays?

    >
    > > So is

    >
    > > vector<int> ve1;
    > > ve1.reserve(100);

    >
    > > always as fast/efficient than

    >
    > > int* ve2 = new int[100];

    >
    > > ?

    >
    > > and other operations as well?

    >
    > > Do you always use vector instead of normal c-arrays? in what situationsnot?

    >
    > I found that for very large arrays of built-in types, the default
    > initialization can be very time consuming. If all you need is an
    > uninitialized array, maybe to pass as an output buffer to a C style
    > function, then raw arrays may be much more efficient.


    It is perhaps because lazy programmer does not know how large buffer
    is needed for something and so allocates absurdly large one. Lazy
    operating system on its order just gives back virtual address to
    nothing.

    The C function under discussion does write only into fraction of that
    virtual buffer and so operating system really provides real memory
    pages only for that fraction. Vector however writes diligently to
    everything and so the result is lot slower.

    The real problem is still that "maybe it will fit" buffer allocation
    antipattern and not the vector.
    Öö Tiib, May 7, 2011
    #7
  8. crea

    James Kanze Guest

    On May 6, 5:53 pm, "crea" <> wrote:
    > Simple question: Is STL vector always as efficient way as using normal
    > c-dynamical arrays?


    > So is


    > vector<int> ve1;
    > ve1.reserve(100);


    > always as fast/efficient than


    > int* ve2 = new int[100];


    > ?


    It's always close enough.

    > and other operations as well?


    > Do you always use vector instead of normal c-arrays? in what situations not?


    Two cases, at least, where C style arrays are preferred:

    1. Static constant arrays of POD types, initialized using
    agglomerate initialization. First, because they avoid order
    of initialization problems (since static initialization can
    be used), and second, because the compiler can work out the
    size of the array itself from the initializers---you don't
    have to count.

    2. For small, fixed length arrays which are used in great
    number, e.g. something like Point3D (where double[3] is
    probably preferrable over std::vector). In such cases,
    there's very little advantage for std::vector, and the
    dynamic allocations (e.g. if you write something like
    std::vector<Point3D> array(100000)) can kill you.

    Otherwise... We do a lot of time critical numbers crunching on
    more or less large vectors (from about 30 elements up), we use
    std::vector exclusively, and it's never caused a performance
    problem.

    --
    James Kanze
    James Kanze, May 8, 2011
    #8
  9. crea

    Jorgen Grahn Guest

    On Sat, 2011-05-07, Juha Nieminen wrote:
    > Gert-Jan de Vos <> wrote:
    >> I found that for very large arrays of built-in types, the default
    >> initialization can be very time consuming.

    >
    > That seems to indeed be the case.
    >
    > You could, of course, use just reserve() instead of actually
    > resizing the vector and then access it, in which case there's no
    > initialization overhead. Of course that presents a multitude of
    > problems, such as size() not giving the proper value and most
    > compilers giving you an assertion failure in debug mode. (It might
    > probably even be UB as per the standard.)


    You mean e.g.

    std::vector<int> foo;
    foo.reserve(1000);
    foo[42] = 96;

    That is definitely not valid code, and IMO not a reasonable
    optimization technique.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 8, 2011
    #9
  10. crea

    Paul Guest

    "crea" <> wrote in message
    news:NIVwp.5850$2...
    > Simple question: Is STL vector always as efficient way as using normal
    > c-dynamical arrays?
    >
    > So is
    >
    > vector<int> ve1;
    > ve1.reserve(100);
    >
    > always as fast/efficient than
    >
    > int* ve2 = new int[100];
    >
    > ?
    >
    > and other operations as well?
    >
    > Do you always use vector instead of normal c-arrays? in what situations
    > not?
    >
    >

    I don't think vectors are as efficient when it comes to multi dimensional
    arrays.
    Paul, May 8, 2011
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jason
    Replies:
    10
    Views:
    647
    EventHelix.com
    Dec 5, 2003
  2. pmatos
    Replies:
    6
    Views:
    23,777
  3. Replies:
    8
    Views:
    1,913
    Csaba
    Feb 18, 2006
  4. Javier
    Replies:
    2
    Views:
    558
    James Kanze
    Sep 4, 2007
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    356
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page