Vector vs. array.

This is a discussion on Vector vs. array. within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by cyberfish On a second thought, you are including the memory allocation/moving time in the vector version (in ...

  1. #16
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    Quote Originally Posted by cyberfish View Post
    On a second thought, you are including the memory allocation/moving time in the vector version (in push_back). This is not fair comparison.
    It may not be, but I pushed for a more general scenario. We're more likely to just let the vector manage the memory instead of pre-allocating, so I used push_back instead of resize.

    Quote Originally Posted by anon View Post
    I wouldn't have thought that they'd kill STL performace completely with default settings.
    They do range checking by default, and I can't really say it's a bad thing, since it's more secure. But it leaves you the option to disable that, which is a very fine thing, indeed.
    Actually, in release, if you try to access an out-of-bounds element in the vector, with range checking OFF, the compiler will completely optimize away that line of code.

    I tried a test by preallocating vector and the result was that they were pretty equal, or vector was faster!
    4-6 ms for vector, and 4-7 ms for native array.
    Last edited by Elysia; 06-21-2008 at 04:48 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #17
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    I can't really see how an array would be slower than a vector. If the vector was preallocated, then it might be a bit slower in the initialization than an ordinary array, because the array is one block of memory and it's presumably allocated on the stack, which is very easy to do. (The vector would likely have to search the free store for enough memory, in separate chunks, which I can't see being faster.)

    And then what's going to be faster than array access? It only involves some pointer arithmetic and dereferencing. Unless you're doing something like this
    Code:
    const int size = 10000;
    int array[size][size] = {{0}};
    for(int y = 0; y < size; y ++) {
        for(int x = 0; x < size; x ++) {
            array[x][y] = x * y;
        }
    }
    and involving a lot of page flipping, I can't see an array being less efficient than a vector.

    At least not without extremely good compiler optimisations.

    [edit] This is in theory here. I guess there must be something more efficient about multiple little blocks of memory compared with one big block of memory, because some results above show that vectors are faster.

    Wait -- maybe it's to do with the heap versus the stack! The vectors must be allocated on the heap, and it looks like the arrays in matsp's example are on the stack . . . . [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #18
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    dwks, you underestimate C++
    I can't get my around why it's faster, either, but the results clearly shows that a vector of vector can be faster (when pre-allocated)!
    Last edited by Elysia; 06-21-2008 at 11:54 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #19
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    Quote Originally Posted by Elysia View Post
    dwks, you underestimate C++
    I can't get my around why it's faster, either, but the results clearly shows that a vector of vector can be faster (when pre-allocated)!
    I may underestimate the power of compiler optimisations, but I simply don't understand how it can be faster. They're both taking chunks of memory and accessing them through dereferencing . . . .

    I think I'll do some experimenting.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    Quote Originally Posted by dwks View Post
    I may underestimate the power of compiler optimisations, but I simply don't understand how it can be faster. They're both taking chunks of memory and accessing them through dereferencing . . . .
    True, but it still shows that C++ can still beat C or be very close to C in terms of performance.
    C++ has evolved a lot.
    I find it amazing
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    It could be an error with the timing. A profiler would be better at determining which is faster at certain jobs, or at least "time" the two driver programs.

  7. #22
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    the reason it is so much slower is simply because std::vector:perator [] (1) does bounds checking and (2) is not inline, so you have a function call versus a simple memory index...
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #23
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    Indeed, but you can remove bounds checking in VS (and it's not required to do bounds checking according to the standard anyway), and in Release, it does very well inline the operator [].
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #24
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by Elysia View Post
    They do range checking by default, and I can't really say it's a bad thing, since it's more secure. But it leaves you the option to disable that, which is a very fine thing, indeed.
    It's a horrible thing. I've heard some serious horror stories about the compatibility problems when a binary-only library links against the "secure" STL and the client code wants the unsafe version because secure version is just too damn slow. Well, no can do, sorry. No mixing of the two. You get to beg the library vendor for a version linking against the unsafe version.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #25
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    While I agree that a "define" is not the best way to use or disable safe parts of the library, the secure library in itself is a good thing IMHO.
    Better yet, they could have used a boolean argument via the template that would allow for enabling or disabling secure features. This would allow the compiler to cut out all the safe code if it was compiled with false.

    Microsoft did a good thing, but implemented it in the wrong way.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #26
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Not the first time
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #27
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> Indeed, but you can remove bounds checking in VS (and it's not required to do bounds checking according to the standard anyway), and in Release, it does very well inline the operator [].

    interesting. after running a performance test on a stripped down vector class (inlined, with no bounds checking) it still turned out to be noticably slower than an array.

    Code:
     
    #include <iostream>
    #include <iomanip>
    #include <vector>
    #include <ctime>
     
    namespace test {
     
    template < typename Type >
    class vector
    {
          public:
     
          vector( size_t length = 0 )
          : data_( 0 ), length_( 0 )
          {
                resize( length );
          }
     
          inline Type &
          operator [ ] ( size_t index )
          {
                return data_[ index ];
          }
     
          inline Type const &
          operator [ ] ( size_t index ) const
          {
                return data_[ index ];
          }      
     
          void
          resize( size_t length )
          {
                free( );
                data_ = new Type[ length_ = length ];
          }
     
          void
          free( void )
          {
                delete [] data_;
                length_ = 0;
          }
     
          virtual
          ~vector( void )
          {
                free( );
          }
     
          protected:
     
          vector( vector const & ); 
     
          Type * data_;
          size_t length_;
    };
     
    } // namespace test
     
    const int size = 100;
     
    class B
    {
    public:
          virtual int sum() = 0;
    };
     
    class V : public B
    {
    private:
          std::vector < std::vector <int> > vec;
    public:
          V() 
          {
                for(int i = 0; i < size; i++)
                {
                      vec.push_back(std::vector<int>(0));
                      for(int j = 0; j < size; j++)
                      {
                            vec[i].push_back(i * j);
                      }
                }
          }
     
          virtual int sum() {
                int s = 0;
                for(int i = 0; i < size; i++) 
                      for(int j = 0; j < size; j++)
                            s += vec[i][j];
                return s;
          }
    };
     
    class V2 : public B
    {
    private:
          test::vector < test::vector <int> > vec;
    public:
          V2() 
          : vec( size )
          {            
                for(int i = 0; i < size; i++)
                {
                      vec[i].resize(size);
                      for(int j = 0; j < size; j++)
                      {
                            vec[i][j] = i * j;
                      }
                }
          }
     
          virtual int sum() {
                int s = 0;
                for(int i = 0; i < size; i++) 
                      for(int j = 0; j < size; j++)
                            s += vec[i][j];
                return s;
          }
    };
     
    class A : public B
    {
    private:
          int arr[size][size];
    public:
          A()
          {
                for(int i = 0; i < size; i++)
                {
                      for(int j = 0; j < size; j++)
                      {
                            arr[i][j] = i * j;
                      }
                }
          }
     
          int sum() {
                int s = 0;
                for(int i = 0; i < size; i++) 
                      for(int j = 0; j < size; j++)
                            s += arr[i][j];
                return s;
          }
    };
     
    int func(B *b)
    {
          return b->sum();
    }
     
    void timeIt(char *name, int (*f)(B *b), B * b)
    {
          int x = 0;
          clock_t t = clock();
          for(int i = 0; i < 100000; i++)
          {
                x += f(b);
          }
          t = clock() - t;
          std::cout << "x = " << x << std::endl;
          std::cout << name << ": " << std::setprecision(6) << static_cast<double>(t) / CLOCKS_PER_SEC << std::endl;
    }
     
    #define TIME_IT(f, b) do { timeIt(#b, f, &b); } while(0)
     
    int main()
    {
          A a;
          V v;
          V2 v2;
          TIME_IT(func, a);
          TIME_IT(func, v2);
          TIME_IT(func, v);
          system( "pause" );
    }
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  13. #28
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    I'm with dwks:
    A vector can be as fast as an array, not faster. Why? because a vector uses an array internally. Anything that proves otherwise has to be an invalid test, and there are so many ways for it to be invalid.

    Remember, these kind of things are highly succeptable to timing variations between runs due to the particular piece of memory sometimes being in the cache or not. The array also should be dynamically allocated to be apples vs apples.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #29
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,630
    Quote Originally Posted by iMalc View Post
    Remember, these kind of things are highly succeptable to timing variations between runs due to the particular piece of memory sometimes being in the cache or not. The array also should be dynamically allocated to be apples vs apples.
    I think the original purpose was to answer if vector of vector was a big disadvantage instead of a 2D array, which clearly proven it isn't.
    Although we got pretty far into discussing timings and how vector of vector could be faster which is great news, really, if true, since that would give a boon to C++ devs who use simpler vectors instead of arrays.

    I digress anyway.
    It's clearly proven that a vector of vector is not necessary much slower than a pure 2D array.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #30
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Until we understand why my results are different from the results showing the opposite way around, I'd say that it may well be that we are looking at completely different setups and thus not comparing the same thing. For example alignment may be something that vectors do better - which is something that should be considered in the optimization of any code.

    In my case, gcc -O3 gives about 11 seconds for both - +/- 0.1 second in either direction.

    When I have some time, I will look into it.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Replies: 6
    Last Post: 11-09-2006, 02:28 AM
  3. [question]Analyzing data in a two-dimensional array
    By burbose in forum C Programming
    Replies: 2
    Last Post: 06-13-2005, 07:31 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21