Thread: Displaying 2D array faster

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    26

    Displaying 2D array faster

    I've been displaying my game map (which draws only what is contained in the bounding box) like so (C#):

    Code:
    // X, Y, Width, Height
    Rectangle rect = new Rectangle(1, 1, 3, 3);
    
    char[,] map = new char[10, 10];
    
    // Initialisation.
    for (int x = 0; x < map.GetLength(0); x++)
    {
        for (int y = 0; y < map.GetLength(1); y++)
        {
            map[x, y] = '#';
        }
    }
    
    // Only draw the part of the map that is contained in the bounding box.
    for (int x = rect.Left; x < rect.Right; x++)
    {
        for (int y = rect.Top; y < rect.Bottom; y++)
        {
            Console.SetCursorPosition(x, y);
            Console.Write(map[x, y]);
        }
    }
    In the "little math problem" thread (which was deleted) Bubba mentioned that there is a better way to display the map, using only one loop.

    So does anyone know how that method (or others) works to draw a map faster than the current method I use?

    Any help is appreciated.

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by HLMetroid View Post
    In the "little math problem" thread (which was deleted) Bubba mentioned that there is a better way to display the map, using only one loop.
    I see no reason not to use two loops, since you need to check the bounds anyway.

    Does Console.Write() automatically move the cursor to the right after writing a char? If so, you can avoid the Console.SetCursorPosition() in the inner loop, calling it only in the outer loop to move to the beginning of the next line. EDIT: I just noticed that your inner loop is looping over y, not x. My suggestion only works if you reverse that, looping over y in the outer loop and x in the inner loop.

    Just that change on its own (processing y in the outer loop and x in the inner loop) might speed it up somewhat, since iterating through memory by column is generally less efficient than by row.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The expensive part of the procedure is the actual drawing operations, not the iterating thru a loop -- and if you use one loop you'll be adding conditionals, which might make it slower than two loops, esp. if the bounding box is much smaller than the map.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Two loops here is no big deal. I was pointing you to the fact that you can unroll the inner loop and in most cases you should. If this was a core render function then you would want to unroll the inner loop. But brute force here is enough to get the job done and you are only printing to the console so it's not an issue.

    On a side note though you should understand arrays enough to be able to traverse a 2D array with one loop or with two. Perhaps you should study up on 2D arrays and exactly what they are.

  5. #5
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    That said, do note HLMetroid the generated MSIL will never contain loop unrolling optimizations, even with the optimization flags. You will always have to do these manually, even if the boundaries of the loop are known and even if they are small. To be clear, even a loop like the one below is not optimized:

    Code:
    for (int i = 1; i <= 2; i++) { Console.Write(i); }
    There's an argument defending that type of optimization is actually performed by the JIT compiler. I find that not only hard to believe, but actually a very bad practice if it indeed were true.

    EDIT: I'm just saying this because C++ compilers usually include this type of optimization for loops smaller than a certain threshold, with known boundaries, which do not change the counter in their body and without complex bodies. Don't expect the same from the current C# compiler.
    Last edited by Mario F.; 02-05-2010 at 08:40 PM.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I'm not even sure a C++ compiler could optimize or unroll inner loops in every situation. The first thing I do is code it the simplest way and if performance is an issue then I start to look at it. I document these types of areas so that if performance becomes a problem later I know right where to look to begin optimizing the code. This helps a lot at work where deadlines don't always allow for the dev time required to optimize. Later when a PM comes and says something about performance I just look back at my notes and then I can at least give some type of answer as to how we may be able to increase the performance in certain situations. It's much better than giving the PM or someone higher the deer in the headlights look.

    However that being said you do need to be careful when optimizing since the release build will be optimized and the debug will not. If you are looking at the debug assembly output then you might be surprised at what you see as compared to the release build output. It is very important to take this into consideration prior to optimizing b/c your optimizations could very well make the code slower than it originally was. Experience has shown me that O(n^x) type loops are usually win-win situations in both debug and release builds. Other optimizations are not so straightforward.

    Since in this case it is a simple console and any PC built in the last 15 to 20 years should be able to fill the console with more pixels than are available on the console window even inside of the ugliest of loops- it's not an issue here. When you get to Direct3D and OGL you will find that even with all this fancy shmancy hardware it is still possible to bring these modern PC behemoths to their knees fairly quick.
    Last edited by VirtualAce; 02-06-2010 at 01:01 PM.

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Quote Originally Posted by Bubba View Post
    However that being said you do need to be careful when optimizing since the release build will be optimized and the debug will not.
    For managed code this isn't much an issue thankfully. It's possible to start a Debug build with "Start Without Debugging" (CTRL+F5) and all optimizations will take place.

    Managed code is more flexible in this regard because most optimizations take place on the JIT.

    I'm not even sure a C++ compiler could optimize or unroll inner loops in every situation.
    As far as I know it will try to unroll both inner and outer loops, given the conditions are met. Problem of course is knowing what these conditions are. So I agree entirely the best option is to do manual unrolling. Other than a few common sense situations, there's probably no way of telling for sure if a nested loop will be unrolled otherwise.

    Of note however is the fact modern processors' branch prediction algorithms (3rd document) can also take an important role in a good number of loop optimizations even when there's no compile-time unwinding. But again, this is of no use to a programmer who, IMO, will not want to rely on the hardware for those performance critical moments and will decide for a manual unwinding instead.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    It is true there are some very low level things that come into play that can trip up optimizations. However some of the tried and true optimizations such as loop unrolling usually, but not always, result in better performance. But again it depends on what the loop is doing internally as to whether or not it is an issue. And of course I wouldn't dare optimize if I hadn't profiled. Strangley enough after profiling my own code most of the time spent was in _stricmp and toupper. This was due to my use of strings. Later I fixed this by using hash IDs and handles to objects. It goes to show that just because you think a section of code is slowing down the performance it may be leading you out into the weeds.

  9. #9
    Registered User
    Join Date
    Feb 2010
    Posts
    6

    Their is a way

    Think of an array as a solid line of data like. 0123456789 and so forth this is an array of 10 now if you make an array like a grid say grid[2][10] it would be like 0123456789 10 11 12 13 14 15 16 17 18 19. so if you set up your for loop like:
    Code:
    for(int x = 0 ; x < ycord * xcord; x++)
    {
    }
     
    if would be the same if you were doing.
    for(int y = 0 ; y < ycord ; y++)
    {
       for(int x = 0 ; x <xcord ; x++)
       {
         
       }
    }
    but very little performance is gained and i would sugest to grab the length first before the for loop. unless their is some purpose for the length like if it wasnt a square/rectangle. The images i attached show an example of it they are both the same in logic.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    but very little performance is gained
    In your trivial example this is true. It really depends on how much the inner loop ends up doing as to whether or not you will receive any benefit from unrolling the loop.

  11. #11
    Registered User
    Join Date
    Sep 2007
    Posts
    26
    Thanks for the help so far everyone.

    Quote Originally Posted by kille6525 View Post
    so if you set up your for loop like:
    Code:
    for(int x = 0 ; x < ycord * xcord; x++)
    {
    }
    Do you think the way I'm doing it here is an optimal way of doing it, or is there a faster way? Note: The console app is just to demonstrate the method I've used.

    Displaying full 2D array:
    Code:
                int width = 10;
                int height = 10;
    
                int x = 0;
                int y = 0;
    
                for (int i = 0; i < width * height; i++)
                {
                    if (x >= width)
                    {
                        x = 0;
                        y++;
                    }
    
                    Console.SetCursorPosition(x, y);
                    Console.Write('#');
    
                    x++;
                }
    Displaying 2D array using bounding box:
    Code:
                int width = 10;
                int height = 10;
    
                int left = 2;
                int right = 4;
                int top = 2;
                int bottom = 4;
    
                int x = 0;
                int y = 0;
    
                for (int i = 0; i < width * height; i++)
                {
                    if (x > right)
                    {
                        x = left;
                        y++;
                    }
    
                    if (x >= left && x <= right
                        && y >= top && y <= bottom)
                    {
                        Console.SetCursorPosition(x, y);
                        Console.Write('#');
                    }
    
                    x++;
                }
    Last edited by HLMetroid; 02-13-2010 at 04:40 PM.

  12. #12
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Forgive my ignorance, but why do you think it's even needed to optimize the rendering loop for a console application?
    The "screen resolution" is so small that even if you managed to find a huge performance gain you wouldn't notice any difference at all.
    Stick to optimizing when and where it is really needed. Anything else is just adding unneeded complication and frustration
    Even if it's just for learning purposes then a console app is hardly the right place to be doing it.
    Last edited by _Mike; 02-13-2010 at 04:04 PM. Reason: spelling..

  13. #13
    Registered User
    Join Date
    Sep 2007
    Posts
    26
    Even if it's just for learning purposes then a console app is hardly the right place to be doing it.
    I'm just interested in knowing if my way of using a single loop with a 2D array is considered to be an optimal way of doing it (in the right situation), or if someone knows of a better way and is willing to share the method.

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Well if you are not interested in the linear approach for optimization but are interested in it as a learning experience then I'm fine with walking you through it.

    First you need to research on what an array is in memory. Two dimensional and n'th dimensional arrays are really just a convenience provided to you by the compiler. You may also want to research into row major and column major arrays.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. cannot print out my 2d array correctly! please help
    By dalearyous in forum C++ Programming
    Replies: 5
    Last Post: 04-10-2006, 02:07 AM
  2. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 09:51 AM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Replies: 6
    Last Post: 10-21-2003, 09:57 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM