Using vector instead of an dynamically declared array

Discussion in 'C++' started by The Cool Giraffe, Feb 15, 2007.

  1. I got a hint recently (guess where, hehe) and was directly
    pointed to the vector class. Now, i have no issues using
    that way but i'm concerned about the performance issue.

    Which is fastest (significantly faster, preferable in any
    way, etc.) in the following list.

    a) std::vector?

    b) a struct with an array and an integer?
    struct {int* arr = new arr[m]; int m}

    c) saving the int as an instance variable?
    int* arr = new arr[m];
    this.arrSize = m;

    In the program, there will be a lot of looping and iterating
    and i'm supposed to use C++, if that's of any importance to
    answer the abc-questions.

    --
    Vänligen Kerstin Viltersten
    (The Cool Giraffe)
     
    The Cool Giraffe, Feb 15, 2007
    #1
    1. Advertising

  2. The Cool Giraffe

    Gavin Deane Guest

    On 15 Feb, 08:59, "The Cool Giraffe" <> wrote:
    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.


    May I ask why? You're not thinking about premature optimisation are
    you?

    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;


    The only way to know which of a these is faster is to measure the
    speed of all of them. And bear in mind that compilers have switches
    and settings that can alter the results so you'll need to know how to
    set up your particular compiler so as not to bias the results. The
    implication there is that your results on one compiler may not be
    applicable to a different compiler.

    Also remember that, while performance is usually something you
    shouldn't be worrying about most of the time (or more specifically,
    unless and until you know you've got a problem), there are times when
    it does matter. The people who wrote your implementation of
    std::vector knew that so it will be written carefully so as not to use
    time or space unnecessarily. And, of course, it has been subject to a
    huge amount of testing and debugging already (by anybody who has used
    the same implementation as you) which won't be true for any hand-
    rolled replacement you write.

    Rather than asking yourself which is fastest of your three options,
    ask yourself which is least likely to result in code with bugs in it.

    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.


    If you're supposed to use C++, use std::vector. Concentrate on writing
    code in the way that gets you to a clear, correct program the fastest.
    Your time is the most important resource to optimise. Reinventing the
    wheel isn't the way to do that.
    http://www.parashift.com/c -faq-lite/containers.html#faq-34.1

    Gavin Deane
     
    Gavin Deane, Feb 15, 2007
    #2
    1. Advertising

  3. The Cool Giraffe

    John Ratliff Guest

    The Cool Giraffe wrote:
    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.
    >
    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;
    >
    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.
    >


    All three solutions are equally fast. There is no appreciable difference
    between them.

    That being said, use std::vector. It was designed to solve your
    problems, and it solves them well.

    --John Ratliff
     
    John Ratliff, Feb 15, 2007
    #3
  4. The Cool Giraffe

    Kai-Uwe Bux Guest

    The Cool Giraffe wrote:

    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.
    >
    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;
    >
    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.


    Don't needlessly worry about performance.

    The proto-typical implementation of std::vector (with simplifications) looks
    like this:

    template < typename T >
    class vector {

    T* the_data;
    std::size_t the_size;
    std::size_t the_capacity;

    public:

    // typedefs and methods

    T & operator[] ( std::size_t n ) {
    return ( the_data[n] );
    }

    };

    The operator[] method will be inlined by most modern compilers. After that,
    it is very likely that the machine code you get does not show the slightest
    difference to the other options.

    I suggest, you write a simple performance test program to test vector access
    vs. array access. I did that some time ago and there was no measureable
    difference in performance (g++, with optimization):

    http://groups.google.com/group/comp.lang.c /tree/browse_frm/thread/3a2562c9a5f8998/15519204726d01e8



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Feb 15, 2007
    #4
  5. The Cool Giraffe

    Dizzy Guest

    The Cool Giraffe wrote:

    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.
    >
    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;


    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.


    If you only iterate over it all 3 versions above should have the
    same "speed" on iteration. In order to prove this just benchmark your code
    with various versions and see for yourself (don't forget to enable at
    least "inline" functions optimizations in your compiler, so that most
    methods of std::vector get inlined).

    --
    Dizzy
    http://dizzy.roedu.net
     
    Dizzy, Feb 15, 2007
    #5
  6. The Cool Giraffe

    Guest

    The Cool Giraffe je napisao:
    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.
    >
    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;
    >
    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.
    >
    > --
    > Vänligen Kerstin Viltersten
    > (The Cool Giraffe)


    Answer for all of three question is: depends.

    If you will use array that hold 'int', than I will use std::vector. It
    is fast as any implementation, it is bug free (at least 99.99%), have
    huge number of methodes and algos already implemented in std lib.
    Using std::vector you will gain a lot of time, and loose nothing.

    Another story is if you are using some complex types. Than, probably,
    you will have some time-penalities. Generaly, You can use this
    assumptation:

    speed(std::vector) <= speed(plain array)

    Upper 'less-or-equal' have important part - 'equal'. It can be fast as
    plain array, but sometimes it can be slower.

    There is no generaly answer for your problem (even upper assumptation
    can not hold for any problem). On one side you have full std::vector
    implementation with huge amounts of algos, and on other side you have
    speed. Wight one and other, than choose. See C++ FAQ Lite about
    choosing :)

    p.s.
    sorry about my bad english

    Best,
    Zaharije Pasalic
     
    , Feb 15, 2007
    #6
  7. wrote/skrev/kaita/popisal/schreibt :
    > The Cool Giraffe je napisao:


    >> Which is fastest (significantly faster, preferable in any
    >> way, etc.) in the following list.
    >>
    >> a) std::vector?
    >> b) a struct with an array and an integer?
    >> c) saving the int as an instance variable?

    >
    > Answer for all of three question is: depends.
    >
    > If you will use array that hold 'int', than I will use
    > std::vector. It is fast as any implementation... Using
    > std::vector you will gain a lot of time, and loose nothing.
    > Another story is if you are using some complex types.


    Actually, what i left out previously (trying to keep the
    question simple) was that i'll be doing simulations on a
    3D-structure, hence a three dimensional (int or double)
    array was what i was aiming at. At least at first.

    So, perhaps the question i'd like to ask is rather this.
    Assuming we'll be working with a 3D array of either
    integers or floating point numbers, what is an
    appropriate choice of variable type?

    I could go with a vector of vectors of vectors but i
    wonder if there perhaps is something more suited. I
    don't feel lucky enough to hope for a vector3d-class
    but perhaps you'll suggest write my own class. Is
    that the ususal way it's being done?

    --
    Vänligen Kerstin Viltersten
    (The Cool Giraffe)
     
    The Cool Giraffe, Feb 15, 2007
    #7
  8. The Cool Giraffe

    Lionel B Guest

    On Thu, 15 Feb 2007 09:59:03 +0100, The Cool Giraffe wrote:

    > I got a hint recently (guess where, hehe) and was directly
    > pointed to the vector class. Now, i have no issues using
    > that way but i'm concerned about the performance issue.
    >
    > Which is fastest (significantly faster, preferable in any
    > way, etc.) in the following list.
    >
    > a) std::vector?
    >
    > b) a struct with an array and an integer?
    > struct {int* arr = new arr[m]; int m}
    >
    > c) saving the int as an instance variable?
    > int* arr = new arr[m];
    > this.arrSize = m;
    >
    > In the program, there will be a lot of looping and iterating
    > and i'm supposed to use C++, if that's of any importance to
    > answer the abc-questions.


    A sort of "in-between" possibility might be to use std::valarray, which is
    (potentially) more compiler-optimizable than std::vector due to it being
    guaranteed "alias free". std::valarray is a bit of an odd beast, though...
    it doesn't satisfy the conditions to be a real container, has peculiar
    semantics and has frequently been criticised for poor design. It also
    lacks a lot of the functionality of std::vector.

    That having been said, there are, at least, some tricks to create very
    efficient multi-dimensional arrays using std::valarray.

    Another possibility for efficient arrays is the Blitz++ library:

    http://www.oonumerics.org/blitz/

    which uses some sophisticated template meta-programming techniques to
    achieve high efficiency.

    --
    Lionel B
     
    Lionel B, Feb 15, 2007
    #8
  9. The Cool Giraffe

    Joe Gottman Guest

    The Cool Giraffe wrote:

    > Actually, what i left out previously (trying to keep the
    > question simple) was that i'll be doing simulations on a
    > 3D-structure, hence a three dimensional (int or double)
    > array was what i was aiming at. At least at first.
    >
    > So, perhaps the question i'd like to ask is rather this.
    > Assuming we'll be working with a 3D array of either
    > integers or floating point numbers, what is an
    > appropriate choice of variable type?
    >
    > I could go with a vector of vectors of vectors but i
    > wonder if there perhaps is something more suited. I
    > don't feel lucky enough to hope for a vector3d-class
    > but perhaps you'll suggest write my own class. Is
    > that the ususal way it's being done?
    >


    If you're going to work with a 3-d array, I'd suggest boost::array (see
    http://www.boost.org/ for details). This is a nice implementation of a
    fixed-size array and is significantly faster than a vector because it
    doesn't have to allocate and deallocate dynamically. So you could declare
    vector<boost::array<double, 3> >;

    Alternatively, you could create your own point class that contains 3
    doubles and make a vector of those. This could be useful if you wanted
    to add your own methods to the point class.

    Joe Gottman
     
    Joe Gottman, Feb 15, 2007
    #9
  10. The Cool Giraffe wrote:
    > wrote/skrev/kaita/popisal/schreibt :
    >
    >>The Cool Giraffe je napisao:

    >
    >
    >>>Which is fastest (significantly faster, preferable in any
    >>>way, etc.) in the following list.
    >>>
    >>>a) std::vector?
    >>>b) a struct with an array and an integer?
    >>>c) saving the int as an instance variable?

    >>
    >>Answer for all of three question is: depends.
    >>
    >>If you will use array that hold 'int', than I will use
    >>std::vector. It is fast as any implementation... Using
    >>std::vector you will gain a lot of time, and loose nothing.
    >>Another story is if you are using some complex types.

    >
    >
    > Actually, what i left out previously (trying to keep the
    > question simple) was that i'll be doing simulations on a
    > 3D-structure, hence a three dimensional (int or double)
    > array was what i was aiming at. At least at first.
    >
    > So, perhaps the question i'd like to ask is rather this.
    > Assuming we'll be working with a 3D array of either
    > integers or floating point numbers, what is an
    > appropriate choice of variable type?
    >
    > I could go with a vector of vectors of vectors but i
    > wonder if there perhaps is something more suited. I
    > don't feel lucky enough to hope for a vector3d-class
    > but perhaps you'll suggest write my own class. Is
    > that the ususal way it's being done?
    >


    Really, really, really (trust me it's really true) the best approach is
    to get your code working first using whatever is simplest (which likely
    means std::vector) and only try to optimise your code later if you are
    unhappy with the performance.

    Well written code is easier to optimize than badly written code is to
    debug. Trust me.


    Don't fall into the newbie trap of premature optimization.

    john
     
    John Harrison, Feb 15, 2007
    #10
  11. John Harrison wrote/skrev/kaita/popisal/schreibt :
    > The Cool Giraffe wrote:
    >> wrote/skrev/kaita/popisal/schreibt :
    >>> The Cool Giraffe je napisao:

    >>
    >>>> Which is fastest (significantly faster, preferable in any
    >>>> way, etc.) in the following list.

    >
    > Really, really, really (trust me it's really true) the best approach is to
    > get your code working first using whatever is simplest (which likely means
    > std::vector) and only try to optimise your code later if you are unhappy
    > with the performance. Well written code is easier to optimize than badly
    > written code is to debug. Trust me.


    I really, really, really trust you. :)

    > Don't fall into the newbie trap of premature optimization.


    I'll try not to and most likely i'm going to fail. But i'll do my
    best not to. Thanks!

    --
    Vänligen Kerstin Viltersten
    (The Cool Giraffe)
     
    The Cool Giraffe, Feb 15, 2007
    #11
    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. JohnZing

    declared or not declared ?

    JohnZing, Feb 5, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    1,615
    Jon Paal
    Feb 5, 2006
  2. pmatos
    Replies:
    6
    Views:
    24,043
  3. Replies:
    8
    Views:
    1,989
    Csaba
    Feb 18, 2006
  4. Javier
    Replies:
    2
    Views:
    606
    James Kanze
    Sep 4, 2007
  5. Replies:
    5
    Views:
    126
Loading...

Share This Page