Why does cache locality matter for array performance?

See my answer about spatial and temporal locality.

In particular, arrays are contiguous memory blocks, so large chunks of them will be loaded into the cache upon first access. This makes it comparatively quick to access future elements of the array. Linked lists on the other hand aren’t necessarily in contiguous blocks of memory, and could lead to more cache misses, which increases the time it takes to access them.

Consider the following possible memory layouts for an array data and linked list l_data of large structs

Address      Contents       | Address      Contents
ffff 0000    data[0]        | ffff 1000    l_data
ffff 0040    data[1]        |   ....
ffff 0080    data[2]        | ffff 3460    l_data->next
ffff 00c0    data[3]        |   ....
ffff 0100    data[4]        | ffff 8dc0    l_data->next->next
                            | ffff 8e00    l_data->next->next->next
                            |   ....
                            | ffff 8f00    l_data->next->next->next->next

If we wanted to loop through this array, the first access to ffff 0000 would require us to go to memory to retrieve (a very slow operation in CPU cycles). However, after the first access the rest of the array would be in the cache, and subsequent accesses would be much quicker. With the linked list, the first access to ffff 1000 would also require us to go to memory. Unfortunately, the processor will cache the memory directly surrounding this location, say all the way up to ffff 2000. As you can see, this doesn’t actually capture any of the other elements of the list, which means that when we go to access l_data->next, we will again have to go to memory.

Related Posts:

  1. Array versus linked-list
  2. What is an idempotent operation?
  3. What is dependency injection?
  4. What is a callback function?
  5. What are bitwise shift (bit-shift) operators and how do they work?
  6. What is the difference between a deep copy and a shallow copy?
  7. What is the difference between concurrency and parallelism?
  8. How Does Modulus Divison Work
  9. What is the difference between a framework and a library?
  10. What exactly is GUID? Why and where I should use it?
  11. What is an invariant?
  12. Prefer composition over inheritance?
  13. What are sessions? How do they work?
  14. What does ‘foo’ really mean? [closed]
  15. How is Python’s List Implemented?
  16. Converting EBNF to BNF
  17. Array of Linked Lists C++
  18. What is tail recursion?
  19. How to dynamically allocate arrays in C++
  20. How do I determine whether an array contains a particular value in Java?
  21. TypeError: only size-1 arrays can be converted to Python scalars (matplotlib)
  22. How to add elements to an empty array in PHP?
  23. How can I remove a specific item from an array?
  24. Explanation on Integer.MAX_VALUE and Integer.MIN_VALUE to find min and max value in an array
  25. Converting array to list in Java
  26. “Parameter” vs “Argument”
  27. Split string into array
  28. How to create an associative array in JavaScript literal notation
  29. How can I create a two dimensional array in JavaScript?
  30. How can I create a two dimensional array in JavaScript?
  31. How to split a string into an array in Bash?
  32. What is an “internal error” and how do I fix it?
  33. Printing out a linked list using toString
  34. Short circuit Array.forEach like calling break
  35. How to convert List to int[] in Java?
  36. Deleting array elements in JavaScript – delete vs splice
  37. How to convert an ArrayList containing Integers to primitive int array?
  38. Convert an integer to an array of characters : java
  39. How to convert int[] into List in Java?
  40. How to efficiently remove duplicates from an array without using Set
  41. Static array vs. dynamic array in C++
  42. Python: Write array values into file
  43. How to create a dynamically-allocated array of const objects, but have values assigned to them?
  44. Remove Object from Array using JavaScript
  45. Print singly linked list in reverse order
  46. What is the difference between ( for… in ) and ( for… of ) statements?
  47. Fill array with random numbers within a specified range (C++)
  48. Remove an array element and shift the remaining ones
  49. How to normalize a 2-dimensional numpy array in python less verbose?
  50. How can I create an array of linked lists in java?
  51. How can I create an array of linked lists in java?
  52. How do I remove an array item in TypeScript?
  53. How can I create an Array of ArrayLists?
  54. How to find the size of an int[]?
  55. How to print a char array in C through printf?
  56. How to clear all the elements of array in C?
  57. Python Array Rotation
  58. How can I create an array/list of dictionaries in python?
  59. How to create an array of strings in C?
  60. Sorting arrays in javascript by object key value
  61. Ruby: undefined method `[]’ for nil:NilClass when trying to get Enumerator on an Array of Hashes
  62. TypeError: Invalid dimensions for image data when plotting array with imshow()
  63. List of Arrays in Java
  64. PHP multidimensional array search by value
  65. Counting an Occurrence in an Array (Java)
  66. Correct way to work with vector of arrays
  67. Resizing dynamic array in c++
  68. How to create a generic array in Java?
  69. Get a random item from a JavaScript array
  70. Using numpy to build an array of all combinations of two arrays
  71. TypeError: only integer arrays with one element can be converted to an index 3
  72. Java ArrayList for integers
  73. Reading data from file into an array
  74. How to change value of object which is inside an array using JavaScript or jQuery?
  75. Add String Array to ArrayList
  76. Java Array Sort descending?
  77. use Lodash to sort array of object by value
  78. Any way to declare an array in-line?
  79. C++ pass an array by reference
  80. Is there any numpy group by function?
  81. Sort array of objects by single key with date value
  82. How can I find the number of elements in an array?
  83. Array type char[] is not assignable
  84. Parameter name omitted error?
  85. Mean Squared Error in Numpy?
  86. How to iterate through table in Lua?
  87. How to sort in-place using the merge sort algorithm?
  88. java.lang.ArrayIndexOutOfBoundsException: 0
  89. Complex JSON nesting of objects and arrays
  90. PHP array delete by value (not key)
  91. Printing from a declared array in MIPS
  92. typedef fixed length array
  93. When should I use a List vs a LinkedList
  94. Create an empty object in JavaScript with {} or new Object()?
  95. PHP Multiple Checkbox Array
  96. Find a value in an array of objects in Javascript [duplicate]
  97. Checking if a key exists in a JavaScript object?
  98. How to push both value and key into PHP array
  99. Convert an array to string
  100. Shuffle an array with python, randomize array item order with python

Leave a Comment