Time to plan for '08

[woogley]

get over the harsh language, twice in a row you’ve more or less accused me of things I haven’t done (saying you’re trying to make everything hard, saying the 8k is a bad idea, etc.)

I’m not even here to talk about the 8k, everything I’m talking about here is the 4k. if you want to make an 8k, go for it, but this thread is not the place to organize it. this topic, as the subject suggests, is clearly about planning for the '08 4k contest.

my personal stance on the matters in this thread:

• 8k: neutral, you can organize that elsewhere
• pack200: see my second post on this thread
• compression: while I agree it’s not the most fun part of the contest, there’s no feasible away around it. Abuse says it perfectly when he says “you cannot escape it”

also, Riven, I did not disagree with your comments without making a fair argument. please re-read my reasoning before taking it personally.

[Jamison]

Can’t we all just, get along?

[Abuse]

@Riven

Hm? Any reference to a class or method or field causes UTF-constants to be inserted inthere. Little you can do about it. If you use your on-the-fly decompressor, the original compressed bytecode, has an constant-pool too, so you’re not really saving much. Reflection is another way to shrink the constant-pool, but it has significant overhead everywhere you use it. Hm… I’m out of ideas. You got something figured out that will make us worship you for the rest of your days.

One more hint could do!

g.drawLine(..);
g.drawRect(..);

*cough*

Method[] m = Graphics.class.getMethods();
m[54].invoke(...);
m[33].invoke(...);

* Riven hopes not.

yeah, that’s the ticket - though I was intending to do a lot more than that, and perform it automatically via bytecode manipulation.

I wonder if the set of public classes defined in the “java.*” package inside the “rt.jar” can be assumed as being a constant.
If so, an entire method invocation could be simplified down to 1 or 2 integers. (rather than several 100 bytes as is when accessed via the constants pool)

[Abuse]

I suppose it would be a form of static linking :

[Riven]

I can guarantee you methods are added to these classes in every release, messing up the order, making your indices break.

Further, the code to invoke a method by reflection (push int, push array, fetch element, push object, push args, invoke method), is larger than simply invoking it (push object, push args, invoke method).

It’s a very nice idea, and I couldn’t have thought of it by myself. Maybe it’s a step-stone to another hack… We’ll see!

[Abuse]

@Riven

I can guarantee you methods are added to these classes in every release, messing up the order, making your indices break.

Further, the code to invoke a method by reflection (push int, push array, fetch element, push object, push args, invoke method), is larger than simply invoking it (push object, push args, invoke method).

It’s a very nice idea, and I couldn’t have thought of it by myself. Maybe it’s a step-stone to another hack… We’ll see!

I agree, the cost per invocation would be greater, especially for primitive type parameters.

Perhaps using reflection is too costly and not a good direction to investigate, rebuilding the constants pool using the static-linking mechanism maybe a more profitable (and lower overhead) means of implementing a similar compression scheme. (though only feasible if the static-linking mechanism can be made to work!)

hmm…I wonder if self-modifying code is feasible =D

[Riven]

It’s probably best not to invoke methods in the first place - (doh ;D) - doing your own software rendering instead of using Graphics.

Anyway, when importing a lot of awt/swing classes, the constantpool looks like:
java.awt.Frame
java.awt.Graphics
java.awt.Color
java.awt.KeyEvent
java.awt.MouseEvent
paint(java.lang.Graphics;):v
setColor(java.lang.Color):v
etc etc etc

Look how often the package-name occurs. Now, ZIP is nice, but can’t really do this efficiently, as there is binary data between those entries.

It might be good to have a method-pattern-finder, like:

Method m(int i, String a, String b) {
   for(Method m: Class.forName("java"+(i==0 ? ".awt." : "x.swing.")+a).getMethods()) // generates a StringBuilder... hm
     if(m.getName().startsWith(b))
        return m;
  return null;
}

Integer[] i_ = new Integer[65536]; // positive ints
Integer[] i_neg = new Integer[65536]; // negative ints
for(int k=0; k<65536;k++) {i_[k]=k; i_neg[k]=-k;}

Method[] t = new Method[QUITE_A_LOT];

// manually link
t[0] = m(0,"Graphics","drawS"); // java.awt.Graphics.drawString(java.lang.String;II):void
t[1] = m(0,"Graphics","drawL"); // java.awt.Graphics.drawLine(IIII):void
t[2] = m(1,"JPanel","rep"); // javax.swing.JPanel.repaint():void

// or load from String[]
String[] ss = {"Graphics","drawS",  "Graphics","drawL",  "JPanel","rep"}; // doubles will have a single pool-entry
for(int k=0, p=0; k<n; k++)
   t[k] = m({0,0,1}[k],ss[p++],ss[p++]);

t[0].invoke(g,"highscore",i_[50],i_[185]); // g.drawString("highscore",50,185) -- no auto-boxing!

I doubt it will help though, the overhead is massive To build this into a bytecode encoder would only add insult to injury… does Rube-Goldberg device ring a bell? 8)

[Markus_Persson]

[quote=“Riven,post:47,topic:30440”]
Isn’t this pretty much “just” embedding pack200?

