Java multiplication strange behaviour
java
Solution
1.) Why is time taken for N=1 unusually greater than the N=10
Because it's the first time the VM has seen that code - it may decide to just interpret it, or it will take a little bit of time JITting it to native code, but probably without optimization. This is one of the "gotchas" of benchmarking Java.
2.) Why is time taken for N=10M and onwards unusually lower ?
At that point, the JIT has worked harder to optimize the code - reducing it to almost nothing.
In particular, if you run this code multiple times (just in a loop), you'll see the effect of the JIT compiler optimizing:
Time taken for 1 : 3732
Time taken for 10 : 1399
Time taken for 100 : 3266
Time taken for 1000 : 26591
Time taken for 10000 : 278508
Time taken for 100000 : 2496773
Time taken for 1000000 : 4745361
Time taken for 10000000 : 933
Time taken for 100000000 : 466
Time taken for 1000000000 : 933
Time taken for 1 : 933
Time taken for 10 : 467
Time taken for 100 : 466
Time taken for 1000 : 466
Time taken for 10000 : 933
Time taken for 100000 : 466
Time taken for 1000000 : 933
Time taken for 10000000 : 467
Time taken for 100000000 : 467
Time taken for 1000000000 : 466
Time taken for 1 : 467
Time taken for 10 : 467
Time taken for 100 : 466
Time taken for 1000 : 466
Time taken for 10000 : 466
Time taken for 100000 : 467
Time taken for 1000000 : 466
Time taken for 10000000 : 466
Time taken for 100000000 : 466
Time taken for 1000000000 : 466
As you can see, after the first the loop takes the same amount of time whatever the input (module noise - basically it's always either ~460ns or ~933ns, unpredictably) which means the JIT has optimized the loop out.
If you actually returned `j`, and changed the initial value of `i` to `1` instead of `0`, you'll see the kind of results you expect. The change of the initial value of `i` to `1` is because otherwise the JIT can spot that you'll always end up returning 0.
Problem
Have a look at the code below: ``` class Test { public static void main(String abc[]) { for( int N=1; N <= 1_000_000_000; N=N*10) { long t1 = System.nanoTime(); start(N); long t2 = System.nanoTime() - t1; System.out.println("Time taken for " + N + " : " + t2); } } public static void start( int N ) { int j=1; for(int i=0; i<=N; i++) j=j*i; } } ``` The output produced by the above question is: ``` Time taken for 1 : 7267 Time taken for 10 : 3312 Time taken for 100 : 7908 Time taken for 1000 : 51181 Time taken for 10000 : 432124 Time taken for 100000 : 4313696 Time taken for 1000000 : 9347132 Time taken for 10000000 : 858 Time taken for 100000000 : 658 Time taken for 1000000000 : 750 ``` Questions: 1.) Why is time taken for N=1 unusually greater than the N=10 ? (sometimes it even exceeds N=100) 2.) Why is time taken for N=10M and onwards unusually lower ? The pattern indicated in the above questions is profound and remains even after many iterations. Is there any connection to memoization here ? EDIT: Thank you for your answers. I thought of replacing the method call with the actual loop. But now, there is no JIT Optimization. Why not ? Is putting the statements in a method facilitating in the optimization process ? The modified code is below: ``` class test { public static void main(String abc[]) { for( int k=1; k<=3; k++) { for( int N=1; N<=1_000_000_000; N=N*10) { long t1 = System.nanoTime(); int j=1; for(int i=0; i<=N; i++) j=j*i; long t2 = System.nanoTime() - t1; System.out.println("Time taken for "+ N + " : "+ t2); } } } } ``` EDIT 2: The output of above modified code: ``` Time taken for 1 : 2160 Time taken for 10 : 1142 Time taken for 100 : 2651 Time taken for 1000 : 19453 Time taken for 10000 : 407754 Time taken for 100000 : 4648124 Time taken for 1000000 : 12859417 Time taken for 10000000 : 13706643 Time taken for 100000000 : 136928177 Time taken for 1000000000 : 1368847843 Time taken for 1 : 264 Time taken for 10 : 233 Time taken for 100 : 332 Time taken for 1000 : 1562 Time taken for 10000 : 17341 Time taken for 100000 : 136869 Time taken for 1000000 : 1366934 Time taken for 10000000 : 13689017 Time taken for 100000000 : 136887869 Time taken for 1000000000 : 1368178175 Time taken for 1 : 231 Time taken for 10 : 242 Time taken for 100 : 328 Time taken for 1000 : 1551 Time taken for 10000 : 13854 Time taken for 100000 : 136850 Time taken for 1000000 : 1366919 Time taken for 10000000 : 13692465 Time taken for 100000000 : 136833634 Time taken for 1000000000 : 1368862705 ```