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  
  Arrays - Fastest way to fill em.  (Read 3489 times)
0 Members and 1 Guest are viewing this topic.
Offline barfy

Junior Member




The evidence of things not seen


« Posted 2004-05-05 21:57:52 »

Hi all,

A question:

What's the fastest way to fill/clear an int type array with the value 0 every frame?

Is it:

1. Create a new int[] each frame?

2. Keep a copy of a 0-filled array then use System.arrayCopy() to fill the destination array with the copy?

3. Use Arrays.fill(dest, 0)?

4. Or something else I haven't thought of?

Thanks Smiley
Offline Matei

Senior Newbie




';..;'


« Reply #1 - Posted 2004-05-05 23:27:59 »

Definitely Arrays.fill. That's what it's designed for - fill an array.

Using new would look for space to allocate new memory (*very* slow + if you get one each frame, you run out of memory and the garbage collector must kick in), and using System.arraycopy requires both reading and writing to an array, whereas Arrays.fill only requires writing.
Offline Abuse

JGO Coder


Medals: 11


falling into the abyss of reality


« Reply #2 - Posted 2004-05-06 01:18:26 »

Indeed, Arrays.fill all the way.

On a vaguely related note.

back when I was doing J2ME work, 1 of the fastest ways to fill an array was something like this :-

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
public static void fill(int [] array, int value)
{
   int length = Math.min(array.length,16);
   for(int i=0; i< length;i++)
   {
      array[i] = value;
   }
   
   while(length<<1 < array.length)
   {
      System.arraycopy(array,0,array,length,length);
      length<<=1;
   }
   
   System.arraycopy(array,0,array,length,array.length-length);
}


Crazy realy Cheesy

infact, on 1 phone in particular, due to a bug in arraycopy,
(it never made a copy of the src array when src=dst) the fastest way to fill an array was :-

1  
2  
3  
4  
5  
public static void fill(int [] array, int value)
{
   array[0] = value;
   System.arraycopy(array,0,array,1,array.length-1);
}


None of this is useful, but its interesting none-the-less Wink

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline barfy

Junior Member




The evidence of things not seen


« Reply #3 - Posted 2004-05-06 06:37:39 »

Quote
Indeed, Arrays.fill all the way.


Hmm, thanks.

I was afraid that Sun's implementation of Arrays.fill() would be something like this:

1  
2  
for(int i=0; i < array.length; i++)
   array[i] = 0;


I'm not sure exactly what optimizations the compiler would perform on such a loop but my guess is that it would not be as optimized as using the natively implemented System.arrayCopy().

The reason I'm looking for a fast way to fill an array with 0's is because I want to clear the DataBuffer array of an image I'm fiddling around with (this is somewhat related to my earlier BufferedImage question, Abuse  Wink ).

Since I'm only going to animate/consider some pixels in the array each frame, I'll have to clear the array first.
Offline D.t.O

Junior Member




Psych'd about Java Games


« Reply #4 - Posted 2004-05-09 23:34:54 »

Quote

I was afraid that Sun's implementation of Arrays.fill() would be something like this:

1  
2  
for(int i=0; i < array.length; i++)
   array[i] = 0;

That's almost exactly what it looks like, except much more flexible (i.e. more params, slower Huh)... Sad

That's probably as fast as it gets without JNI.

Enjoy.
Regards,
     - D.t.O
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #5 - Posted 2004-05-10 02:50:42 »

I suspect Array.fill is 'known' to the VM and it is optimized into very efficient native code.  Just like the Math functions are really just placeholders for the VM to fill in with native instructions when it compiles the bytecode.

Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2004-05-10 09:52:42 »

If the "state of the art" JVM can't optimise that for loop and array fill into the tightest possible machine code by now, I'll get me coat.

Cas Smiley

Offline D.t.O

Junior Member




Psych'd about Java Games


« Reply #7 - Posted 2004-05-11 05:52:39 »

I never knew the Math functions were optimized like that...I oughtta stop looking @ the source because it is fake!!! Angry

[I guess I should also stop trying to reimplement Math functionality :-/]

Enjoy.
Regards,
     - D.t.O
Offline darcone

Junior Member




Size matters


« Reply #8 - Posted 2004-05-12 07:13:18 »

Regarding that J2ME for loop - first, I believe it would be faster to do a:

1  
for(int i = array.length - 1; i >= 0; i--) array[i] = somevalue;


Thats what I have read on Sony ericsson slides. Another interesting thing I read was that due to the way exceptions are being handled on a J2ME platform, this should be a *bit* faster too:

1  
2  
3  
4  
5  
6  
7  
8  
try {

 int i = 0;
 while(true) {

  array[i++] = somevalue;
 }
} catch(Exception ArrayOutOfBoundsException e) { }


I may be wrong, but I may be right Smiley And again, this (aspecially the last one) applies to J2ME, the first one to J2SE but is more ugly than effective.
Offline princec

JGO Kernel


Medals: 343
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #9 - Posted 2004-05-12 09:50:32 »

That is an absolute abomination.

Cas Smiley

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 2004-05-12 10:21:21 »

Quote

Regarding that J2ME for loop - first, I believe it would be faster to do a:

Code:
for(int i = array.length - 1; i >= 0; i--) array = somevalue;




Thats what I have read on Sony ericsson slides. Another interesting thing I read was that due to the way exceptions are being handled on a J2ME platform, this should be a *bit* faster too:

