This section will be easier to understand if you are familiar with the memory hierarchy on modern processors.
Performance considerations
Array based implementations of collections will generally show slightly better performance than linked list implementations. This will only be in the constant factor: scanning both arrays and linked lists is basically an O(n) operation. However, a number of factors contribute to slightly better performance of arrays:- The address of the next element in an array may be calculated from a current address and an element size - both held in registers:
(next)address := (current)address + size Both addresses may use a single register. Since no memory accesses are required, this is a single-cycle operation on a modern RISC processor. - Using arrays, information is stored in consecutive memory locations: this allows the long cache lines of modern processors to be used effectively. The part of the cache line which is "pre-fetched" by accessing the current element of an array contains part of the next array element. Thus no part of the cache or the CPU<->memory bandwidth is "wasted" by not being used. In contrast, with linked list implementations:
- There is additional overhead for pointers (and the overhead normally introduced by memory allocators like malloc). This means that fewer elements can fit into a single cache line.
- There is no guarantee that successive elements in a list occupy successive memory locations. This leads to waste of memory band-width, because elements pre-fetched into the cache are not necessarily used.
