Dive Into Systems

11STORAGE AND THE MEMORY HIERARCHY

Although designing and implementing efficient algorithms is typically the most critical aspect of writing programs that perform well, there’s another, often overlooked factor that can have a major impact on performance: memory. Perhaps surprisingly, two algorithms with the same asymptotic performance (number of steps in the worst case) run on the same inputs might perform very differently in practice due to the organization of the hardware on which they execute. Such differences generally stem from the algorithms’ memory accesses, particularly where they store data and the kinds of patterns they exhibit when ...