Home
Faster Laziness Using Dynamic Pointer Tagging

Alexey
<!--
   * Set PREV_SKIN = customtitle
   * Set CUSTOMTOPICTITLE = Faster Laziness Using Dynamic Pointer Tagging
   * Set CUSTOMHEADTITLE = Faster Laziness Using Dynamic Pointer Tagging
   * Set WEBTITLE =
-->

_Simon Marlow, Alexey Rodriguez Yakushev and Simon Peyton Jones. At the [[http://www.informatik.uni-bonn.de/~ralf/icfp07.html][2007 ACM SIGPLAN International Conference on Functional Programming]]_

In the light of evidence that Haskell programs compiled by GHC exhibit
large numbers of mispredicted branches on modern processors, we
re-examine the "tagless" aspect of the STG-machine that GHC uses as
its evaluation model.  

We propose two tagging strategies: a simple strategy called
semi-tagging that seeks to avoid one common source of unpredictable
indirect jumps, and a more complex strategy called dynamic
pointer-tagging that uses the spare low bits in a pointer to encode
information about the pointed-to object.  Both of these strategies
have been implemented and exhaustively measured in the context of a
production compiler, GHC, and the paper contains detailed descriptions
of the implementations.  Our measurements demonstrate significant
performance improvements (14% for dynamic pointer-tagging with only a
2% increase in code size), and we further demonstrate that much of the
improvement can be attributed to the elimination of mispredicted
branch instructions.

As part of our investigations we also discovered that one optimisation
in the STG-machine, vectored-returns, is no longer worthwhile and we
explain why.

*Paper:* ([[%ATTACHURL%/ptr-tagging.pdf][pdf]])

---++ Implementation
Dynamic Pointer Tagging (and tagging of function pointers) has been already implemented in GHC. From version 6.8 and onwards the optimisation will be available to users of stable versions of GHC.

-- Main.AlexeyRodriguez - 11 Oct 2007