Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Enhanced loop in Tiger  (Read 7266 times)
0 Members and 1 Guest are viewing this topic.
Offline altair

Senior Newbie





« Posted 2004-02-21 22:48:11 »

I have just downloaded 1.5 and started playing with it.
I made a small test with the new enhanced loops. So far I  thought it was just a syntax improvment. I did not realize it can help improve the performance of loops also. Isn't that cool or did I just wake up after everybody ?

Before 1.5, one would write (some stupid test) like this:

// array is int[]

               for (int i=0, n=array.length; i<n; i++)
               {
                     int p = array;
                     p=p+p+p;
               }

in 1.5, it becomes:

             for (int p : array)
               {
                     p=p+p+p;
                }

There is no penalty access to the elements of the array and my first tests show it is actually faster (and yes it is a micro benchmark however it have some audio processing code with tight loops goobling most of the processing time). I wonder if the JVM also can optimize the bound checks since it 'knows' that the whole array is going to be scanned ?


Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #1 - Posted 2004-02-22 00:45:44 »

Interesting.   I guess in that case it is always guaranteed that the index are never out of bounds... I imagine the byte code that is output is therefore exactly what hotspot expects in order for it to do the bounds check elimination.   You should use javap to see how the byte code differs between the two loop formats.

Offline Mark Thornton

Senior Member





« Reply #2 - Posted 2004-02-22 08:51:09 »

Quote
               for (int i=0, n=array.length; i<n; i++)

Possibly your attempted optimisation of copying the array length to 'n' actually slows the loop down. Try using
1  
for (int i=0; i<array.length; i++)

instead.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline AndersDahlberg

Junior Member





« Reply #3 - Posted 2004-02-22 08:51:27 »

A quick test:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
public class Test {
    private static int[] test = new int[10000];

    public static void main(String[] args) {
      // Init
     for (int i = 0; i < test.length; i++) {
          test[i] = i;
      }

      // Jit
     testOld();
      testOld();
      testNew();
      testNew();

      // Test old:
     long old = System.nanoTime();
     
      long total = 0;
      for (int i = 0; i < 10; i++) {
          total += testOld();
      }
     
      long now = System.nanoTime();
     
      System.out.printf("Old took %.3f ms and produced %d\n", ((now - old)/1000000.0f), total);
     
      // Test new:
     old = System.nanoTime();
     
      total = 0;
      for (int i = 0; i < 10; i++) {
          total += testNew();
      }
     
      now = System.nanoTime();
     
      System.out.printf("New took %.3f ms and produced %d\n", ((now - old)/1000000.0f), total);
    }

    private static int testOld() {
      int sum = 0;
      for (int i = 0; i < test.length; i++) {
          sum += test[i];
      }
      return sum;
    }

    private static int testNew() {
      int sum = 0;
      for (int i : test) {
          sum += i;
      }
      return sum;
    }
}

...gives:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
private static int testOld();
  Code:
   0:      iconst_0
   1:      istore_0
   2:      iconst_0
   3:      istore_1
   4:      iload_1
   5:      getstatic      #2; //Field test:[I
  8:      arraylength
   9:      if_icmpge      26
   12:      iload_0
   13:      getstatic      #2; //Field test:[I
  16:      iload_1
   17:      iaload
   18:      iadd
   19:      istore_0
   20:      iinc      1, 1
   23:      goto      4
   26:      iload_0
   27:      ireturn

private static int testNew();
  Code:
   0:      iconst_0
   1:      istore_0
   2:      getstatic      #2; //Field test:[I
  5:      astore_1
   6:      aload_1
   7:      arraylength
   8:      istore_2
   9:      iconst_0
   10:      istore_3
   11:      iload_3
   12:      iload_2
   13:      if_icmpge      32
   16:      aload_1
   17:      iload_3
   18:      iaload
   19:      istore      4
   21:      iload_0
   22:      iload      4
   24:      iadd
   25:      istore_0
   26:      iinc      3, 1
   29:      goto      11
   32:      iload_0
   33:      ireturn


