Garbage Collection and Skipped Turns

Starting a new thread to discuss my efforts to deal with the skipped turn issue that is apparently related to garbage collection eating up allowed run time. This was previously discussed in thread "Shielding Success Rates Mystery", for anyone who wants to see where it all started.

I purposely did not contribute to the rumble over the last few days after the pairings for XanderCat 12.6 were lost. I originally ran many of the original pairings on my PC that does not have the skipped turns issue. Most of the re-run pairings were likely run by Voidious, whose system does exhibit the skipped turns issue.

The difference between the two is quite significant. With clients that don't exhibit the skipped turns issue, XanderCat achieved an APS of 87.7. With clients that do exhibit the shipped turns issue, XanderCat achieved an APS of 86.5. The difference -- 1.2 APS -- is quite significant. With the current rumble participants, it makes the difference between 5th and 8th place.

Most of the difference is due to the skipped turns causing the bullet shielding system to fail much of the time. But likely the skipped turns in general -- ignoring the bullet shielding -- also contribute a small amount.

I had previously fixed a few performance bottlenecks to make XanderCat run quite a bit faster (v 12.3), with much lower turn time peaks, but this only achieved a marginal improvement. I now need to shift to figuring out how to reduce the amount of garbage my framework apparently creates. This is not a real easy problem to address, because it is a very unique Java problem that rarely ever needs to be addressed in the real world, so there is not a lot of information or research available online to help on this.

I think one thing I can do is to eliminate as many intermediate local variables as I can. For example, variables with only method scope that are used to break something into multiple easier to maintain steps. These extra method scope variables may be contributing to the garbage collection, especially in the first round. Eliminating them may help to fix the problem, but at the expensive of either combining multiple lines together into more complex lines or making the variables have a wider than necessary scope (declaring them as part of the class), thus eating more memory overall but eliminating the possibility of it triggering garbage collection.

I don't know if these steps will help, but I will probably give it a try. I am also not sure if there are other ways to reduce garbage collection, but maybe I will come across some other ideas. I may actually create a second branch in my source tree for this work, something I never thought I would do for Robocode. I want to keep the current version, as I think it will constitute better code and perhaps someday the garbage collection issue will be addressed by changes to Robocode itself; but if my garbage reduction efforts work, for now I will operate off of a garbage reduced branch.

This seems like a really crappy thing to push onto you as a bot author. I do think our time is probably better spent coming up with a proposal to change Robocode itself and submitting that (as idea, design, or code) to Fnl. There could be a very simple and elegant solution that would work, like "allow 10x the CPU constant for the first 100 ticks". (Disabling CPU limits in first 100 ticks seems problematic, since you want to at least interrupt bots that hit infinite loops.) Another idea is having Robocode run its own GC cycle right before the match starts, in case bots are being penalized for GC of the game engine.

I'll try to get to another round of tests and find out how much I need to raise the CPU constant to get normal performance out of XanderCat.

I've had to deal with this quite a bit when writing games in c#. Similar to Java the GC can case obvious stalls. The easiest way is to stop calling the "new" function at run time by using pooling. For instance at the start of a match, or a round create a container object which contains N pooled objects which you know you create often, eg wave objects. At the point you wish to use one, take it from the pool, initialise it, use it, then return it to the pool when finished at any point later on.

Because you have not called new, and then nulled the object, the memory used does not go up, it stays constant, thus no GC is run. It's obviously impractical to pool everything so you just do the worst offenders which are things that you create often and throw away.

That seems like a great approach. And you can even create the pools in a static block, which I'm pretty sure runs before the match starts and won't count against any of your CPU time.

Speaking of static blocks, I've noticed that they get run on Robocode/rumble startup for every single bot, which is partly why it takes so long to start when there are lots of bots in the /robocode/robots directory. I also suspect that code in static blocks isn't subject to the security manager, since it can print to the main console. Does somebody feel like writing a test bot to see if this theory is correct?

Local variables are stored in the stack and not the heap, so they don't affect garbage collection.

You should look after "new" abuse, like Wolfman said. Although sometimes the instantiation is implicit and simply searching for the "new" keyword doesn't always work.

There are heap profiling tools which locate automatically where too many objects are being instantiated.

Local variables are stored on the stack but any time you use new it will go on the heap afaik:

public void MyFunc(Object a) {

  Object b = a; // Variable b is on the stack, pointing at a.
  b = new Object(); // Memory allocated on heap, referenced by variable b on the stack

}

This is my understanding of it. Please correct me if I am wrong!

This is correct.

