Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (535)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  JumpTables  (Read 5770 times)
0 Members and 1 Guest are viewing this topic.
Offline Azeem Jiva

Junior Member




Java VM Engineer, Sun Microsystems


« Posted 2005-10-04 22:37:47 »

In case anyone is interested, JumpTables made it into Java6 B55 (should be available wednesday or thursday).  If you have large switch statements this should help a bit.  Give it shot and report any bugs.  Thanks.

Mustang bits at:   https://mustang.dev.java.net/
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #1 - Posted 2005-10-18 12:13:14 »

I always thought that if you order your switch cases, you already got jump tables since years already  Huh
What is my confusion here?

Offline K.I.L.E.R

Senior Member




Java games rock!


« Reply #2 - Posted 2005-10-18 12:42:50 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Mark Thornton

Senior Member





« Reply #3 - Posted 2005-10-18 13:22:36 »

Large switch statements are quite a reasonable approach for some types of code. Specifically parsers where the code is frequently machine generated.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2005-10-18 13:46:37 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

And how long were you learning Java again?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #5 - Posted 2005-10-18 15:08:42 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

You show me how to create a *performing" interpreted CPU emulator without switches.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2005-10-18 15:17:57 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

You show me how to create a *performing" interpreted CPU emulator without switches.

Hm... maybe with a HashMap<Integer, Runnable> ? Better to roll your own hashmap implementation then, to support <int, Runnable> (without autoboxing). You'd safe yourself from a massive jump-table, but the Runnables might slow you don't a bit. I suspect it aint worth the effort for JEmu2 Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #7 - Posted 2005-10-18 15:41:15 »

This approach will lead to 2 performance problems: Bounds checking and indirect function calls through an interface.

I even experimented with an array of interface references so that I can do opcodes[opcode].exec(); but even this is significantly slower than a switch.

Offline pepijnve

Junior Member




Java games rock!


« Reply #8 - Posted 2005-10-18 17:31:19 »

I think you're correct that jumptables have been there all along, at least at a bytecode level. There's even an instruction dedicated to this (tableswitch). Maybe what Azeem is refering to is that the tableswitch bytecode instruction is now also JIT'ed to a native jumptable?
Offline Azeem Jiva

Junior Member




Java VM Engineer, Sun Microsystems


« Reply #9 - Posted 2005-10-18 19:43:24 »

Correct, the bytecodes generated from a switch statement can either be a tableswitch or a lookupswitch (depending on size, sparseness,etc).   The previous implementation would create a binary search tree to calculate which branch of the switch statement to take.  The Jumptable implementation creates a table in the constant section of the generated code, and in most cases its just a load address of the base of the table, calculate the index and jump to the new destination.  The larger the table, the faster the implementation.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #10 - Posted 2005-10-18 21:43:00 »

oh sweetness  Kiss  Grin

Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #11 - Posted 2005-10-18 23:20:42 »

I just gave it a try (Java HotSpot(TM) Client VM (build 1.6.0-ea-b56, mixed mode):

On JEmu2, with Z80 based emulators I see a nice overal performance boost of almost 6%. Pretty impressive  Smiley
With one MC68000 based emulator I see an overal performance gain of about 9-10%  Cheesy, but in another MC68000 emulator, I see a tiny performance degredation of about 2%  Undecided.
However, the latter emulator spends much less time in large switches (more time is spent in video emulation compared to CPU emulation), so I guess this little loss has to do with something else. I'll try to put my finger on the cause of this degradation (really hard to tell at this point).

But overall, I'm impressed!

EDIT: BTW, I measured against 1.4.2_03 client VM. I'll measure against a 1.5 later.

Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #12 - Posted 2005-10-19 01:21:19 »

Correct, the bytecodes generated from a switch statement can either be a tableswitch or a lookupswitch (depending on size, sparseness,etc).   The previous implementation

My memory (back since 1.0.x/1.1.x days) is that you could get something like up to 16 int before it switched to the less direct impl?

malloc will be first against the wall when the revolution comes...
Offline K.I.L.E.R

Senior Member




Java games rock!


« Reply #13 - Posted 2005-10-19 06:54:51 »

3rd year now.
What does that have to do with jump tables?
I believe they are completely unreasonable even when you want to parse large amounts of data.
Just because I can't think of something better at this time doesn't mean a better way doesn't exist.


If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

And how long were you learning Java again?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #14 - Posted 2005-10-19 09:17:34 »

Quote
I believe they are completely unreasonable even when you want to parse large amounts of data.
Just because I can't think of something better at this time doesn't mean a better way doesn't exist.

Maybe you should first think of a reason why jump tables are unreasonable before claiming that my code is broken.
As long as you can't think of something, I believe you are wrong. Remember we're talking about raw performance here, which is not always the same as pretty code.

Quote
My memory (back since 1.0.x/1.1.x days) is that you could get something like up to 16 int before it switched to the less direct impl?
I remember that when you have a properly ordered switch, you get a tableswitch (even if it's quite large), otherwise you get a lookup switch.

Offline Azeem Jiva

Junior Member




Java VM Engineer, Sun Microsystems


« Reply #15 - Posted 2005-10-19 17:28:25 »

But overall, I'm impressed!


Thanks!  You can play with the flags to change how large the switch statement has to be before Jumptables are used.  The flag is -XX:MinJumpTableSize=
The default is at 16, you can try smaller but I've found 16 to be about the right size.
Offline Raghar

Junior Member




Ue ni taete 'ru hitomi ni kono mi wa dou utsuru


« Reply #16 - Posted 2005-10-19 22:05:15 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

You show me how to create a *performing" interpreted CPU emulator without switches.
With binary search. Then compilation into underlying machine code, or bytecode.

And one more thing.

Markov models. In fact PATRICIA trie would do wonders. ~_^
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #17 - Posted 2005-10-20 00:30:55 »

If you have switch statements so large that you're required to optimise them than your code is broken and you should fix it.
Switch statements are jump tables.

All properly written Java code will not see a performance increase with this "feature" in Mustang.

You show me how to create a *performing" interpreted CPU emulator without switches.
With binary search. Then compilation into underlying machine code, or bytecode.

And one more thing.

Markov models. In fact PATRICIA trie would do wonders. ~_^

No, I don't have to search anything.

Look, an interpreting CPU emulator is very easy:

while (cyclesLeft > 0) {
  int opcode = fetch();
  execute(opcode);
}

fetch() just reads an opcode from memory.
Nothing to optimize here, for example:

bus.readByte(PC++);

As I see it, I have 2 options for implementing execute():
1)
switch(opcode) {
  case OPCODE_0: opcodeNOP(); break;
  case OPCODE_1: opcodeADD(registerA, registerB); break;
  etc.
}

2) A pre populated array with function pointers to implementations of the different opcodes:

  opcodes[opcode].exec();

