Which is faster? :P

[trollwarrior1]

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(); }

[Roquen]

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 }

[trollwarrior1]

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!

[Damocles]

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.

[Roquen]

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.

[Abuse]

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.

[Damocles]

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?

[Roquen]

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

Pseudo random is deterministic.  That's a good thing.

[trollwarrior1]

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?

[Varkas]

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.

Games published by our own members! Check 'em out!

[Abuse]

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.

[Damocles]

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...

[Roquen]

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.

[Damocles]

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)

[Varkas]

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.

[Roquen]

@Damocles: It's slower to look up in a table.  Your benchmark is flawed.

[Damocles]

care to elaborate? Not what I measure..

[delt0r]

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.

[ctomni231]

@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.

[Troncoso]

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.

[trollwarrior1]

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 Better discuss it first :D

[Troncoso]

You aren't asking for discussion. People are discussing it and you are all "can you guys just tell me which is faster?"....

[trollwarrior1]

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.

[Damocles]

see, actual Measurement is better than just theorising

[trollwarrior1]

see, actual Measurement is better than just theorising

I knew that already.

[Roquen]

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

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).

[theagentd]

see, actual Measurement is better than just theorising

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

[Roquen]

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)

[delt0r]

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.