My understanding of the snippet above is that you have 3 variables. 2 local in the stack (references "a" and "b") and 1 in the heap (Object instance).

Some variables stay in the stack only, like primitives (double, float, int...).

Where would a primitive array like an int[] end up?

Java treats an array as an object, so on the heap.

However, these days the JVM is more intelligent than you guys are giving it credit for, eg. it has Escape Analysis to determine if objects should be put on the stack if they stay local.

Didn´t know about escape analysis.

What I usually do to take in account all optimizations, even those I don´t know about, is to use profiling tools. Measure what is really happening, instead of looking at the code and guessing.

I've actually been debating writing a Robocode simulator to make robot profiling much easier. What it would do is to pretend to run a robot battle with your robot against either another opponent, or perhaps some imaginary robot, using a combination of mock objects and simulation. It would run without any security at all, no sandbox, nor would their be skipped turns, so you would only want to run it with trusted robots. But it would be much easier to run a profiler against. The simulated battle may not be a perfect simulation, but as long as it's close, it should work and be useful.

When I do profiling in Robocode, I run a battle of a bot against itself. Then I filter the results by package so engine data is filtered out and only data from my bots appear in the profiling report.

What profiling tool do you use? I haven't tried that many, but I've been rather unsuccessful trying to use profiling tools on Robocode. The last one I tried was Visual VM, but when you try to profile a running instance of Robocode with Visual VM, it prompts for a username and password. I kind of gave up and assumed I would run into similar trouble with all profiling tools, either due to the Robocode security setup or due to the odd way that Robocode loads classes and sandboxes robots. If you know of a profiling tool that works with existing Robocode, please share!

I tried VisualVM and when it asked for username/pw I just did a/a and it worked, I suspect it asks for them but doesn't actually use them.

Make sure you start robocode with -Ddebug=true so that it disables skipped turns!

I got Visual VM working and running through Eclipse too. Its a bit unintuitive to set up through Eclipse but its working now and easy to run. As MN says you can filter out any results from specific packages and just profile your bot (though its worth noting that you might want to leave any java data structure packages such as the Vector class if you use it a lot in your robot).

I managed to get my movement running pretty fast within an hour of getting Visual VM running! :D

If I find the time I might write a wiki page on how to get it up and running in Eclipse and how to set it up to profile your robot.

I just use eclipse, but it took so long that I never really did much profiling (with that). Instead, I timed a bunch of candidates for worst cpu usage and printed the times to the console and then focused on those. All of that, until I realized that I was the only bot evaluating 20 points on the secondary waves :-) When I changed that, I think Gilgalad became one of the fastest bots in the top ten.

Some things to optimize: wall smoothing, I think I recall that you used your own algorithm for this. How fast is that? Geometry methods: How efficient are your precise intersection methods?

I assume you already cache your wave data?

what sort of danger function do you use for surfing?

I never really had trouble with gun speed (yet... we'll see what my latest ideas do to that) so I assume you wouldn't either, but you could at least add some code to verify this.

The last one I used in Robocode was HPROF.

I call the engine directly through the API so GUI stay out of the way.

Yes. However anything that you are creating during a function and keeping hold of for a few frames and then releasing is going to be allocating on the stack. Stuff like "Wave" objects, "Bullet" objects or whatever else you use in your bot will cause GC stalls if you create lots, use for a while and then null. This is where the pooling comes into force. I would definitely recommend pooling objects such as waves etc if you are having trouble with stalls and then go from there.

-wolfman

Yes, yes, come to the dark side, make your code ugly but fast, like mine :-p

Although its more likely that the stall is caused by your code running too slow rather than blaming it on the GC imho. Can you use eclipse to profile execution and memory of robots? Anyone know? If so a wiki page would be lovely :)

Arrays are objects in java:

public void func() {

  int[] myArray; // myArray variable on the stack
  myArray = new int[5]; // Array object allocated on heap, referenced by myArray variable on the stack

}

Note that member variables of objects are obviously going to take up memory on the heap not the stack - eg if you have 30 primitive member variables (ints, doubles etc) of a class and call new on that class, it will take up more memory allocation than a class that has 1 primitive member variable.

However allocating 30 local primitive variables during a function call allocates those primitive types on the stack alongside you local member reference variables.

While I am not the saddest person here that this has happened to you (as my robot is right above yours in the rankings with only a little APS between it and yours). But I know I would hate it if this happened to me. However I have tried to design things from the ground up in more recent robots to limit object creation and destruction.

At one point I even reused old objects (aforementioned pooling) instead of creating new ones. That didn't make it into the current version however.