-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|433|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Link Home -> Help/Tutorials

 
HoboBen
Created : 19 December 2011
Edited : 21 December 2011

Spacial Locality of Reference

Spacial Locality of Reference: an Efficient Access Pattern in any Cache System

https://www.tophatstuff.co.uk/?p=119
Did you know that looping through an array by Y and then X can be faster than looping by X and then Y?

Simply changing the order in which you loop when accessing memory can, even in real world cases, speed up your program by 650%!

Iterating through an Unsigned Char array:


Iterating through a Signed Integer array:


Continued at: Spacial Locality of Reference: an Efficient Access Pattern in any Cache System

---

This is the first article that I've written in a while; hope you like it!

 

Comments
Tuesday, 20 December 2011, 04:01
HoboBen
 		Now with a new graph!

Notice the spikes that appear in the benchmarks.

Looking at the Unsigned Char benchmark, the first spike occurs at an array width of 1024. Squaring this value gives an array size of 1024x1024 bytes, or one megabyte. This is the exact size of my CPU's Level 2 Cache! (Yes, my computer is old!). Therefore, it is reasonable to assume that these spikes correlate to cache sizes.
Wednesday, 21 December 2011, 17:12
Jayenkai
 		Interesting stuff!

I use arrays EVERYWHERE, so things like this are interesting to me.
I say that... I rarely give a crap.. But on slower systems like DS Homebrew, it's these little tidbits that let you throw the most into a game, and get something half-working out the other side.

For a long long time I've given up on "proper" multidimensional arrays, instead opting for the array[(y*limit)+x] approach.
I'm sure the extra chunk of maths doesn't actually help in that respect..
Thursday, 22 December 2011, 20:05
9572AD
 		IIRC from my old 8-bit BASIC days, it depends on the implementation of multi-dimensional arrays which is faster.
Friday, 23 December 2011, 03:13
HoboBen
 		Yup, Fortan and MATLAB are big exceptions