Thread: Vector vs. array V2.

  1. #1
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677

    Vector vs. array V2.

    In reference to the thread on
    http://cboard.cprogramming.com/showthread.php?t=109567
    and this old thread:
    http://cboard.cprogramming.com/showthread.php?t=104334

    I have updated the code to use dynamic memory allocation for the array model.

    Here is the code I used (generally unmodified from previous test, aside from adding extra code to do the dynamic memory allocation):
    Code:
    #include <iostream>
    #include <iomanip>
    #include <vector>
    #include <ctime>
    
    const int size = 128;
    
    class B
    {
    public:
    	virtual int sum() = 0;
    	virtual ~B() {}
    };
    
    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 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;
    	}
    };
    
    class D: public B
    {
    private:
    	int **parr;
    public:
    	D()
    	{
    		parr = new int*[size];
    		for(int i = 0; i < size; i++)
    		{
    			parr[i] = new int[size];
    			for(int j = 0; j < size; j++)
    			{
    				parr[i][j] = i * j;
    			}
    		}
    	}
    	~D()
    	{
    		for(int i = 0; i < size; i++)
    		{
    			delete [] parr[i];
    		}
    		delete [] parr;
    	}
    	int sum() {
    		int s = 0;
    		for(int i = 0; i < size; i++) 
    			for(int j = 0; j < size; j++)
    				s += parr[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 < 1000000; 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;
    	D d;
    	TIME_IT(func, a);
    	TIME_IT(func, v);
    	TIME_IT(func, d);
    }
    Key:
    a - fixed size array on the stack.
    v - vector of vector.
    d - dynamically allocated 2D array.

    Result: g++ -O2 -fomit-frame-pointer -funroll-loops
    Code:
    x = -802947072
    a: 12.031
    x = -802947072
    v: 11.297
    x = -802947072
    d: 12.907
    Result: Visual Studio .Net (VC++ version 7.0, cl version 13.00)
    Code:
    x = -802947072
    a: 6.218
    x = -802947072
    v: 10.75
    x = -802947072
    d: 7.891
    As you can see (and as I expected), the dynamic variant ends up closer to vector, but still slightly slower than the fixed size array.

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

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Your classes aren't equivalent. At first glance I'd say you need to size the vector in the constructor's initializer list. I don't have time to go into too much detail beyond that though.

    Also, do you have VC++ 7.1 or later? 7.1 is generally considered to be the first good implementation of the standard library for VC++.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Could you add a single block of memory with manual address calculation as another test case? And increase size to 2048, to increase the effect that caching problems create?
    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

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    I'd also increase the number of iterations to get better accuracy, and also check what the difference is if you call vector::reserve() to set it to the size it will end up with before starting the tests.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your classes aren't equivalent. At first glance I'd say you need to size the vector in the constructor's initializer list.
    This test doesn't time the creation and destruction of the objects (should be negligible because it happens once, whereas the objects are used 1000000 times).

    And increase size to 2048,
    If size was increased, wouldn't it be too much for the stack array?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> and also check what the difference is if you call vector::reserve() to set it to the size
    To be equivalent you would set the size in the constructor.

    However, using reserve and push_back could theoretically be an optimization (although I doubt it would matter for POD types) because it avoids a default construction of all the objects. The equivalent for that with new[] involves placement new, but I don't think it's necessary to go that far with the timing.


    >> This test doesn't time the creation and destruction of the objects
    Oops, I made the same mistake last time. I think that information would be pertinent, though.

    >> If size was increase, wouldn't it be too much for the stack array?
    We're really trying to compare vector versus dynamic array, though (at least that was the context of the other thread from R.Stiltskin).
    Last edited by Daved; 11-24-2008 at 04:33 PM.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The STL implementation may be a point, but the construction phase is not what I'm measuring. It only measures the time it takes to sum all the numbers in the array/vector.

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

  8. #8
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    i tried running the same program on VS2005, release mode, and something really bazaar happens. the vector fails completely. i had to reduce the loop to 100000. here are the results:
    Code:
    x = 778698752
    a: 0.578
    x = 778698752
    v: 4.812
    x = 778698752
    d: 0.578

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    VC++ 2005 and later have iterator checks turned on for operator[] even in Release mode. You need to turn that off (I don't know the flag off the top of my head).

  10. #10
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    Quote Originally Posted by Daved View Post
    VC++ 2005 and later have iterator checks turned on for operator[] even in Release mode. You need to turn that off (I don't know the flag off the top of my head).
    weird, i put
    Code:
    #define _SECURE_SCL 0
    #define _SECURE_SCL_THROWS 0
    at the top of my program and it didn't make a difference.

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I extended the size to 2048 x 2048 array/vector size. As the vector is guaranteed to be a contiguos block, I don't expect any difference between reserve/resize.

    Visual studio results:
    Code:
    x = 2097152000
    v: 13.859
    x = 2097152000
    d: 13.766
    I omitted the static array variant, as it does indeed use more stack space than an application is allowed to use...

    This is fewer iterations and bigger blocks of memory, so I guess the overhead of memory reads reduce the efficiency of the processor -> less difference between the two implementations. (Becuase in both cases, the cache-hit rate is lower, and the processor spends more time waiting for the memory to be read). From that perspective, a smaller size is "better", because the processor can cache the memory, and we no longer depend on the external bus to bring data in at a rate about 10x slower than the processor itself.

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

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    When I compile it with VC++ 2008 express I get 3 warnings about the TIME_IT calls in main():
    Code:
    warning C4127: conditional expression is constant
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cpjust View Post
    When I compile it with VC++ 2008 express I get 3 warnings about the TIME_IT calls in main():
    Code:
    warning C4127: conditional expression is constant
    Is that the "do ... while(0)" that is complains about? Try removing that - it's the only "condition" in the entire line, so I can't think of what else it may be.

    I just have this habit of using "do while" around macros, really.

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

  14. #14
    Registered User
    Join Date
    Aug 2008
    Posts
    188
    Quote Originally Posted by matsp View Post
    I just have this habit of using "do while" around macros, really.
    that caught my eye when i first read the source...what's the reasoning behind this? thanks.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by bling
    that caught my eye when i first read the source...what's the reasoning behind this?
    A trick so that you can do things like use an if statement with no else block in a macro without potentially breaking the code that uses the macro.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 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