Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (489)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (555)
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  
  Which is faster? :P  (Read 1994 times)
0 Members and 1 Guest are viewing this topic.
Offline trollwarrior1
« Posted 2013-12-05 08:11:28 »

So um I was thinking about this code and I'm really wondering which is faster.

1  
2  
3  
4  
5  
6  
7  
Random random = new Random();
int rand = random.nextInt(2);
if(rand == 0) {
   // DO SOMETHING
}else if(rand == 1) {
   // DO SOMETHING ELSE
}


Or this.

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  
// Let's say this array is filled only when the program starts and is never changed.
Action[] actions = {
new Action() {
   public void doAction() {
      // DO SOMETHING
  }
},
new Action() {
   public void doAction() {
      // DO SOMETHING ELSE
  }
}};


// Now let's say we do this in a loop everytime we update the game or something
Random random = new Random();
int rand = random.nextInt(2);

acionts[rand].doAction();



interface Action {
   public void doAction();
}


Offline Roquen
« Reply #1 - Posted 2013-12-05 08:19:17 »

The "new" dominates the computation.  That's followed by nextInt(2).  If you only need to do one of two fixed things with equal probability then:

1  
2  
3  
4  
5  
6  
7  
8  
9  
// rng already exists and if you can be JRE 7+ is a threadlocalrandom instead of random...or a custom PRNG

// calling nextInt because nextBoolean is kinda borked, but you could use that instead.
if (rng.nextInt() < 0) {
   // do one
}
else {
  // do other
}
Offline trollwarrior1
« Reply #2 - Posted 2013-12-05 08:22:13 »

I'm asking which is faster. Not which is faster to write. Let's say we had 1000 actions to check. I guess array would be faster.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Damocles
« Reply #3 - Posted 2013-12-05 08:22:28 »

take the firt version,
for once because its much more intuitive, and also I doubt that the bycode for the second runs any faster.

Also reuse the Random object.

if you want to speed it up, rather fill an array with random booleans at startup, and iterate over it.
This saves you to run .nextInt

like:

if(bools[counter++]) doMyThing();
else doTheOther();

or

bools[counter++]?doMyThing():doTheOther();


make shure to not run over the arrays limit.
(reset the counter and/or reinitialize the array with new booleans)

----

a general rule for optimization:

if you want more speed, you need to use more memory.
if you want to use less memory you have to sacrisfy some speed.

Offline Roquen
« Reply #4 - Posted 2013-12-05 10:01:54 »

For form sake: the likehood of this being statistically important is zero.

I'm asking which is faster. Not which is faster to write.
That's the question I answered.

if you want to speed it up, rather fill an array with random booleans at startup, and iterate over it.
This saves you to run .nextInt
That's slower and makes random very not random.

a general rule for optimization:

if you want more speed, you need to use more memory.
if you want to use less memory you have to sacrisfy some speed.

"If you want to get from the UK to the US as fast as possible, then book a ticket on the Titanic".

This statement is the same as the "memory vs. speed" rule of thumb.  Both of these ships sank a very long time ago.  It might be still true if your programming a 10 year lego mindstorm...otherwise forget it.  In general the opposite is true.
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #5 - Posted 2013-12-05 10:03:08 »

A is much faster; it requires nothing more than a conditional branch.

B's implementation on the other hand ( array[index].method() ) requires:

if(array == null) throw NullPointerException
if(index >=array.length) throw ArrayIndexOutOfBoundsException
if(array[index] == null) throw NullPointerException
Method call using invokeinterface (which requires a search of the method table, creation of a stack frame, etc etc).

Though as previously said; you shouldn't be considering performance at this level, simply write your code in the clearest way possible.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Damocles
« Reply #6 - Posted 2013-12-05 10:07:11 »

Quote
That's slower and makes random very not random.

well, try to proove that it slower..

Besides, its as random as you want it to be,
picking a number from a list of random numbers (never from the same list position) qualifies as a random number...

If it where not random then it would be deterministic.
Whats the formula then supposed to be?

Offline Roquen
« Reply #7 - Posted 2013-12-05 10:18:46 »

I don't need to.  It walks more memory.

Pseudo random is deterministic.  That's a good thing.
Offline trollwarrior1
« Reply #8 - Posted 2013-12-05 10:34:57 »

Could you guyz stop giving the stupid advice like "reuse the random object"
I will now try to re-make my question.
Which way would it be faster to do it, if we have 10000 actions to check?
Offline Varkas
« Reply #9 - Posted 2013-12-05 10:38:17 »

Unless this is really a bottleneck in your application, stop worrying about the speed.

The second is better OOP. if you liek OOP, take it.
The first is procedural programming, if you like that, take it.

To me, the second solution looks better, but only because I like OOP. I still might implement the first one at any time if I feel lazy.

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #10 - Posted 2013-12-05 10:41:15 »

