Is multiplication faster than array access?
java, optimization
Solution
Konrad Rudolph commented on the issues with the benchmarking. So I am ignoring the benchmark and focus on the question:
Is multiplication faster than array access?
Yes, it is very likely. It used to be the other way around 20 or 30 years ago.
Roughly speaking, you can do an integer multiplication in 3 cycles (pessimistic, if you don't get vector instructions), and a memory access costs you 4 cycles if you get it straight from the L1 cache but it is straight downhill from there. For reference, see
Latencies and throughput in Appendix C of the Intel 64 and IA-32 Architectures Optimization Reference Manual
Approximate cost to access various caches and main memory?
Herb Sutter's presentation on this very subject: Machine Architecture: Things Your Programming Language Never Told You
One thing specific to Java was pointed out by Ingo in a comment below: You also get bounds checking in Java, which makes the already slower array access even slower...
Problem
To my surprise I get a longer time (10 milliseconds) when "optimizing" multiplications by pregenerating the results in an array compared to the original 8 milliseconds. Is that just a Java quirk or is that general of the PC architecture? I have a Core i5 760 with Java 7, Windows 8 64 Bit. ``` public class Test { public static void main(String[] args) { long start = System.currentTimeMillis(); long sum=0; int[] sqr = new int[1000]; for(int a=1;a<1000;a++) {sqr[a]=a*a;} for(int b=1;b<1000;b++) // for(int a=1;a<1000;a++) {sum+=a*a+b*b;} for(int a=1;a<1000;a++) {sum+=sqr[a]+sqr[b];} System.out.println(System.currentTimeMillis()-start+"ms"); System.out.println(sum); } } ```