The Simplicity of Cache Efficient Functional Algorithms. - Clinger, William D. (Communications of the ACM, 2015)
The article discusses a study published within the journal that demonstrated a model for analyzing and describing the efficiency of functional algorithms. Topics discussed include the accuracy and complexity of cache-aware estimates of real-world performance, the use of asymptotic notation to describe costs, and cache-oblivious algorithms as an example of the use of abstraction to combine accurate cost estimates with tractability. Also mentioned are the correspondence between allocation order and memory order, the expression and analysis of efficient cache-oblivious functional algorithms, and the ability of computer scientists to improve both the simplicity and accuracy of models.