I don't have to search through the array at all because I know in advance where everything is, so here is nothing to optimize.

The 2nd option is the nice one, but the problem with 2) is bounds checking and indirect calls.
In my experience a switch is much faster.

Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #18 - Posted 2005-10-20 00:39:05 »

But overall, I'm impressed!


Thanks!  You can play with the flags to change how large the switch statement has to be before Jumptables are used.  The flag is -XX:MinJumpTableSize=
The default is at 16, you can try smaller but I've found 16 to be about the right size.

Thanks, I'll play with that.

Just one more question:
Why is there even a lookup switch? Isn't a JumpTable always faster?

Offline abies

Senior Member





« Reply #19 - Posted 2005-10-20 16:00:21 »

Why is there even a lookup switch? Isn't a JumpTable always faster?

a) Sparse values. Like
1  
2  
3  
4  
5  
6  
switch (i) {
 case 1:
 case 999:
 case 12121212:
 default:
}


In such cases, binary branches are probably the best solution.

b) Degenerated cases like 2-4 switch targets, speculative path on CPU can cover most of the paths, depending on architecture, while having a jump to address taken from memory location is bound to be 100% stopping any kind of lookahead/pipelining.

Artur Biesiadowski
Offline Azeem Jiva

Junior Member




Java VM Engineer, Sun Microsystems


« Reply #20 - Posted 2005-10-20 16:25:55 »


Thanks, I'll play with that.

Just one more question:
Why is there even a lookup switch? Isn't a JumpTable always faster?

Lookup switch is a bytecode representation of your switch statements. 
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #21 - Posted 2005-10-22 11:52:41 »

BTW, I noticed that there is no server VM in the 1.6 snapshot. Is there going to be one?
I just did a performance comparison of JEmu2 with MAME, and found that one game runs about 18% slower than MAME on the 1.6 client VM while it runs as fast as MAME using the 1.4.2 server VM. I'd be really interested to soo how a 1.6 server VM would compare here  Cheesy

Offline abies

Senior Member





« Reply #22 - Posted 2005-10-22 12:14:09 »

BTW, I noticed that there is no server VM in the 1.6 snapshot. Is there going to be one?

Are you sure you have downloaded jdk, not jre ? Also, be sure to copy it by hand from jdk bin directory to jre bin directory after installation.

Artur Biesiadowski
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #23 - Posted 2005-10-24 22:50:14 »

Oh yes, you're right it was only the jre  Embarrassed
I didn't want to do a real install (last time I did that, JWS and browser integration got messed up), so I downloaded the self-extracting JAR.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

E.R. Fleming (20 views)
2014-07-29 03:07:13

E.R. Fleming (8 views)
2014-07-29 03:06:25

pw (39 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (26 views)
2014-07-23 21:07:15

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21

Zero Volt (50 views)
2014-07-17 23:47:54

danieldean (42 views)
2014-07-17 23:41:23

MustardPeter (45 views)
2014-07-16 23:30:00
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!