Prefetching in Functional Languages

Sam Ainsworth, Timothy M Jones

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Functional programming languages contain a number of runtime and language features, such as garbage collection, indirect memory accesses, linked data structures and immutability, that interact with a processor’s memory system. These conspire to cause a variety of unintuitive memory-performance effects. For example, it is slower to traverse through linked lists and arrays of data that have been sorted than to traverse the same data accessed in the order it was allocated.

We seek to understand these issues and mitigate them in a manner consistent with functional languages, taking advantage of the features themselves where possible. For example, immutability and garbage collection force linked lists to be allocated roughly sequentially in memory, even when the data pointed to within each node is not. We add language primitives for software-prefetching to the OCaml language to exploit this, and observe significant performance improvements a variety of micro- and macro-benchmarks, resulting in speedups of up to 2× on the out-of-order superscalar Intel Haswell and Xeon Phi Knights Landing systems, and up to 3× on the in-order Arm Cortex-A53.
Original languageEnglish
Title of host publicationProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management
Place of PublicationNew York, NY, USA
PublisherACM Association for Computing Machinery
Number of pages14
ISBN (Print)9781450375665
Publication statusPublished - 16 Jun 2020
Event2020 ACM SIGPLAN International Symposium on Memory Management -
Duration: 16 Jun 202016 Jun 2020

Publication series

NameISMM 2020
PublisherAssociation for Computing Machinery


Conference2020 ACM SIGPLAN International Symposium on Memory Management
Abbreviated titleISMM 2020
Internet address


  • OCaml
  • Software Prefetching
  • Functional Programming
  • Hardware Prefetching

Fingerprint Dive into the research topics of 'Prefetching in Functional Languages'. Together they form a unique fingerprint.

Cite this