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) { }else if(rand == 1) { } |
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
| Action[] actions = { new Action() { public void doAction() { } }, new Action() { public void doAction() { } }};
Random random = new Random(); int rand = random.nextInt(2);
acionts[rand].doAction();
interface Action { public void doAction(); }
|
|
|
|
|
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
|
if (rng.nextInt() < 0) { } else { }
|
|
|
|
|
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!
|
|
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.
|
|
|
|
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.
|
|
|
|
Abuse
|
 |
«
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.
|
|
|
|
Damocles
|
 |
«
Reply #6 - Posted
2013-12-05 10:07:11 » |
|
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
|
 |
«
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.
|
|
|
|
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?
|
|
|
|
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.
|
|
|
|
Games published by our own members! Check 'em out!
|
|
Abuse
|
 |
«
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.
|
|
|
|
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; static boolean[] rans=new boolean[RANDOMLISTSIZE]; static int counter=0; static Random ran=new Random(); public static void main(String[] args) { for(int i=0;i<RANDOMLISTSIZE;i++) { rans[i]=ran.nextBoolean(); } long start = System.currentTimeMillis(); for (int i=0;i<100000000;i++) { randomFromRandom(); } 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
|
 |
«
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.
|
|
|
|
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)
|
|
|
|
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.
|
|
|
|
Roquen
|
 |
«
Reply #15 - Posted
2013-12-05 11:00:35 » |
|
@Damocles: It's slower to look up in a table. Your benchmark is flawed.
|
|
|
|
Damocles
|
 |
«
Reply #16 - Posted
2013-12-05 11:02:17 » |
|
care to elaborate? Not what I measure..
|
|
|
|
delt0r
|
 |
«
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
|
|
|
ctomni231
|
 |
«
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.
|
|
|
|
Troncoso
|
 |
«
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.
|
|
|
|
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  Better discuss it first  :D
|
|
|
|
Troncoso
|
 |
«
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?"....
|
|
|
|
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.
|
|
|
|
Damocles
|
 |
«
Reply #23 - Posted
2013-12-05 12:53:51 » |
|
see, actual Measurement is better than just theorising 
|
|
|
|
trollwarrior1
|
 |
«
Reply #24 - Posted
2013-12-05 13:01:12 » |
|
see, actual Measurement is better than just theorising  I knew that already.
|
|
|
|
Roquen
|
 |
«
Reply #25 - Posted
2013-12-05 13:14:12 » |
|
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
|
 |
«
Reply #26 - Posted
2013-12-05 13:19:28 » |
|
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
|
Myomyomyo.
|
|
|
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(); public static final int nextInt() { if (false) data = 0xac549d55*data + 12345; else { data ^= (data << 13); 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
|
 |
«
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
|
|
|
|