What is meaning of locality of data structure?

Question

I was reading following article,

What Every Programmer Should Know About Compiler Optimizations

There are other important optimizations that are currently beyond the capabilities of any compiler—for example, replacing an inefficient algorithm with an efficient one, or changing the layout of a data structure to improve its locality.

Does that mean if I change sequence (layout) of data members in class, it can affect performance?

So,

class One
{
int data0;
abstract-data-type data1;
};

Differes in performance from,

class One
{
abstract-data-type data0;
int data1;
};

If this is true, what is rule of thumb while defining classes or data structure?

Take a look at [THIS](http://blogs.msdn.com/b/vcblog/archive/2013/09/11/introducing-gw-compiler-switch.aspx) link. — LPs, Feb 04 '15 at 07:31
@LPs Thanks for link.. how much one should learn to use C++;) — Pranit Kothari, Feb 04 '15 at 07:36
[cache locality in practice](http://stackoverflow.com/questions/28179820/running-in-parallel-on-a-shared-memory-quad-core-computer-using-4-threads/28181831#2818183) — qqibrow, Feb 04 '15 at 18:10

score 4 · Accepted Answer · answered Feb 04 '15 at 07:26

Locality in this sense is speaking mostly to cache locality. Writing data structures and algorithms to operate mostly out of cache makes the algorithm run as fast as it possibly can. Cache locality is one of the reasons quick sort is quick.

For a data structure, you want to keep the parts of your data structure that refer to each other relatively close to each other, to avoid flushing out useful cache lines.

Also, you can rearrange your data structure so that the compiler will use the minimum amount of memory required to hold all the members and still efficiently access them. This helps make sure your data structure consumes the minimum number of cache lines.

_{A single cache line on a current x86-64 architecture (core i7) is 64 bytes.}

code_fodder · Answer 2 · 2015-02-04T07:36:01.610

I am not an expert on data/structure locality, but it has to do with how you organize your data to avoid the CPU caching bits of memory from all over the CPU thus slowing down your program by constantly waiting for a memory fetch.

For example, a linked list can be a scattered all over your memory. However if you changed this into an array of "elements" then they are all in contiguous memory - this would save memory access times if you needed to traverse they array all at one time (its just one example)

Additionally: Also becareful of some of the STL libraries, again I am not 100% sure which are the best, but some of them (e.g. list) are quite bad in terms of locality. Another , perhaps more common example is an array of pointers, where the pointed to elements can be scattered around memory. Of course, you cannot always avoid this easily because you sometimes need to be able to dynamically add/move/insert/delete elements...

Summary: It basically means take care how you layout your data with regard to memory access.

score 0 · Answer 3 · answered Feb 04 '15 at 07:30

Sort class members by how frequently you will be accessing them. This maximizes the "hotness" of the cache line that contains the head of your class, increasing the likelihood of it remaining cached. Another factor that you care about is packing - due to alignment, rearranging the order in which members are declared could lead to a reduction in the size of your class which would in turn reduce cache pressure.

(None of them are definitive, of course. These rules of thumb aren't a substitute for profiling.)

What is meaning of locality of data structure?

3 Answers3