4
\$\begingroup\$

My game had some lag, so I tried to improve the performance.

I found that if I write my loops separately like this:

for (...){
    for (...){
        // Do operation A 
        // (Fill int[][] with 1s)
    }
}

for (...){
    for (...){
        // Do operation B 
        // (Work with Sprite Renderers & Spritebatch)
    }
}

for (...){
    for (...){
        // Do operation C
        // (Work with Shape Renderers with alpha)
    }
}

then the result runs a whole lot faster than if I try to do all the operations in one loop:

for (...){
    for (...){
        // Do operation A 
        // Do operation B
        // Do operation C
    }
}

Can anyone explain this?

I'm running this game on Android OS!

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you include the whole (pseudo, if too long)code in the question? Links might get broken, code listing will not. \$\endgroup\$ – wondra Mar 31 '18 at 10:24
  • 2
    \$\begingroup\$ Yes, please do. And it usually has to do with the dataset size in relation to CPU cache. \$\endgroup\$ – Engineer Mar 31 '18 at 11:18
  • 1
    \$\begingroup\$ How many times did you run this in a loop while profiling. Beware the dangers of profiling. You should have a warm up phase, where you call the method but ignore the results. Then a very large number of calls that you record. And the results will still probably be suspect but less so. You may have experienced a hotspot compile right in the middle of your test, which speeds things up in the long term but slows them down in the short term \$\endgroup\$ – Richard Tingle Mar 31 '18 at 11:19
  • \$\begingroup\$ those loops runs every frame in render() method. and as i said i use libgdx and also posting the code here wont help that much. so i can just explain it shortly. the first loop sets all 2d list to 1. the second loop draw sprite ( not from the list ). the third one draws a rectangle with alpha value from the list ( which is calculated in the 2nd loops after setting all to 1 ). and the calculation is just simple maths. \$\endgroup\$ – Han Programer Apr 2 '18 at 6:34
7
\$\begingroup\$

This is not an unexpected result actually. It's a little like how a person's efficiency plummets when they try to multi-task, compared to when they can focus on doing one specific job.

Modern CPUs in computers and phones are vastly faster than the memory they're connected to, so there's elaborate caching and pre-fetching machinery set up to try to stuff the cache full of what the CPU might need soon, so that it doesn't have to wait on data to arrive all the way from main memory. This article on data locality from Game Programming Patterns explains the situation very well.

When you're in a tight inner loop that does just one thing, you make it very easy for these caching systems to predict what the CPU needs and keep ahead of it. For instance, iterating over an integer array in order, your CPU will work through sequential memory addresses, working on every bit of data in each cache line before moving onto the next one. That's the ideal access pattern for these systems

As your loop grows more complicated, your CPU has to switch between doing multiple different tasks, asking for stuff from different areas of memory, and possibly evicting data or instructions from the cache that it will need again when it returns to "operation A" to make room for data/instructions it needs to work on "operation C." This makes it harder for the caching systems to stay ahead of the CPU, and it might stall waiting for main memory from time to time.

So sometimes, letting the CPU do a batch of one type of work uninterrupted, then do a batch of a second kind of work, can help it do both faster than if it were trying to interleave the two.

The order of the nested loops matters too, for the similar reasons. Iterating over a 2D/jagged array [x][y] in the order for ( y...) { for ( x...) { ... } } means grabbing the first entry of the first inner array, then jumping way down the memory address space to the first entry of the second inner array, instead of working on the rest of the data from the first array that got pulled in on the same cache line. That data will probably be evicted from the cache by the time we come back to look at the second entry from the first inner array, forcing us to request it from main memory again...

This is one scenario that could lead to the profiling results you're seeing. But we won't know for sure unless you do some deeper profiling to count things like cache misses. As mentioned in the comments above, this could also be due to coincidence - profiling is tricky, and it takes controlled setups and a lot of repetition to be sure of the data.

\$\endgroup\$
  • \$\begingroup\$ im coding on AIDE ( Android IDE ) So its kinda hard to do deeper profiling & debugging, but ill try to do some and ill post the result \$\endgroup\$ – Han Programer Apr 2 '18 at 6:33
  • 1
    \$\begingroup\$ The second paragraph is honestly going to be the most likely thing there with the little amount of data.. CPUs try to guess what is going to happen next and make sure that they have the memory they need and the instructions they want to run ready for when they get to them.. Having a cache miss on memory or a logic statement that is 50/50 split in its results (if ( rand % 2 == 0)) can put a halt to that capability and make things run very slowly. Data Oriented Designs take advantage of this and is how GPUs have almost always run (vertex buffers, etc, same data ran through the same calculations) \$\endgroup\$ – James Apr 5 '18 at 3:41
  • \$\begingroup\$ found another awesomely surprisefull fact: when i have two separate batch its even faster than one. I think its because each batch is a mesh of vertices, am i right? \$\endgroup\$ – Han Programer Apr 17 '18 at 10:46
0
\$\begingroup\$

After some deep research and a lot of testing finally found out that the problem wasnt the loop as because it works on a simple maths. but the problem was in the rendering batch, the more batch there is, java will likely to share more memory to each batch as because batch is a collection of vertices. i divided them because i have to batch.begin() and batch.end() every batch, and it runs better. thanks all in helping me today. P.s sorry for bas english XD

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.