Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is meaning of locality of data structure?

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?

like image 279
Pranit Kothari Avatar asked Feb 04 '15 07:02

Pranit Kothari


People also ask

What is locality in data structure?

Spatial locality (also termed data locality) refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as traversing the elements in a one-dimensional array.

What does locality mean?

1 : the fact or condition of having a location in space or time. 2 : a particular place, situation, or location.

What is locality in coding?

Locality refers to the ability to perform operations like decoding/correction/testing in sublinear or sometimes constant time. For example, a constant query locally decodable code (LDC) allows decoding of any message bit in constant time given a corrupted encoding of the message.

What is locality in DBMS?

Locality of reference refers to a phenomenon in which a computer program tends to access same set of memory locations for a particular time period. In other words, Locality of Reference refers to the tendency of the computer program to access instructions whose addresses are near one another.


1 Answers

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.

like image 163
jxh Avatar answered Sep 21 '22 23:09

jxh