Very slow processing of vectors?

(Borland C++ Free Command Line Compiler, WinXP)

Ok, I'm having a bit of a deilema, this code goes on for about 10-20 seconds before completing, and the loop only runs twelve times... It shouldent be this slow, and it doesnt really work as every time I call this it makes a very long wait.

Platform class <-> (Do I need to make my class support vectors?)

Code:

---

class Platform {
 private:
  SHORT Strength;
  SHORT SteppedOn;
  SHORT x;
  SHORT y;
 public:
  Platform() {Strength=1; SteppedOn=0; x=0; y=0;}
  Platform(SHORT str, SHORT Step, SHORT x_pos, SHORT y_pos) {Strength=str; SteppedOn=Step; x=x_pos; y=y_pos;}

  void Set(SHORT str, SHORT Step, SHORT x_pos, SHORT y_pos) {Strength=str; SteppedOn=Step; x=x_pos; y=y_pos;}

  SHORT GetX() {return x;}
  SHORT GetY() {return y;}
  SHORT GetStr() {return Strength;}
  SHORT GetWStatus() {return SteppedOn;}
  void Reset() {Strength=1; SteppedOn=0; x=0; y=0;}
};

---

Called function:

Code:

---


//Wall8 is '-' its declared in another portion of code.

Platform FindPlatform() {
 int x_pos, y_pos, MPR;
 Platform MOR;
 char Ac[1];

 for(y_pos=1; y_pos <= 23; y_pos++)
  for(x_pos=1; x_pos <= 78; x_pos++) {
  Ac[0]=ReadPos(x_pos, y_pos);
    if(Ac[0] == Wall8)
    MOR.Set(1, 0, x_pos, y_pos);
    return MOR;
  }

 return MOR;
}

---

Main body:

Code:

---

int LINE() {
 int x, TotalPlats;
 vector <Platform> Plat;

 TotalPlats=12;

 for(x=0; x < TotalPlats; x++)
  Plat.push_back(FindPlatform());
}

---

This is going way to slow. is it the vectors or the function or what?

Quote:

---

this code goes on for about 10-20 seconds before completing, and the loop only runs twelve times... It shouldent be this slow, and it doesnt really work as every time I call this it makes a very long wait.

---

Each call of FindPlatform() calls ReadPos() up to (23 * 78) times, so in the worst case ReadPos() is called 21528 times. You might try declaring Plat to be a static array of 12 Platform objects, but I think you will hardly see an improvement in speed unless improvement is made to FindPlatform() and/or ReadPos().

ReadPos code:

Code:

---

char ReadPos(SHORT x, SHORT y, SHORT ix=0, SHORT iy=0) {
 DWORD reader;
 COORD Pos;
 char EEE[1];
 SHORT v;

 Pos.X = x;
 Pos.Y = y;

 for(v=0; v > ix; v--)
  Pos.X--;

 for(v=0; v > iy; v--)
  Pos.Y--;

 for(v=0; v < ix; v++)
  Pos.X++;

 for(v=0; v < iy; v++)
  Pos.Y++;

 ReadConsoleOutputCharacter(hOt, &EEE[0], 1, Pos, &reader);

 return EEE[0];
}

---

This is not the problem. I can tell you that because of this bit of code:

Code:

---

int FindAllPlats() {
 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++) {
  Ac[0]=ReadPos(x_pos, y_pos);
    if(Ac[0] == Wall8)
    MPR++;
  }

 return MPR;
}

---

This runs at A++ speed. My problem appears to be the vector itself. (I cant declare my vector as a static array of twelve, some of that code was improvised so I didint half to post my whole application.)

Quote:

---

My problem appears to be the vector itself.

---

hmm... okay. I would suggest using vector's reserve(), but I dont see how that can make a difference of seconds. Also, I'm not too clear on your code, but if FindPlatform() returns the same Platform on each iteration, it may be more efficient to write:

Code:

---

vector<Platform> Plat(TotalPlats, FindPlatform());

---

Quote:

---