Old took 1.008 ms and produced 499950000
New took 0.675 ms and produced 499950000

Yay - very nice Smiley

(

Old took 20.450 ms and produced 7049827040
New took 23.482 ms and produced 7049827040

If array is ten times bigger Sad
)
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #4 - Posted 2004-02-22 10:55:08 »

interesting that the new for construct doesn't generate the optimal loop :-

1  
2  
3  
4  
5  
6  
7  
8  
      int sum = 0;
      int [] array = test;
      int length = array.length;
      for(int i = 0; i < length; i++)
      {
         sum += array[i];
      }
      return sum;


it generates :-

1  
2  
3  
4  
5  
6  
7  
8  
9  
      int sum = 0;
      int [] array = test;
      int length = array.length;
      for(int i = 0; i < length; i++)
      {
         int j = array[i];
         sum+=j;
      }
      return sum;


This is bad for 2 reasons :-/

1) more bytecode
2) it uses more than 4 local variables.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline abies

Senior Member





« Reply #5 - Posted 2004-02-22 13:05:19 »

I would not care about number of local variables - it will be optimized by jit anyway to no-op.

I also don't see a real problem with number of bytecodes - unless you are coding for j2me, in such case foreach is out of reach anyway Wink

Artur Biesiadowski
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #6 - Posted 2004-02-22 14:03:41 »

But seeing as its automatically generating the code, what is the reason for it to NOT generate the optimal loop :-/

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Jeff

JGO Coder




Got any cats?


« Reply #7 - Posted 2004-02-22 17:02:51 »

Keep in mind that even beofre 1.5 there should be no penalty to the array access.  Thsi is because array has absolutely prdictable bounds.

Such a small microbenchmark has lots of places it can go wrong.  Keep in mind the On Stack reaplcement issue and other issues that often make microbenchmarks like this more or less useless...

JK

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Jeff

JGO Coder




Got any cats?


« Reply #8 - Posted 2004-02-22 17:04:18 »

Btw.. just the fact that the relationship chnages with much bigger loop sizes suggests a warm-up problem in the benchmark.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline altair

Senior Newbie





« Reply #9 - Posted 2004-02-22 17:54:54 »

There mere fact that both code versions actually differ is already food for thought IMO (that was not obvious from the documentation I read about 1.5).

@Mark,
I do not think so, this syntax is used in lots of places in java source files. At worst it does not optimize anything but I would be surprised if it slows down the test.

@Anders,
Did you wait for the warmup to finish as Jeff suggested ?

@Jeff,
This kind of micro benchmarks can easily go wrong but they are interesting when they mimick the hot spots of your program (small loops called zillions of time to process audio/video data for instance).

Are you saying that the hotspot JVM is 'smart' enough to remove array bound checkings before 1.5 ? (I thought bound checkings could be only removed by a flag) It means it is able to analyze that the index is not modified inside of the loop code, that the increment is contant (maybe it _must_ be 1 in order to remove bound cheks). If so, then it is not obvious there is any gain at all, otherwise, the loops with the new syntax should be faster.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Mark Thornton

Senior Member





« Reply #10 - Posted 2004-02-22 18:23:13 »

The server JVM in 1.4 is supposed to be able to remove array bounds checks. The client VM does not.
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #11 - Posted 2004-02-22 18:35:59 »

Quote
The server JVM in 1.4 is supposed to be able to remove array bounds checks. The client VM does not.

Where did you get this information?

I think the only thing to compare in these cases is the bytecode that is generated.  If the bytecode from the new method is larger that is bad because it will be less likely to be inlined.    I don't see the relevance in the number of local variables, as the only thing that seems relevant it that they will fit in registers, but of course that is only an issue AFTER compiling to native code.. so it ultimately could be the same code that hotspot generates, if some locals can be eliminated when the bytecode is compiled.

