4k Code Optimization Tips list

Contests 4K Game Competition - 2012
#1

Hi, lets enter here some Optimization Tips for 4k as a quick overview:

2 must-sees first:
http://www.java4k.com/index.php?action=view&page=getstarted (Java4k Homepage links)
http://www.indiespot.net/app/java-four-kay (Compile&Shrink)

Here some findings:

Code that looks “Optimized” and short often does not result in a smaller jar/pack200.

one example:
using
Version1:
Color c1=new Color(200,100,0);
looks worse than
Version2:
Color c1=new Color(0xc86400);

but when defining many colors
the first version is actually better when the color-parameters repeat,

Color c1=new Color(200,100,0);
Color c2=new Color(100,200,0); //good
(but: Color c2=new Color(102,203,0); //not good)

I think the reason is, that while the first version writes a shorter bytecode, the
second version is easier for the compressor to find a pattern in. So contracting information
into less bytes already in the sourcecode can render the efficiency of the packer useless.

another example:

to store a bytearray inside a string, where each value was between 1 and 10
I tried to compress it into UTF characters
“\u24fe\u21ee” -> storing 4 entries per character, eg 2 entries per byte
where my earlier version used a primitive use of simple character for each entry
“ABCABAAC” -> storing 1 entry per byte

In the end the second version compressed much better.
I think because the packer uses only “full” bytes to build its dictionary.

A quick way to test changes is to use an Hex Editor for example, to see the size of the classfile,
and compare it on the byte-level if any fancy code-constructions are not resulting in the same output as the “primitive” version.

a > b is not shorter than a >= b … so dont worry using >= <= etc. in comparissons/loops when needed

you can use a decompiler to see your own results, after obfuscation.
This really helps in some cases to see what was obfuscated away, and does not need improvement in
the source.

a last resort can always be to to “switch” positions of codelines, where the order does not matter.
The packer might find a better pattern in the new version.
This could be automated.
(only usefull at the very final packing up of the game, small changes can render the result useless)

more:

#2

some general optimisations:

  • a do while loop uses less byte code than just a plain while loop

  • try to use numerics constants between -127 and +127 as these will be stored as byte type in contants bool

  • when looping or in any situation you can manage, perform the conditional test against 0, 1 or -1 as these have special short byte code representaions. i.e.


for (i=9;i>=0;--i)

instead of


for (i=0;i<10;++i)
  • whilst it used to be true, i am not so sure any more with the latest compilers, using a pre-increment (–i) generated smaller byte code than post-increment (i++) but i guess it cant hurt to try.
#3

I’d like to point out that while some of the above tips are undoubtedly true and useful for squeezing out that extra byte, they’re not the sort of optimizations that’ll make or break a 4k game.

The basics, as suggested on the 4k games wiki (there’s a link on java4k.com, or you can go here) are what one should consider first. No custom classes, no methods beyond the main method, careful handling of input and rendering… these will go a long way towards helping beginners. I’d strongly recommend having a look at one of the many 4k applet templates posted in these forums this year and earlier years.

As for tiny optimizations, somebody once pointed out that instead of using float arrays to represent objects, one might use classes already present in the standard API - for example, an instance of Arc2D.Double can hold 6 doubles for you, or Rectangle could hold four. Now whether this is an optimization or not is a bit uncertain… I’ve seen it generate both smaller and larger files after compression, but it might be worth a shot for saving a few extra bytes if you’re in the final stages of optimization.

EDIT: Oh, and just because it doesn’t seem to be mentioned on the wiki, keeping your class name short (preferably one letter only) saves some space, as obfuscators won’t normally rename your class. I don’t know whether Riven’s tool does this for you, though.

EDIT2 : I noted that the java.net main wiki is being shut down, and the java 4k games design wiki with it. I’ve requested it be exported as per the instructions on the site, so we’ll see how that goes.

#4

True its not a starter guide I ment here.
More of a collection of specific tips/findings.
For beginners, the framework thread last year is very helpful.

Here: example templates

#5

Yep, I understood as much, just wanted to make it clear to anybody who stumbles over this thread.

With that said, I’m sure any additional insight is appreciated. :slight_smile:

#6

I guess I will explain the beginner technique I used for making my game.

My problem was that I don’t know how to organize my code without class. Consider the following :


public class Map{

ArrayList<Unit> unitList;

}

public class Unit{

value1;
value2;
value3;
...

}

This kind of scenario happens very often. You have a list of object each with their own attribute so it makes sense to make another class for them. But in Java4k competition making multiple class is a no no.

So here is a simple solution to that problem.


public class Map{

ArrayList<Map> unitList;

unitValue1;
unitValue2;
unitValue3;
...

}

Now your map class can act both as the Map class and the Unit class. And it makes your code much smaller to have only one class. I find it easier to write my game in multiple class and then shrinking it’s size using that technique.

#7

For a 4k game, you want to avoid using the OO way of insulating data with code, and trim down the problem to just the data. In your example, you can simulate a double array (int[][]) by having a fixed amount of data stored per unit (UNIT_DATA_SIZE), and indexing the data per unit:


private static final int MAX_UNIT_COUNT = 30;
private static final int UNIT_DATA_SIZE = 5;
private static final int UNIT_POS_X_INDEX = 0;
private static final int UNIT_POS_Y_INDEX = 1;
private static final int UNIT_VEL_X_INDEX = 2;
private static final int UNIT_VEL_Y_INDEX = 3;
private static final int UNIT_HEALTH_INDEX = 4;

...
int[] units = new int[MAX_UNIT_COUNT * UNIT_DATA_SIZE];

int unit = 3;
int unitx = units[unit * UNIT_DATA_SIZE + UNIT_POS_X_INDEX];
int unity = units[unit * UNIT_DATA_SIZE + UNIT_POS_Y_INDEX];

and so on. Further optimizations can be made by changing the referencing of the array index by using shifts (change UNIT_DATA_SIZE to UNIT_DATA_SIZE_SHL, and have “(unit << UNIT_DATA_SIZE_SHL)” ). It’s a bit inefficient for memory usage, but makes smaller bytecode.

#8

I alway start of using methods and arrays (sometime classes)
Just to quickly get the prototype working.

Only in the later steps I contract it down. (copy-past the methods in, contract everything into one array etc)

Optimizing the code too early can leave you with coding on a messi basis.

Its not too hard to get a working code smaller. At least easier than working on
a preoptimized and hard to read sourcecode.

#9

Yeah but if not all your data are int you can’t do that. My method is more flexible.

#10

Also, I just tried your method and my method to compare the byte difference. The result might surprised you.


public class Test1 {
	
	int value1;
	int value2;
	
	Test1 [] unit;

}



public class Test2 {
	
	public static final int unitSize = 2;
	public static final int unitValue1Index = 0;
	public static final int unitValue2Index = 1;
	
	int [] unit;

}

Test1 : 328 bytes
Test2 : 406 bytes

So, in a very simple example, my method seems better.

Prove me that I’m wrong pls. :slight_smile:

EDIT : I changed all the variable name so they become 1 character long to make sure that it wasn’t that that make the difference and the result are still in my favor :

Test1 : 318 bytes
Test2 : 371 bytes

#11 

private static final int MAX_UNIT_COUNT = 30;
private static final int UNIT_DATA_SIZE = 5;
private static final int UNIT_POS_X_INDEX  = 0*MAX_UNIT_COUNT;
private static final int UNIT_POS_Y_INDEX  = 1*MAX_UNIT_COUNT;
private static final int UNIT_VEL_X_INDEX  = 2*MAX_UNIT_COUNT;
private static final int UNIT_VEL_Y_INDEX  = 3*MAX_UNIT_COUNT;
private static final int UNIT_HEALTH_INDEX = 4*MAX_UNIT_COUNT;

...
int[] units = new int[MAX_UNIT_COUNT * UNIT_DATA_SIZE];

int unit = 3;
int unitx = units[unit + UNIT_POS_X_INDEX];
int unity = units[unit + UNIT_POS_Y_INDEX];

It’s better this way, no ?

Nevertheless, i have compact every tables in 2 table (one of ints and one of doubles). I set table to the same size and same steps (better compression).
Result : 4 131 --> 4 028 ;D I’m happy

#12

It doesn’t surprise me. Running javap -c -private on each class, you’ll see that the static variables are still in the class file. Let’s do some small changes, in order to better reflect actual usage*:


public class Test1 implements Runnable {
        private int value1;
        private int value2;
        private Test1[] unit;
        public void run() {
                unit = new Test1[1];
                System.out.println(unit[0]);
        }
}
public class Test2 implements Runnable {
        private static final int UNIT_SIZE = 2;
        private static final int UNIT_VALUE1_INDEX = 0;
        private static final int UNIT_VALUE2_INDEX = 1;
        private int[] unit;
        public void run() {
                unit = new int[1];
                System.out.println(unit[UNIT_VALUE1_INDEX]);
        }
}

Now let’s run the classes through a minimizer (I picked Proguard for this test). I see this:

Test1.class (javac output): 562 bytes
Test1.class (proguard output): 363 bytes
Test2.class (javac output): 635 bytes
Test2.class (proguard output): 339 bytes

That means, with proper optimization, the array size difference is 24 bytes smaller**. And that’s for a trivial example. Once you start getting into accessing members, rather than just an index, the difference becomes much greater.

(Part of this magic comes from the minimizer stripping out those constant declarations and uses them inline where needed.)

  • I added the “run” method to ensure the variable is not stripped out of the class due to being not used. I added “implements Runnable” to ensure the “run” method isn’t removed.
    ** There is a slight difference with the signature invoked between these two run methods: one invokes java/io/PrintStream.println:(Ljava/lang/Object;)V, the other invokes java/io/PrintStream.println:(I)V, a difference of 17 bytes, but still that makes Test1.class 7 bytes bigger)
