Cache-Oblivious Data Structures

As of March 2020, School of Haskell has been switched to read-only mode.

Cache-Oblivious Data Structures show that by optimizing for any one cache with unknown parameters you simultaneously optimize for all caches asymptotically.

As we get more and more caches, this model becomes more and more "true" over time, and the ability for hand-written code to exceed it by using the cache parameters is lessened by each additional cache we add to the system.

  • Part I: Deamortized ST 8 Nov 2013Edward Kmett

    This is a slow exploration of a novel approach to deamortization in Haskell, that lets us implement more algorithms with a fully functional persistent API, with previously unachievable asymptotics.