I’ve done some interesting experiments with reflection… you can’t rely on the class names being in the same order, of course, but… say… if you need to name 200 enemies in a game, picking class names from java.awt might be an interesting approach.

[Abuse]

Didn’t someone last year try embedding a pack200 jar inside a class file?
If I remember rightly, most if not all the gains were eaten up by the overhead in unpacking & instanciating the contained class within said pack200 archive?

[Morre]

You’re all insane. I love it.
Granted, I’ve far less experience with these things than most of you guys, but this way of thinking is well above my skills on so many levels. I mean, I understand what you’re saying (for the most part), but there’s no way I’d ever have thought of some of those things myself. Brilliant, I say. And pretty silly. :>

May I say I fear the day Markus and Abuse re-enters the contest? (I can’t remember if Riven participated or not last year?)

[moogie]

@Abuse

Didn’t someone last year try embedding a pack200 jar inside a class file?
If I remember rightly, most if not all the gains were eaten up by the overhead in unpacking & instanciating the contained class within said pack200 archive?

Yeah that was me

for my entry it did not help, but for many other 4k entries i tested it did give net gains.

I will probably attempt to optimise the ‘launcher’ code further this year to see if it will give net gain for my entry this year.

[Abuse]

@Morre

You’re all insane. I love it.
Granted, I’ve far less experience with these things than most of you guys, but this way of thinking is well above my skills on so many levels. I mean, I understand what you’re saying (for the most part), but there’s no way I’d ever have thought of some of those things myself. Brilliant, I say. And pretty silly. :>

May I say I fear the day Markus and Abuse re-enters the contest? (I can’t remember if Riven participated or not last year?)

Given my field is J2ME, I have a vested interest in any new tech. that can reduce code size (though obvious mangling with the bytecode stream, or manipulating the reflection api is beyond the scope of what is possible in J2ME)

A further optimisation that has yet to be investigated is the J2SE JSR/RET instruction ([jump to | return from] sub-routine).
it is normally only used for flow of control when handling finally{} blocks, however given that 4kb games are typically contained within a single ‘main’ (be that the ‘main’ method, or the class constructor), it could be used to embed utility methods within this ‘main’ method allowing them to be executed as sub-routines. (reducing their invocation cost, and eliminating several constant pool entries)

It is worth noting the JSR instruction, while still supported, is no-longer used in classes generated by the 1.6 compiler. (instead, the contents of the finally block are duplicated)
A change that has come about due to the reorganizing(optimisation) of the class file verifier (so it operates in a similar way to those employed in J2ME VMs)

Therefore, if a bytecode tool to perform this optimisation were to be attempted, you’d have to use the java 1.5 compiler (not sure if 1.6 compiler -target 1.5 will work)

[Abuse]

@moogie

Yeah that was me

for my entry it did not help, but for many other 4k entries i tested it did give net gains.

I will probably attempt to optimise the ‘launcher’ code further this year to see if it will give net gain for my entry this year.

That was one of my fears - a game that has already been heavily optimised to reduce the constants pool size is unlikely to gain a significant benefit from pack200 compression.

[moogie]

@Abuse

That was one of my fears - a game that has already been heavily optimised to reduce the constants pool size is unlikely to gain a significant benefit from pack200 compression.

Well, i found i do get significant benefit from using pack200 compression per se, its just having to use a launcher which kills the benefit

hmm… i wonder if a subset of pack200 techniques could achieve benefit… i would have to be able to decompress the class though.

[moogie]

@Abuse

Given my field is J2ME, I have a vested interest in any new tech. that can reduce code size (though obvious mangling with the bytecode stream, or manipulating the reflection api is beyond the scope of what is possible in J2ME)

I am not 100% sure whether it will work with J2ME… it should, but i found by creating a new Class Attribute and then embedding image data inside this attribute significantly saves precious bytes by removing an entry in the JAR and is better than embedding using Hex ecoded values in the source.

The JVM ignores this new unknown attribute and it is simple to read in the image data by means of pre-appending a unique byte sequence ( in my entry last year it was [quote]||
[/quote]
) In your code use the .getResourceAsStream() and seek until you reach this magic unique sequence. From there is is as simple as reading in you images as usual.

e.g.

   InputStream is=this.getClass().getResource("a.class").openStream();
            
            //search for the magic number
            while (!(is.read()=='|' && is.read()=='|'));
            
            //read in sprite infomation

It could be helpful for J2ME…

[Abuse]

Unfortunately most J2ME VMs prevent you getting a stream to the class files within the jar

There is also the memory overhead of embedding any kind of data inside class files - in that it will effectively be loaded into memory twice - once in the class file definition, and a second time in your expanded in-memory representation.

[nonnus29]

To me the allure of pack200 was getting those few hundred more bytes into the game. The original appeal of the j4k was ‘can it be done?’ and then it turned into ‘yes, it can be done, now what cool games can be made?’ and Kevin, Markus (and a few other people I can’t name) proved that really cool games can be made in 4k.

I’m sure there are lots more cool games to be made in 4k, even without pack200. Me, I’m still waiting for the lwjgl 16k.