CODEWITHSUNDEEP
haskelloptimizationreal-timeimmutabilityghc
MasterMastic
MasterMastic

Reputation: 21306

When does GHC internally mutate immutable values?

I wish to use Haskell for a realtime application that consists of a ever-changing heavy state.

The state is immutable, of course, so at every state-step I will re-create a new slightly-changed state and discard the old one. It would turn out painfully inefficient in this instance, because I have no need for the previous states.

I often encountered people saying that GHC can optimize those kind of stuff and internally mutate immutable values, and I want to make sure that it will.

Is it possible? is there a way to determine if GHC will optimize it by internally mutating the value? is there a way to enforce it / make sure it will?

P.S. Is there a formal name for this optimization?

Upvotes: 3

Views: 547

Answers (3)

Yuras
Yuras

Reputation: 13876

AFAIK ghc doesn't perform such the optimization in general case. It probably requires unique types.

But its runtime is optimized for such "slightly-changed state" case. Usually your state is (or can be represented as) something like a tree, and most of manges actually reuse most of existing tree. So modification operated only few pointers, and is very efficient. Consider the example:

data State = State
  { theA :: A
  , theB :: B
  }

data A = A Int
data B = B String

modifyTheA :: (A -> A) -> State -> State
modifyTheA f s = s {theA = f (theA s)}

Here modifyTheA function creates new State, but it is just two pointers. The whole theB string is reused.

Upvotes: 4

Jeremy List
Jeremy List

Reputation: 1766

GHC does this optimization on one condition: if an object is used once in the function where it's declared and no additional references to it are created. It isn't applied if the object is created and used in separate functions unless the source function is inlined.

There is another related optimization that GHC does more reliably. If a function's last action is to call itself with mostly the same arguments then it won't even touch the arguments that are unchanged.

Upvotes: 2

leftaroundabout
leftaroundabout

Reputation: 120741

GHC itself doesn't do this. Various container libraries use a trick called stream fusion, which means some copies that the pure-functional code suggests aren't actually ever made – but this is still not true "internal mutation", rather it groups together multiple operations that would each involve a copy to one single big operation with still only one copy.

I don't think it's really feasible to get true "mutation-optimisation" in a fully automatic way; some languages like Mercury kind of claim they do it, but I don't really know how well it works.

However, a good pure functional language like Haskell is quite capable of explicitly dealing with mutable state: through monads. This can either be the "omnipotent" IO monad (somewhat frowned upon because you lose all ref-transp. guarantees, but for a realtime application this is probably the right thing), or the specialised ST monad, whose purpose is specifically to allow you using true mutable state while keeping the outside behaviour of the program purely-functional.
If you take such an approach, you not only make sure there won't be costly copies made, you also probably end up with nicer code. Because sometimes mutation is just the right way to think about some problem; even code that's really pure-functional sometimes gets nicer if you "pretend" to use mutable state, in the State monad.

Upvotes: 9

Related Questions