Code:
try {

int i = 0;
while(true) {

 array[i++] = somevalue;
}
} catch(Exception ArrayOutOfBoundsException e) { }




I may be wrong, but I may be right  And again, this (aspecially the last one) applies to J2ME, the first one to J2SE but is more ugly than effective.


I did a quick test and on the client your 1st method is as fast as a regular
1  
2  
        for (int i = 0; i < array.length; i++)
            array[i] = somevalue;


On the server, both your 1st method and the regular method are ~3 times as fast as the client.
Array.fill() is about as fast a loop in the client, in the server its a bit slower than a loop.
Your last method is (not surprisingly) waaaay slower in all tests. It's just weird it is faster on J2ME...

But as usual, don't take these numbers too seriously. They might only apply to my limited test case.

Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #11 - Posted 2004-05-12 10:39:02 »

Quote

Array.fill() is about as fast a loop in the client, in the server its 2-3 times as slow as a loop.


How much warmup did you do? We were seeing last week that with 1.4.2_04 we needed at least 5 minutes of continual stress to have given the server time to catch up with the client. And it could take ten minutes to get the full oomph. Although...that was with "real world" code that's a lot less trivial than a stupid array fill.

(who cares?; please...show me the profiler output that claims array.fill is bottlenecking your application performance! and if the OP can't, they are a FOOL [1] for even caring if there's anything "faster")

[1] - pre-emptive optimization being the root - if not "of all evil" - then at least of many optimization problems, and very very many bugs and broken code.

malloc will be first against the wall when the revolution comes...
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #12 - Posted 2004-05-12 10:49:37 »

Yeah I edited my post after doing some more tests (where I just let the program run longer). In the server it's still a tiny bit slower. Not really worth it, but still slower.

Quote

[1] - pre-emptive optimization being the root - if not "of all evil" - then at least of many optimization problems, and very very many bugs and broken code.

Sure, I've learned my lessons in the past which is why I added the disclaimer in my post that you shouldn't take the results too seriously.

Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #13 - Posted 2004-05-12 11:36:28 »

Quote
Yeah I edited my post after doing some more tests (where I just let the program run longer). In the server it's still a tiny bit slower. Not really worth it, but still slower.


Sad Benchmarking still requires tons of patience, doesn't it? Even with some fairly good free automated test tools appearing these days...

I get the impression that most of the crappy micro-benchmarkers who write all these silly specious articles on "java slower than C++ shocker" compound their mistakes by never running benchmarks for more than the minimum *they reckon* they need - typically about 30 seconds, or pehaps a few minutes if they're feeling diligent. We certainly have seen improvements even 10 minutes after startup - and time when the server is "idling" seems to always be at 0% cpu usage, implying it's only ever optimizing if there's at least some load [blah imagines a benchmarker starting their app and leaving it idle for 30 minutes thinking this will "warm up" the server JVM].

Although, I guess I ought to be pleased if they ever even realise to try the server JVM Roll Eyes

Speaking of which, does Sun not have a "tiger-team" in their marketing dept who seeks out and destroys broken benchmarks? It's the kind of thing that MS inadvertently taught to all the big IT companies years ago - making it someone's day-job to (legitimately) get rid of bad press is a very effective way of improving your reputation among customers. Given that a few accidentally broken benchmarks can cost you hundreds of thousands of dollars, as the bad-mouthing percolates...

malloc will be first against the wall when the revolution comes...
Offline Abuse

JGO Coder


Medals: 11


falling into the abyss of reality


« Reply #14 - Posted 2004-05-12 12:13:43 »

Quote
percolates


hmmmmmmmmmm.

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

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #15 - Posted 2004-05-12 12:41:01 »

I just benchmark on the server VM to see how much of an impact it has for us being tied to the client VM (since nobody has the server VM).
Sometimes the impact is very high (array access being a notable example), sometimes the client performs surprisingly well compared to the server.
Now an IBM-like VM would be nice :-), having server speed and client warm-up time all in one.

Offline darcone

Junior Member




Size matters


« Reply #16 - Posted 2004-05-13 14:38:19 »

I ran a test comparing two methods on a J2ME emulator:

Method 1:

1  
for(int i = 0; i < array.length; i++) array[i] = i;


Method 2:

1  
2  
3  
4  
5  
6  
int i = 0;
           
try {

 while(true) array[i++] = i;
} catch(Exception e) { }


After a few hundred tests (didnt really believe it myself after just a few tests) I got this result on 10000 elements in a int[]:

1: 150 ms
2: 80 ms

So apparently I was right about the ugly method 2 being faster. Now the question remains if it is faster to do a "i != 0" comparison rather than doing a "i < b" comparison, my argument was that doing a "!= 0" would only need one memory reference, while the second would need two. But erik said it wouldnt matter since of the pipeline architecture and since I am not an expert when it comes to hardware perhaps someone has somethint to say about this?
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #17 - Posted 2004-05-13 15:30:15 »

Hey, don't quote me on that! I said my asm was rusty and this is just an assumption  Wink Grin
Anyway I never seen any speed difference between a!=0 and a<b.

Offline darcone

Junior Member




Size matters


« Reply #18 - Posted 2004-05-13 15:43:48 »

Ok, I take that back Smiley
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.

Riven (9 views)
2014-07-29 12:53:52

Dwinin (7 views)
2014-07-29 10:59:34

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

E.R. Fleming (9 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 (51 views)
2014-07-17 23:47:54
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!