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; (Borland C++ Free Command Line Compiler, WinXP) Ok, I'm having a bit of a deilema, this code goes on for ...

  1. #1
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379

    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?
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    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().
    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

  3. #3
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    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.)
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    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());
    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.
    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

  5. #5
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    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.

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

  7. #7
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    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 >.<.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    1,203
    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.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  9. #9
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    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?
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  10. #10
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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

  11. #11
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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.

  12. #12
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    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.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    There's something very weird going on here. Vector is never that much slower than an array.
    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

  14. #14
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    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.

    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

  15. #15
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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.
    Last edited by jwenting; 02-04-2006 at 05:23 AM.

Page 1 of 3 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