Could you guyz stop giving the stupid advice like "reuse the random object"
I will now try to re-make my question.
Which way would it be faster to do it, if we have 10000 actions to check?

The answer is the same; you shouldn't care which is faster, you should be writing your code so that it's readable & maintainable.

Case in point; for 10000 actions, a switch statement with sequential case values would be fastest.... and simultaneously the least maintainable.

For 10k actions I'd consider determining the commonality of the actions, and making it data-driven.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Damocles
« Reply #11 - Posted 2013-12-05 10:42:33 »

Here some code to play around,
using a list is about 4 times faster on my system.

Having 100.000 discrete random numbers should suffice for normal gamelogic (like AI descisions).

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  
57  
58  
59  
import java.util.Random;

public class TestSpeed
{

   static int value=0;
   
   static final int RANDOMLISTSIZE=100001; //use more if more random needed
  static boolean[] rans=new boolean[RANDOMLISTSIZE];
   static int counter=0;
   static Random ran=new Random();
   
   public static void main(String[] args)
   {
      //preperation at initialization
     //extra time does not impact the gameloop
           
      for(int i=0;i<RANDOMLISTSIZE;i++)
      {
         rans[i]=ran.nextBoolean();
      }
   
      //start timekeeping
     long start = System.currentTimeMillis();
     
      for (int i=0;i<100000000;i++)
      {
         //randomFromList();  //FAST
        randomFromRandom();    //SLOW      
     }
     
      //stop timekeeping, evaluate
     System.out.println(System.currentTimeMillis()-start+" ms :: "+ value);
     
   }
   
   static void randomFromList()
   {
      if(rans[counter++]) inc();
      else dec();        
      if(counter>=RANDOMLISTSIZE) counter=0;
   }

   static void randomFromRandom()
   {
      if(ran.nextBoolean()) inc();
      else dec();
   }
   
   static void inc()
   {
      value ++;
   }
   static void dec()
   {
      value --;
   }

}


In the end of the day, to know how fast something is compared to something else,
you need to MEASURE it...

Offline Roquen
« Reply #12 - Posted 2013-12-05 10:46:44 »

Could you guyz stop giving the stupid advice like "reuse the random object"
If you want reasonable advice, then you should pose the question you're asking and not one which you aren't.

@Damocles: your benchmark is flawed.
Offline Damocles
« Reply #13 - Posted 2013-12-05 10:57:10 »

Of course the output is not as random for HUGE amounts of random number,
but for up to RANDOMLISTSIZE sompletely random.


I made so many iterations to have an actual impact on speed to measure the effect.

Point was to proove that picking something from a list is simply faster (even in 2013)
than running a method of Random.

The approch to use depends of course what the aim is.
If you only need a random number every gameframe, it makes no sense.

If you need to have a LARGE amount of random numbers (millions), you
also should not take this approach,
But then, this is something you wont need in realtime anyhow (eg terrain generation or such)

Offline Varkas
« Reply #14 - Posted 2013-12-05 10:58:11 »

Which way would it be faster to do it, if we have 10000 actions to check?

