Data types

Strictness annotations

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
import Data.Foldable (foldl')

data Foo = Foo Int
  deriving Show
data Bar = Bar !Int
  deriving Show
newtype Baz = Baz Int
  deriving Show

main :: IO ()
main = do
  print $ foldl'
    ((Foo total) x -> Foo (total + x))
    (Foo 0)
    [1..1000000]
  print $ foldl'
    ((Bar total) x -> Bar (total + x))
    (Bar 0)
    [1..1000000]
  print $ foldl'
    ((Baz total) x -> Baz (total + x))
    (Baz 0)
    [1..1000000]

• Lots of thunk allocation with Foo
• What about Bar vs Baz? A few differences.

Advantages of strictness annotations:

• Avoid space leaks
• No hidden bottom values
• GHC errors out when you forget a field

Recommendation: if you don’t need laziness in a field, make it strict.

Pattern matching

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
import Data.Foldable (foldl')
import UnliftIO.Exception (pureTry)

data Foo = Foo Int
  deriving Show
data Bar = Bar !Int
  deriving Show
newtype Baz = Baz Int
  deriving Show

main :: IO ()
main = do
  print $ pureTry $
    case Foo undefined of
      Foo _ -> "Hello World"
  print $ pureTry $
    case Bar undefined of
      Bar _ -> "Hello World"
  print $ pureTry $
    case Baz undefined of
      Baz _ -> "Hello World"

Memory layout

• Foo contains:
  • Data constructor (one word)
  • Pointer to Int (one word)
  • Int has a data constructor (one word)
  • Int has a payload Int# (we’ll get to later, one word)
• Bar in theory has the exact same thing, but wait till next section
  • Strictness does not directly affect memory layout
• Baz is a newtype, guaranteed to have no runtime representation
  • Int itself is still two words
  • In ideal situations, GHC can avoid the data constructor, we’ll say that with GHC core later

Unpack

That extra Int data constructor is annoying, get rid of it!

data Bar = Bar {-# UNPACK #-} !Int

• Inlines the contents of Int into the Bar representation
• Avoids extra headers and pointers
• Only works on:
  • Strict fields
  • Non-polymorphic fields
  • Type must have a single data constructor types
  • Question Why?
• Bonus: applied automatically to primitive types (like Int)
• In practice: don’t need {-# UNPACK #-} on Int
  • Personally, I’ll still add it for clarity often

Why not always unpack fields? It can be a pessimization with large data types due to copying lots of data instead of copying a single pointer. If the value is a machine word, it’s always better to unpack, thus the primitive type optimization.

What’s in an Int?

Int is defined in normal Haskell code, it’s not a GHC built-in. Don’t believe me?

https://www.stackage.org/haddock/lts-12.21/ghc-prim-0.5.2.0/GHC-Types.html#t:Int

data Int = I# Int#
data Word = W# Word#

Magic hash!

$ stack exec -- ghci -XMagicHash
GHCi, version 8.0.1: https://www.haskell.org/ghc/  :? for help
Prelude> import GHC.Prim
Prelude GHC.Prim> :k Int#
Int# :: TYPE 'GHC.Types.IntRep

Int# is the magic, built-in value provided by GHC, in the ghc-prim package.

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types

main :: IO ()
main = print $ I# (5# +# 6#)

Going low level

High level, good code:

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script

main :: IO ()
main = print $ sum [1..100 :: Int]

Hopefully GHC optimizes this into a tight loop. But let’s write that tight loop manually:

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE BangPatterns #-}
main :: IO ()
main = print $ loop 0 1
  where
    loop !total i
      | i > 100 = total
      | otherwise = loop (total + i) (i + 1)

• Why did I put a bang on total but not i?
• Can you rewrite that function without the bang?

OK, let’s get primitive!

#!/usr/bin/env stack
-- stack --resolver lts-12.21 script
{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types

main :: IO ()
main = print $ I# (loop 0# 1#)
  where
    loop total i
      | isTrue# (i ># 100#) = total
      | otherwise = loop (total +# i) (i +# 1#)

• Basically no need to ever do this
• GHC should always be smart enough to do it for you
• But good to understand that GHC is optimizing to this
• Important for reading core

Sum type representation

• Data constructor: one word, tells us which constructor
• Remaining fields follow

Example:

data Foo = Bar !Int !Int | Baz !Int | Qux

How much memory needed for:

• Bar 5 6
• Baz 5
• Qux

Constructors with no fields (like Qux or Nothing): one copy in memory shared by all usages.

Compare the following:

data Result = Success !Int | Failure
data MaybeResult = SomeResult !Result | NoResult

Versus:

data MaybeResult = Success !Int
                 | Failure
                 | NoResult

• Semantically: identical
• Calculate memory representation of each

Takeaway: if performance is crucial, consider “inlining” layered sum types. Downside:

Pointer tagging

https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/HaskellExecution/PointerTagging

• Pointers are always machine-word aligned
• That means lowest 2 bits (3 bits on 64-bit archs) are always 0
• So… encode some useful info there!
  • All zeros == thunk
  • Other value tells you the constructor type
  • Can avoid a pointer indirection when caseing
• Pointer tagging only works for less than 4 data constuctors (8 on 64 bit)

Subscribe to our blog via email

Email subscriptions come from our Atom feed and are handled by Blogtrottr. You will only receive notifications of blog posts, and can unsubscribe any time.