Very slow processing of vectors?

This is a discussion on Very slow processing of vectors? within the C++ Programming forums, part of the General Programming Boards category; Now instead of throwing guesses all over the place, time the different parts of the code. I would time it ...

  1. #16
    Registered User
    Join Date
    Aug 2003
    Posts
    1,198
    Now instead of throwing guesses all over the place, time the different parts of the code. I would time it in some way like this:

    Code:
    int FindAllPlats() {
    
     __int64 freq, time0, time1;
     QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
     int x_pos, y_pos, MPR;
     char Ac[1];
    
     for(y_pos=1; y_pos <= 23; y_pos++)
      for(x_pos=1; x_pos <= 78; x_pos++) {
       QueryPerformanceCounter((LARGE_INTEGER*)&time0);
       Ac[0]=ReadPos(x_pos, y_pos);
       QueryPerformanceCounter((LARGE_INTEGER*)&time1);
       std::cout << ((float)time1-(float)time0)/(float)freq << endl;
       std::cin.get();
        if(Ac[0] == Wall8)
         MPR++;
       }
    
     return MPR;
    }
    And then keep doing that with all parts of the code until you find the bottleneck.

  2. #17
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Instead of doing something like that, it might be simpler to just use a profiler. Dev-C++ integrates one, but I'm not sure about the Borland Compiler your using (does it include an IDE?)
    Programming Your Mom. http://www.dandongs.com/

  3. #18
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    the free compiler is just that, a compiler only (and a helpfile with the user manual).
    It does come with implib and things like that, but no debugger or profiler.

    The full commercial product of course includes those as well as a complete IDE.

  4. #19
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    First of all a platform does not warrant it's own class in the way you are using it.

    A platform is simply a value in the map array that translates either to a printed character or a tile bitmap. Ice and other surfaces can be simulated by equating an ID or range of IDs for tiles, characters to a surface type.

    The way you are doing it you will have to iterate through a lot of platforms mid-game.

  5. #20
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    Did you not read my post? When swapped with a static array the speed increased greatly. Grr, how many times do I have to say this?

    I cant use a static array permenantly however. It ends up being alot of memory. (32kb + 66kb? not sure. * levels) I could declare them globaly, but it would end up taking up lots of memory no matter what. It would end up taking several mb's, for a console game, thats just retarded.

    Once again, when the vector array was replaced to a static the speed increased. Its not a guess, I posted my code to prove it. Something is rotten in my code, its not how many times I called this ReadConsoleOutputCharacter function.

    I know where my bottleneck is as I said, its the vector. When removed or replaced, the lag vanishes.

    This doesnt make sence, vectors should not be this slow.
    Code:
    //Static:
     for(x=0; x < TotalPlats; x++)
       Plat[x] = FindPlatform();
    //Takes about .2 seconds.
    Code:
    //<vector>
      for(x=0; x < TotalPlats; x++)
       Plat.push_back = FindPlatform();
    And bubba, my class is built based around only one tile, so I dont really need id's. Its called Platform, but its refering to the '-' character. If I do add in more platforms, the class would become alot more complex.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  6. #21
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> Its not a guess, I posted my code to prove it.
    Where?

    So what happens when you reserve space in the vector and treat it like the static array instead of using push_back?

  7. #22
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    Did you not read my post? When swapped with a static array the speed increased greatly. Grr, how many times do I have to say this?
    1) I tested your code as you posted it and it completes in a fraction of a second using vectors instead of arrays.
    2) Common knowledge dictates that vectors, while somewhat slower than straight arrays, aren't several orders of magnitude slower. If they were noone would use them.

    So the conclusion must be that 3) the code you posted isn't the code you're using and/or 4) the problem is not in the posted code at all.

  8. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    I cant use a static array permenantly however. It ends up being alot of memory. (32kb + 66kb? not sure. * levels) I could declare them globaly, but it would end up taking up lots of memory no matter what.
    Logically, if your vector will eventually reach that size, then it will take up (roughly) the same amount of memory as well.

    Once again, when the vector array was replaced to a static the speed increased. Its not a guess, I posted my code to prove it. Something is rotten in my code, its not how many times I called this ReadConsoleOutputCharacter function.
    I suggest writing the smallest and simplest program that demonstrates that swapping a vector for a static array leads to such a drastic speedup. I suspect that while writing this new program, you will find out a problem in your actual code that needs to be addressed, outside of the various suggestions that have been made in this thread.

    So what happens when you reserve space in the vector and treat it like the static array instead of using push_back?
    I just dont see how that will make much of a difference, the memory re-allocation cant possibly take so long.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    Static array:

    Code:
    int blah() {
     int x, TotalPlats;
     Platform Plat[13];
    
     SetPos(0, 0);
    
     TotalPlats=12;
    
     for(x=0; x < TotalPlats; x++)
       Plat[x] = FindPlatform();
    }
    Vector:

    Code:
    int blah() {
     int x, TotalPlats;
     vector <Platform> Plat;
    
     TotalPlats=12;
    
     for(x=0; x < TotalPlats; x++)
       Plat.push_back(FindPlatform());
    }
    The static array is insanely faster. When actualy infused with my code, the results are the same. The static array is always about five seconds faster.

    I'm not farmiliar with vector.reverse, but it sounds to me like it reverse a block of memory, I could reserve a block based on the amount of platforms I found, but how do I use this?

    Once again, dont imply its other parts of my code. Its not. This is a problem somewhere with my use of vectors. When swapped with a static array, the speed increased by five seconds or so.

    Lol you guys definantly stick to what you say for a very long time -,-.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  10. #25
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    I wonder why you ask if you "know" the source of your problem already. Everybody tells you that it cannot be the vector ( at least not the part of your vector-use that you show here ).
    If 15 seconds instead of 20 seconds is "insanely faster" and that is ok for you then you have solved the problem and you don't need any advice.
    BTW it's not vector::reverse it's vector::reserve that you should use.
    Kurt

  11. #26
    Registered User
    Join Date
    Aug 2003
    Posts
    1,198
    Yes the vector is slower than a static array, simply because a vector will do more calls to copyconstructors and destructors and everything. Take this code example:
    Code:
    #include <iostream>
    #include <vector>
    #include <windows.h>
    
    using namespace std;
    
    class Foo
    {
    public:
    	Foo() 
    	{ 
    		for(int i=0; i<10000; i++)
    			for(int j=0; j<10000; j++);
    	}
    	Foo(const Foo &rhs)
    	{
    		for(int i=0; i<10000; i++)
    			for(int j=0; j<10000; j++);
    	}
    };
    
    Foo GetFoo()
    {
    	return Foo();
    }
    
    int main()
    {
    	int x, TotalPlats;
    	Foo Plat[13];
    
    	TotalPlats=12;
    
    	__int64 freq, time0, time1;
    
    	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
    	QueryPerformanceCounter((LARGE_INTEGER*)&time0);
    	for(x=0; x < TotalPlats; x++)
    		Plat[x] = GetFoo();
    
    	QueryPerformanceCounter((LARGE_INTEGER*)&time1);
    
    	cout << "time0: " << (time1-time0)/(float)freq << endl;
    
    	vector<Foo> Plat2;
    
    	QueryPerformanceCounter((LARGE_INTEGER*)&time0);
    	for(x=0; x < TotalPlats; x++)
    		Plat2.push_back(GetFoo());
    	QueryPerformanceCounter((LARGE_INTEGER*)&time1);
    
    	cout << "time1: " << (time1-time0)/(float)freq << endl;
    }
    On my machine the static array part will run in roughly 3.45 seconds, and the vector part will run in around 16.7 seconds. But if I comment out the copyconstructor and let the vector use the default one the vector part will actually run faster than the static array part. So yes, vectors can be very slow if you do lots of expensive stuff in the copyconstructor. Otherwise vectors can actually be faster than the static arrays, so dont go around blaming the vectors for being slow, look at your code and see what might cause the major slowdown.

    I wouldnt be surprised if you actually have alot of stuff going on in the copyconstructor in the Platform class.

  12. #27
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    The static array is insanely faster. When actualy infused with my code, the results are the same. The static array is always about five seconds faster.
    Well, a static array is usually faster than a std::vector, it is just that the speed increase should not be so drastic. Since you are certain that std::vector is too slow, try writing a dynamic array by hand, e.g.
    Code:
    int blah() {
    	int TotalPlats = 12;
    	Platform* Plat = new Platform[TotalPlats];
    	for (int x = 0; x < TotalPlats; ++x) {
    		Plat[x] = FindPlatform();
    	}
    	delete[] Plat;
    	return 0;
    }
    Is the above still much faster than the equivalent using std::vector?

    Once again, dont imply its other parts of my code. Its not.
    After having seen you use 4 loops when 2 additions and assignments would suffice, I wouldnt bet on your claim.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #28
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    In some circles, deque is advocated as the "default" container to use over vector. So give deque a tyr.

    Quote Originally Posted by http://www.gotw.ca/gotw/054.htm
    In Most Cases, Prefer Using deque (Controversial)

    1. In the standard library, vector and deque provide similar services. Which should you typically use? Why? Under what circumstances would you use the other?

    The C++ Standard, in section 23.1.1, offers some advice on which containers to prefer. It says:

    vector is the type of sequence that should be used by default... deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

    I'd like to present an amiably dissenting point of view: I recommend that you consider preferring deque by default instead of vector, especially when the contained type is a class or struct and not a builtin type, unless you really need the container's memory to be contiguous.

    ...< section removed for brevity, visit link for full text>

    The paged organization of a deque offers significant benefits:

    1. A deque offers constant-time insert() and erase() operations at the front of the container, whereas a vector does not -- hence the note in the Standard about using a deque if you need to insert or erase at both ends of the sequence.

    2. A deque uses memory in a more operating system-friendly way, particularly on systems without virtual memory. For example, a 10-megabyte vector uses a single 10-megabyte block of memory, which is usually less efficient in practice than a 10-megabyte deque that can fit in a series of smaller blocks of memory.

    3. A deque is easier to use, and inherently more efficient for growth, than a vector. The only operations supplied by vector that deque doesn't have are capacity() and reserve() -- and that's because deque doesn't need them! For vector, calling reserve() before a large number of push_back()s can eliminate reallocating ever-larger versions of the same buffer every time it finds out that the current one isn't big enough after all. A deque has no such problem, and having a deque::reserve() before a large number of push_back()s would not eliminate any allocations (or any other work) because none of the allocations are redundant; the deque has to allocate the same number of extra pages whether it does it all at once or as elements are actually appended.

    Interestingly, the Standard stack adapter, which can only grow in one direction and so never needs insertion in the middle or at the other end, has its default implementation as a deque:

  14. #29
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    With 12 entries, any speed decrease should not be due reallocation. To test this, construct the vector with the correct number of entries:
    Code:
    int blah() {
     int x, TotalPlats;
    
     SetPos(0, 0);
    
     TotalPlats=12;
     vector <Platform> Plat(TotalPlats);
    
     for(x=0; x < TotalPlats; x++)
       Plat[x] = FindPlatform();
    }
    or use reserve to allocate the space first:
    Code:
    int blah() {
     int x, TotalPlats;
     vector <Platform> Plat;
    
     SetPos(0, 0);
    
     TotalPlats=12;
     Plat.reserve(TotalPlats);
    
     for(x=0; x < TotalPlats; x++)
       Plat.push_back(FindPlatform());
    }
    Note that using reserve will minimize the calls to the copy constructor. If Shakti is right that the Platform class's copy constructor does a lot of processing (even though the posted version of the class doesn't have a copy constructor defined), then using reserve will minimize that copying.

  15. #30
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    Aha! When a call was made to vector.reserve, it made it speed up alot. The speed between static and vector is now totaly unnoticable!

    Thank you guys!

    Just for the record;
    Code:
     vector <Platform> Plat;
    
     TotalPlats=12;
     Plat.reserve(TotalPlats);
    
     for(x=0; x < TotalPlats; x++)
       Plat.push_back(FindPlatform());
    Last edited by Blackroot; 02-05-2006 at 05:58 PM.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

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

Similar Threads

  1. Vectors
    By naseerhaider in forum C++ Programming
    Replies: 11
    Last Post: 05-09-2008, 08:21 AM
  2. How can i made vectors measuring program in DevC++
    By flame82 in forum C Programming
    Replies: 1
    Last Post: 05-07-2008, 02:05 PM
  3. How properly get data out of vectors of templates?
    By 6tr6tr in forum C++ Programming
    Replies: 4
    Last Post: 04-15-2008, 10:35 AM
  4. file writing crashes
    By test in forum C Programming
    Replies: 25
    Last Post: 08-13-2002, 08:44 AM
  5. Points, vectors, matrices
    By subnet_rx in forum Game Programming
    Replies: 17
    Last Post: 01-11-2002, 01:29 PM

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