I am learning python data structures and came across list being cache friendly. Can anyone please explain this in layman terms? What is locality of reference? and how is reference to an element of list is stored in array?
Python lists use contiguous blocks of memory to make indexing fast. In memory, you can imagine a list holding strings would look like this:
0x3334
+----+----+----+----+----+
| "S"| "t"| "a"| "c"| "k"| <-- Data stored at specific memory location
+----+----+----+----+----+
0x1 0x2 0x3 0x4 0x5 <-- Memory Addresses
With the contiguous block of memory referenced by 0x3334 and the individual indices of the block referenced with 0x1, 0x2...
CPUs use a CPU cache to store memory in a hierarchy of importance, ranging from data that is most recently used, to least recently used. When data is stored contiguously (like in Python lists), you get a large chunk of memory allocated for the list in the heap. When the list is created, it will store this data in the most recently used level of the CPU cache to retrieve the list quickly.
Locality of reference is relevant here because the way CPU caches are commonly designed is that data that is most recently used is more likely to be used again compared to data that hasn't been used in a long time, which is unlikely to be used again.
For example, if you have a variable that isn't used that much in a program, it is unlikely that it will be used that much in the program as the program executes in the processor, so you don't have to call the data at the memory address referenced by that variable many times from the CPU cache. If you have a variable in a loop, then it will be retrieved from memory storage many times since it's in a loop and it will always remain in the most recently used level of the CPU cache (typically the RAM).
There is a high cost attributed to accessing the least recently used level of the CPU cache. This cost is in time (CPU clock cycles). If your CPU checks the most recently used level of the cache and sees that the data of the contiguous block of allocated memory for the list isn't there, it will check subsequent levels of the cache (level 1, level 2, ... , main memory), until it reaches the main memory which is the slowest memory to retrieve from because it's usually physically farther away from the CPU on a motherboard. The fastest memory to retrieve from is the RAM because it's usually physically closer to the CPU, or in some CPUs it is a component of the CPU itself.
Therefore, Python lists are cache friendly because the memory allocated in a cache is contiguous for quick retrieval speed from storage.