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.
, 1998