#13

Absolutely. If you want uber-small code then base your game around 1 or 2 big arrays. Works pretty good for me!

#14

Wow it’s really magic :). Thx for the explanation

#15

Might be the wrong place, but this is what I used in Burning Man to fit so many levels into a small space -

Assuming your game has tiles, and there are several different sorts of tiles, the naive way to store them is a big array that goes left to right, with a byte or part of a byte for each tile type in order. You can improve this by adding things like back references (something like: tile type 15 doesn’t exist, it means the next byte says how many bytes backwards to look, and the byte after that says how long to keep copying old bytes). However, this comes out to much larger file sizes than necessary as well.

The way to really pack those down is what the ROM hacking scene calls an object format (or they did when I was a part, it’s been ten years). The idea here is that your level files consist of a series of records like Type, X, Y, Width, Height - bit-packed however works for your specific case, of course (do not bit pack across byte lines, the space savings in the file will almost always get canceled out by the extra code). Write a pair of for loops that take those stats and fill in that tile type in your array, and do that for each entry in order.

So, if your game has a 16x16 grid, and you have 4 types of objects, your format could look something like this:

XXXXYYYY WWWHHHTT - one nibble of X, one nibble of Y, three bits each of width and height, and two bits for type

You also need a terminator that says when a level is done. Pick a value you’ll never use for the first byte and quit when you get there. I normally use 0xFF because that’s what everything ever uses in ROM hacking, but you don’t have to do that. In the above format, that would mean no objects can start in the lower right corner.

An example level with the above looks something like this:

00001000 11111101 //x=0, y=8, width=8, height=8, type = 1. A rectangle of stone blocks in the lower left quadrant
10001010 11110101 //x=8, y=10, width=8, height=6, type = 1. A lower rectangle of stone blocks in the lower right quadrant
11001010 01101111 //x=12, y=10, width=3, height=3, type = 3. A small pool of water in the lower right quadrant
11111111 // FF terminator

Which is to say, roughly the first level of Burning Man. That’s 9 bytes. (The real thing uses 13 bytes)

Writing this out by hand is AWFUL so don’t. I wrote a level editor for Burning Man. Your editor doesn’t need to be 4k at all so go nuts and do it the normal way. Your editor doesn’t need to be used by anyone else either, so go nuts and make it super unfriendly. The Burning Man editor was write-only (I remade levels from scratch every time I wanted to modify one, this helped keep size down) and would only do one level. I used cat to put the level set together.