I cant declare my vector as a static array of twelve, some of that code was improvised so I didint half to post my whole application.

---

Actually, I meant just testing by swapping the vector for a static array and see if it makes a difference. If it does, then it does make a stronger case that the vector is the problem.

I don't want to argue with you about the performance of a vector.

This is the best example of unefficient code that I have ever seen.
As Laserlight has alredy pointed out you call ReadPos() up to 21528 times ( 12 times for each screen position ), which again calls ReadConsoleOutputCharacter() to read a single character. Only 1 call to ReadConsoleOutputCharacter() is actually reqired. I would say the bottleneck is there.

Read this

Kurt

Incidentally, it looks like the 4 loops that play around with Pos.X and Pos.Y in ReadPos() can be expressed as:

Code:

---

Pos.X = x + ix;
Pos.Y = y + iy;

---

Basically, what your loops do is this: if ix < 0, it decrements Pos.X abs(ix) times. This is the same as just adding ix (which is negative) to Pos.X. If ix > 0, it increments Pos.X ix times. This is the same as just adding ix to Pos.X. Since x is assigned to Pos.X, you might as well as just add x and ix and assign the result to Pos.X

However, I think ZuK's analysis is correct, that an I/O related function like ReadConsoleOutputCharacter() is what makes ReadPos() expensive in terms of time.

Quote:

---

Only 1 call to ReadConsoleOutputCharacter() is actually reqired.

---

Are you sure? It looks like Pos changes since x and y changes, so ReadConsoleOutputCharacter() is called with a different value of dwReadCoord on each call of ReadPos() from FindPlatform().

I know I could read my whole console into a string or char, but I dont see how thats different because you still have to call string[x * y]. I dont know how ReadConsoleOutputCharacter works, but I can guess it throws the whole console into an array and finds the character in that array. So its probably much slower actualy, I'll probably end up replacing it.

But thats not my main problem, I tried using a 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();
}

---

This goes much faster. Literaly the speed increase is insane. I dont want to have to declare 2000 platforms however, that would be way to much memory. (4^2 * 2000, 32000 bytes) I dont want to allocate so much, and I cant dynamicaly expand an array any other way without using new & delete which I was advised not to do.

So, do I have an alternative besides:
Declaring an obeese block of memory.
Using vectors <-> or can I do this in a better fashion?.

[edit]
Just saw your post, haha I cant beileive I made a loop where I could have used simple addition -,-. Boy I'm dumb >.<.

actually 32000 bytes is not much in terms of computers, think of games that allocate hundreds of megabytes, you just allocate a little more than 31 kilobyte, dont worry about that.

This is not a comercial game, allocating 32kb is insane in this case. If their is no alternative, I guess I could if I absolutely have to, but I feel having an additional 32kb floating around for a very small portion of the game is just dumb on my behalf. It does appear that vectors are my problem, but is their no alternative to theyse?

Come to think of it, Is this possible?

Code:

---

char Test(int x) {
 char alto[x];
}

---

That way you allocate memory equal to x... But is this alloud? Thinking about this, wont this allocate blocks of unused memory aswell?

Quote:

---

Originally Posted by laserlight

Are you sure? It looks like Pos changes since x and y changes, so ReadConsoleOutputCharacter() is called with a different value of dwReadCoord on each call of ReadPos() from FindPlatform().

---

Quite shure. The dwReadCoord is just the starting position and nLength is the number of characters to read.
I would create an array that can hold the the entire screen-content and call ReadConsoleOutputCharacter() with the coords(0,0) and a length of the nr of characters on the screen. All the other checks could then be performed on this buffer.
This should work because there is no I/O while the function LINE is running.
Also I could imagine that ReadConsoleOutputCharacter() would perform a lot of synchronization ( locking ) work for each call to make it threadsafe.
Kurt

So you worry about needing 31 kilobytes of extra RAM more than you appreciate the speed increase that caching provides?
Weird reasoning.

Just make sure you deallocate the memory when no longer needed.