As Jeff says the test run was far too short initially.

Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #12 - Posted 2004-02-22 20:13:54 »

Quote


I don't see the relevance in the number of local variables,


Java bytecode has special instructions for storing and loading from the 1st 4 local variables. (1byte instruction)
That example above uses 5 local variables, so 1 of the locals is being accessed using the less compact, generic instruction. (1byte instruction, 1byte argument [hmm, or is it a word?])

I'm sure it makes absolutely no difference once compiled to native (if it did, I would be very worried Tongue).
I was just pointing out that an automatically generated loop is less than optimal, which seems illogical to me.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2004-02-23 07:26:42 »

Check the performance of System.arraycopy (which is native code) versus your own pure Java array copy code and see how it fares.

If it's properly compiled and optimised we should see the difference tending towards 0.

Cas Smiley

Offline AndersDahlberg

Junior Member





« Reply #14 - Posted 2004-02-23 08:16:50 »

Well, now - the above was just the largest difference the new for loop could make to execution speed. Smart bytecode versus jitting Smiley

When main is extracted to a seperate static method (letting the jit compile it) and run in a loop from main until it stabilizes the following numbers show (a factor of 100 bigger than the initial run - size doesn't matter when it stabilizes even in the 10000 case):

java [1.5beta1]:

Old took 224.790 ms and produced 17832936640
New took 218.237 ms and produced 17832936640
Old took 227.440 ms and produced 17832936640
New took 212.157 ms and produced 17832936640

and so on...

java -server:

Old took 92.369 ms and produced 17832936640
New took 95.806 ms and produced 17832936640
Old took 97.163 ms and produced 17832936640
New took 93.987 ms and produced 17832936640


java -Xint:

Old took 1905.819 ms and produced 17832936640
New took 1483.741 ms and produced 17832936640


The new for loop is approx. 5-10% faster (i.e. not much!)  when run under client, on server the bound checks are eliminated making the comparision void. Interesting though that the server version is more than 20x faster... Smiley
Offline Mark Thornton

Senior Member





« Reply #15 - Posted 2004-02-23 09:38:37 »

Quote

Where did you get this information?

http://java.sun.com/j2se/1.4/performance.guide.html

I knew I'd seen it somewhere, but it took a while to find again.

Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #16 - Posted 2004-02-23 12:27:39 »

Quote

java -Xint:

Old took 1905.819 ms and produced 17832936640
New took 1483.741 ms and produced 17832936640


The new for loop is approx. 5-10% faster (i.e. not much!)  when run under client, on server the bound checks are eliminated making the comparision void.

What do you mean 'making the comparison void' ?  It looks to me that there is a significant speed up using the new method on the server VM.  The new method is > 20% faster according to the numbers above.

Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #17 - Posted 2004-02-23 12:33:02 »

Quote

http://java.sun.com/j2se/1.4/performance.guide.html

I knew I'd seen it somewhere, but it took a while to find again.


Interesting.  But slightly incomplete.. he have to assume so much.  That page states that array bounds check elimination was added to the server VM in 1.4 (presumably 1.4.0).  But I haven't seen anything that states what optimizations are done in the current client VM.  For 1.4.1 through to 1.5 beta 1 (on which these test were run) there could be additional optimizations to the client VM.  It would be great to have a definitive answer as to what the precise differences between client VM and server VM are in the later releases.

Offline Mark Thornton

Senior Member





« Reply #18 - Posted 2004-02-23 13:27:13 »

http://java.sun.com/docs/performance/
http://java.sun.com/j2se/1.4.2/1.4.2_whitepaper.html

Nothing for 1.4.1 or 1.5 (yet).
Offline AndersDahlberg

Junior Member





« Reply #19 - Posted 2004-02-23 15:56:15 »

Quote

What do you mean 'making the comparison void' ?  It looks to me that there is a significant speed up using the new method on the server VM.  The new method is > 20% faster according to the numbers above.


Nah, that's the interpreted results you have there Smiley

In the server version the difference is  +/- < 5% (i.e. alternating and within error margin)
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #20 - Posted 2004-02-23 16:44:04 »

Quote

Those papers don't give definitive answers about what optimizations ARE done in the client VM .  For instance they don't even mention that the SSE/SSE2 instructions are only used by the server VM.  Thanks for looking though Smiley.

Offline Jeff

JGO Coder




Got any cats?


« Reply #21 - Posted 2004-02-24 20:10:00 »

Quote
Are you saying that the hotspot JVM is 'smart' enough to remove array bound checkings before 1.5 ?


Bounds check hoisting has been in the compiler since 1.4

JK

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline cfmdobbie

Senior Member


Medals: 1


Who, me?


« Reply #22 - Posted 2004-02-25 22:43:05 »

Quote
Bounds check hoisting has been in the compiler since 1.4


Surely bounds check hoisting is part of the JVM?  Or have I misunderstood something... Roll Eyes

Wouldn't it be a security hole to trust the bytecode that an index is in range?

Hellomynameis Charlie Dobbie.
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #23 - Posted 2004-02-26 00:18:29 »

He means the Just In Time Compiler.. when HotSpot compiles to native code.

Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #24 - Posted 2004-02-26 07:27:23 »

...and it's only in the much-unused, horribly-slow-to-start-up server VM Sad

Cas Smiley

Offline Mark Thornton

Senior Member





« Reply #25 - Posted 2004-02-26 07:46:53 »

Quote
...and it's only in the much-unused, horribly-slow-to-start-up server VM Sad

Cas Smiley

The one with the incredibly sophisticated install procedure for adding to the public JRE. Sad
Can you specify the server JVM with webstart (and have it downloaded if not present)?
The startup looks like being even slower relative to the client JVM in Tiger --- the shared class stuff seems only to apply to the client VM.
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #26 - Posted 2004-02-26 09:02:05 »

I don't believe you can explicity specify the server VM in Webstart yet. It's not a great solution anyway - we still rather desperately need the hybrid 2-stage VM instead of separate client and server VMs.

Sharing classes is enabled with the server VM but not initialized by default. Run java -server -Xshare:dump and it'll create the shared classes file for the server VM. Working well here.


Cas Smiley

Offline Jeff

JGO Coder




Got any cats?


« Reply #27 - Posted 2004-02-28 03:58:55 »

Quote

The one with the incredibly sophisticated install procedure for adding to the public JRE. Sad


Huh?  Explain this? To my knowledge the only thing you need to do in the JRE to get the server VM is type -Xserver on the command line.

No install required.

Got a question about Java and game programming?  Just new to the Java Game Development Community?  Try my FAQ.  Its likely you'll learn something!

http://wiki.java.net/bin/view/Games/JeffFAQ
Offline Bombadil

Senior Member





« Reply #28 - Posted 2004-02-28 06:16:16 »

Quote


Huh?  Explain this? To my knowledge the only thing you need to do in the JRE to get the server VM is type -Xserver on the command line.

No install required.

For the Java JRE 1.5 ?

For the Java JRE 1.4 it's different. Just you lucky Apple users have got the server VM by default. We poor Windows users don't see any server VM bundled in the JRE 1.4. At dev time you can copy the JDK's server VM dll folder to the JRE so that sending the following command works: java -server -version

Maybe this is what Mark meant?
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #29 - Posted 2004-02-28 06:49:20 »

Jeff is mistaken; you still need to copy the DLL. In beta1 at least.

The Apple server VM is not the same as Sun's server VM. It merely changes memory tuning characteristics (at this point in time).

Cas Smiley

Pages: [1] 2
  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.

CopyableCougar4 (18 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (63 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!