Array access pretty slow

Performance Tuning
#1

Lastly I tried an optimization in a frequently executed piece of code: 3 variables of small size needed to be saved in a sort of “stack array” of fixed size. In the first version each variable was stored and retrieved from an individual array.

After packing all info into one single array with shifting and oring (saving two array acceses), the code was significantly faster! Obviously array access is much more expensive than a few bit-ops…

But how expensive is it really? I would guess it takes at least two condition checks for the bounds and one multiplication to calculate the address. Does anyone know exactly?

#2

It doesn’t likely take a multiply to calculate the address… more likely a shift or perhaps even a native addressing mode of the processor, since the sizes of array entries are always powers of two.

byte = 1
char/short = 2
int/float/obj. ref. = 4
long/double/(obj.ref. 64-bit VM) = 8

You are timing both bounds checking AND memory bandwidth. In your packed version there is a single memory access and the shifts and stuff will happen in registers.

#3

You say its a stack.

java Arrays are a very inefficient way to do stacks. if this can be coded recursive where the stack is implied on the system stack youll get much better performance.

The reason is bounds-checking. The Vm doesnt knwo what you have is a stack so it treats every access as dangerous. The system stack is implemented with that knowledge and cna be much more efficient. (In the Hotspot case it just puts a memory trap right above and right below the stack.)

#4

Oh, that was a lighning fast reply :o

No, unfortunately i can’t (or at least it would be very messy) implement the stack with recursion.

Another question: generally what is faster, 2 accesses to arrays with length 64 or 1 access to an array with 4096 length? I suppose this depends on CPU caching… so it’s platform dependant… a rule of thumb?

Have a nice day!