The problem (and also the reason why you don't get the answers you want) is that there are many external dependencies which influence the speed. How clogged is your memory bus already? Is the code small enough to fit into the CPU cache? Will the hotspot compiler kick in and optimize the code?= If yes, how optimizable is the code? How big are the actions actually (the amount of code in each action)?

That's also why it is hard to becnhmark, since a benchmark can't simulate e.g. a clogged memory bus, and most likely is small enough to run in the cache and also be optimized. Which is not neccesarily the case in your real scneario.

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Offline Roquen
« Reply #15 - Posted 2013-12-05 11:00:35 »

@Damocles: It's slower to look up in a table.  Your benchmark is flawed.
Offline Damocles
« Reply #16 - Posted 2013-12-05 11:02:17 »

care to elaborate? Not what I measure..

Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #17 - Posted 2013-12-05 11:42:11 »

Roquen is right. A L3 cache miss can cost 100s of cycles, even L2 cache is many cycles, you can calculate a lot in that time. LUT are something that worked only a long time ago. Memory access is the dominate feature in performance on modern CPUs. Cache coherency is more or less everything.

Microbenchmarks are even worse with LUT at missleading people. Cache performance when doing the same things a million times back to back is not the same as doing something else in between each lookup.

Finally who cares. The thing you do in your branch is going to cost more cpu than this branch.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline ctomni231

JGO Wizard


Medals: 99
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #18 - Posted 2013-12-05 11:44:29 »

@op: If you just want an honest response, the less times you use 'new' the better. Everything else has such a minimal effect on speed that it doesn't matter.

Offline Troncoso

JGO Coder


Medals: 20



« Reply #19 - Posted 2013-12-05 12:30:25 »

Could you guyz stop giving the stupid advice like "reuse the random object"
I will now try to re-make my question.
Which way would it be faster to do it, if we have 10000 actions to check?

Why don't you do 10,000 iterations and time it? I don't get what you are doing here. Are you trying to get someone else to do it for you? If you have the code, then it's not hard to figure out.
Offline trollwarrior1
« Reply #20 - Posted 2013-12-05 12:34:31 »

Could you guyz stop giving the stupid advice like "reuse the random object"
I will now try to re-make my question.
Which way would it be faster to do it, if we have 10000 actions to check?

Why don't you do 10,000 iterations and time it? I don't get what you are doing here. Are you trying to get someone else to do it for you? If you have the code, then it's not hard to figure out.

Just doing it is no fun Cheesy Better discuss it first Cheesy:D
Offline Troncoso

JGO Coder


Medals: 20



« Reply #21 - Posted 2013-12-05 12:38:48 »

You aren't asking for discussion. People are discussing it and you are all "can you guys just tell me which is faster?"....
Offline trollwarrior1
« Reply #22 - Posted 2013-12-05 12:43:26 »

I made this little test.

Loop through 10000 if statements. It took 0.09milis.
Picking a action from action array which has 10000 members, it took about 0.0025

Ofcourse you will say that "this is not correct benchmark". But :: :
If there are only a few if statements, than using IF statements is a lot faster.
If you have a lot of stuff to check, better make a hashmap or a list or an array.
Offline Damocles
« Reply #23 - Posted 2013-12-05 12:53:51 »

see, actual Measurement is better than just theorising Wink

Offline trollwarrior1
« Reply #24 - Posted 2013-12-05 13:01:12 »

see, actual Measurement is better than just theorising Wink

I knew that already.
Offline Roquen
« Reply #25 - Posted 2013-12-05 13:14:12 »

Use an array (or a switch if sufficiently small number)

Quote
see, actual Measurement is better than just theorising
But only if the measurement is done correctly.

To expand on delt0r's comments.  It's true that the action is going to cost more than the dispatch in OPs question, but the reasoning is more generally interesting.

Don't use java.util.Random.  It's core generator requires a CAS, which with no contention is still very expensive (let's call it 50 cycles on average).  And that's dumb anyway because you don't want more than one thread using the same generator anyway (you become non-deterministic.  note this doesn't mean better quality...that's the same....you've made your life hell if you need to debug.  There's no upside.)  Instead use a custom PRNG or if you're unwilling then java.util.concurrent.ThreadLocalRandom.  If you take Damocles code and replace Random with ThreadLocalRandom, then the gap between the two will drastically drop (but is result is still meaningless).  Change to using an XORSHIFT then the generated version will be faster (on average across current-ish CPUs).
Offline theagentd
« Reply #26 - Posted 2013-12-05 13:19:28 »

see, actual Measurement is better than just theorising Wink
First of all, the list version gets noticeably slower if you run the test multiple times in a loop: 410ms first run to 458ms for subsequent runs. Secondly, microbenchmarks overstate the performance of lookup tables since nothing else is competing for cache space so the whole or a large part of the lookup table can be cached and reused. Hence, this benchmark is pretty useless in the first place. Sorry. Only a real-world performance test would make sense here.

Also, there's not a very big point in optimizing this specific part in the first place. Calculating 10 000 random values takes around 0.1ms for me. Would you ever need that many random values in a single frame? If you do, you have more problems with your algorithm than with the performance of your random number generator.

I'd say the answer to "Which is faster?" is "Does it matter?". Random is cleaner, shorter and has more predictable performance than a lookup table, so I'd go with it.

EDIT: Using ThreadLocalRandom as Roquen just suggested is around 10% faster than a lookup table:
List: 457.359 ms
ThreadLocalRandom: 410.875 ms

Myomyomyo.
Offline Roquen
« Reply #27 - Posted 2013-12-05 14:07:54 »

Now just for fun try an embedded XorShift and then an LCG.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
   
 static int data = 1|(int)System.nanoTime();
   
 /** Returns a uniform 32-bit integer. */
 public static final int nextInt()
 {
   if (false)
     data = 0xac549d55*data + 12345;  // LCG
  else {
     data ^= (data <<  13);           // XorShift
    data ^= (data >>> 17);
     data ^= (data <<   5);
   }
   return data;
 }

static void randomFromRandom()
{
   if (nextInt() < 0) inc(); else dec();
}


(EDIT: Opps...I forgot to disallow a seed of zero...bad me)
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #28 - Posted 2013-12-05 14:29:11 »

I use something very similar to Roquen's rng, its somewhere in the code section. It can generate 2^31 random numbers in seconds on modern machines. Not minutes. It is also "more random" than that stupid mersenne twister.

I have no special talents. I am only passionately curious.--Albert Einstein
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.

Nickropheliac (13 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

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

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

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

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

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

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

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

BurntPizza (47 views)
2014-08-09 21:09:32
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!