Not a bad idea actually. But why would that be quicker? You still have to read every character on the screen when you make a call to ReadConsoleOutputCharacter. Because when you call it once and extract all the chars, you are duplicating the whole screen. But you still have to have every character copied over to your buffer. Making several smaller calls to ReadConsoleOutputCharacter in my mind is just quicker.

But once again, this is not my speed issue. Vectors are slowing me down considerably, is their any alternative, or is their something I'm doing wrong?

By the way, thank you for your help thus far.

There's something very weird going on here. Vector is never that much slower than an array.

Quote:

---

Originally Posted by Blackroot

Not a bad idea actually. But why would that be quicker? You still have to read every character on the screen when you make a call to ReadConsoleOutputCharacter. Because when you call it once and extract all the chars, you are duplicating the whole screen. But you still have to have every character copied over to your buffer. Making several smaller calls to ReadConsoleOutputCharacter in my mind is just quicker.

---

Each call to any function adds some overhead. If you can achieve the same with fewer calls this will be faster.

Quote:

---

But once again, this is not my speed issue. Vectors are slowing me down considerably, is their any alternative, or is their something I'm doing wrong?

---

This is just not possible. 12 calls to push_back() cannot need 10 to 20 seconds. Nobody would use a vector then.
Kurt

yes, ReadConsoleOutputCharacter() is the only logical place for the major performance problems.
Out of the 10-20 seconds, all but a few tens of milliseconds are almost certainly spent in that one function.

Running just the code you put up here (a single call to LINE) completed in a fraction of a second if I remove the call to ReadConsoleOutputCharacter().

Leaving that call in and passing it 0 for the first parameter (rather than the hOt you didn't specify, it is only a few milliseconds slower.

So whatever hOt is is the culprit, if your problems are in this piece of your program at all.

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.

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?)

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.

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.

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.

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

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

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

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.

Quote:

---

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?

Quote:

---

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.

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:

---

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.

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());

---

reserve() is handy for just such a thing - another potential improvement (though w/o having read in detail all of the thread, I could be off ;) ) would be to make your vector store pointers rather than full objects - this would have the benefit of NEVER having to call the copy constructors on your objects. Additionally, for LOTS more safety against memory leaks, store boost::shared_ptr<Platform> (or the new TR1 equivalent, if your compiler supports that). That way, you can create the Platform dynamically on the heap. wrap it in the shared_ptr, pass that to the vector, and forget about it. The pointer will be deleted when the last shared_ptr to it goes out of scope.

Or use a boost::ptr_vector, which would be ideal for this application and removes the overhead of shared_ptr.

Ah, yeah - forgot about those! Good call.

Just for completeness, does the Platform class have a copy constructor, copy assignment operator, or any other member variables that were not shown in the initial post? The only data shown was four SHORTS, which I assume (hope) are just short ints. If you are pushing back only 12 instances that use the default copy, I highly doubt that there would be more than one reallocation and that the copying would cause such a dramatic speed decrease.

Point being that you shouldn't have to worry about reserve when you are reserving space for 12 instances of a class that contains only 4 short ints. Something else caused your slowdown, and you just masked the issue by using reserve.

Could be. I noticed after going through all this my actualy program was calling ReadPos more like a few hundred million times. My loop broke somewhere into infinite because I never updated my older code to reflect the newer :/. But that doesnt stop that the vector seemed to cause the greatest speed decrease. When replaced with a static, it went alot faster.

Anyways, its fixed. Your codes are way above my head -,-. Is their any tutorial that explains your suggestions? -,- *Searches google*

>> Your codes are way above my head

Whose code? Most of the code here just uses vector, which you were already using. There are references available for vector and the rest of the standard library that you have hopefully found with your search.

>> Anyways, its fixed.

Unfortunately, it just appears to be fixed. Whether it is actually fixed or not we don't know because you haven't dug deep enough to find the details. It is often better to find the root of the problem than merely cover it up. I wouldn't be surprised if you had another "major slowdown" later on if you continue to work on this project.