Cache Friendly Code
Computer science was developed in the mid-20th century, when computers hardly existed, but nevertheless, by the 1980s, most of the useful data structures and algorithms had been discovered and refined. Algorithmic complexity analysis is a topic that anyone who learns computer science encounters – and there are well-accepted textbook definitions of the complexity of data structure operations. However, after 50 years since these things were analyzed, computers have evolved in a way that is quite different from what could have been envisaged. For example, a common "fact" is that the list data structures are faster for insertion operations than arrays. This seems like common sense because inserting an element into an array involves moving all the items after that point to new locations, whereas inserting into a list is merely a few pointer manipulations. We will test this hypothesis in the following exercise.