leaky-0.1.0.0: HTML/leaky.html
<!DOCTYPE html>
<html>
<head>
<title>Leaky: Minimal robust Haskell space leak</title>
<link rel="stylesheet" href="style.css" />
</head>
<body>
<div class="main">
<a id="r1"></a>
<!--h3>Space Leak : A Haskell Sore Spot</h3-->
<h2 style="margin-top: 50px; margin-bottom: 10px;">Space Leak</h2>
<h3 style="margin-top: 12px; color: #666;">A Haskell Sore Spot</h3>
When a program retains memory longer than the programmer expects,<br />
it is said to <span><em>leak space</em>. <a href="#1">[1]</a></span>
<p>
<!-- http://neilmitchell.blogspot.ca/2013/11/acm-article-leaking-space.html -->
Quoting from Neil Mitchell's 2013 <a href="http://queue.acm.org/detail.cfm?id=2538488">article</a> in <em>ACM Queue</em>:
<p>
<em style="display: block; margin-left: 15px; margin-right: 100px;">
"[Writers of] compilers for lazy functional languages have been dealing with space leaks for more than 30 years and have developed a number of strategies to help.
...
Despite all the improvements, space leaks remain a thorn in the side of lazy evaluation, producing a significant disadvantage to weigh against the benefits."
<p>
"Pinpointing space leaks is a skill that takes practice and perseverance. Better tools could significantly simplify the process."
</em>
<p>
<a id="r2"></a>
The Haskell applications programmer is well aware that space leak poses a significant impediment to <span>development. <a href="#2">[2]</a></span>
In fact, any large Haskell program, even carefully coded by skilled programmers, will typically exhibit space leak compounded of multiple causes.
The most serious cases are catastrophic, requiring urgent measures for development and testing to proceed.
Such dire leaks can arise several times per week.
<p>
<a id="r3"></a>
All space leak degrades performance, and production-quality programs should eradicate as much leak behaviour as <span>possible. <a href="#3">[3]</a></span>
Difficulty ranges from distracting (minutes) to formidable (days, or worse).
This steers development resources away from the application domain, forcing one to resort to bag-of-tricks hackery in attempting to isolate and resolve the more serious leaks as they arise.
Understanding what's going on requires thinking about memory at a low level, and the abstractions involved are more complex than traditional block allocation.
For space leak debugging, the current best practises constitute a black art.
Leak behaviour is also extremely sensitive to build configuration (compiler version, and flags such as optimisation level).
<p>
<a id="r4"></a>
The problem stems from the lazy evaluation model of <span>Haskell <a href="#4">[4]</a></span>
which has been discussed at length elsewhere (see <a href="#Related">Related</a>).
<p>
<h3>What can we do?</h3>
This situation seems pretty hopeless. Can anything be done?
<p>
Of course! We can keep studying the phenomenon:
<ul>
<li>programming practise evolves as leaky coding patterns are recognised
<li>compilers get better at optimising leak away
<li>diagnostic and remedial tool support improves (for instance <a href="http://hackage.haskell.org/package/seqaid">seqaid</a>)
</ul>
There is also a wealth of blog posts online concerning space leak and related topics.
The examples you find may not leak with current compilers, but the principles of <em>demand</em>, <em>strictness</em> and <em>forcing</em> are still worth understanding: Space leak always arises in the development of real Haskell applications.
<h3>I heard Haskell will be strict-by-default in future...</h3>
Nah. ;) But if it were, you'd then have complementary problems, of overly strict code hurting performance.
Making the language implicitly strict is not a panacea (though a pragma to that effect would be welcome; also consider <a href="http://hackage.haskell.org/package/strict-ghc-plugin">strict-ghc-plugin</a> and <a href="http://hackage.haskell.org/package/seqaid">seqaid</a>).
<p>
<a id="r5"></a>
We will prevail against space leak, and all such things, without forfeiting lazy semantics;
through an improved understanding of demand, strictness, and evaluation.
The optimal solution will often be a complex fusion of lazy and strict.
As better tools emerge, these judgements will be automated, meaning less disruption to your development objectives.
You'll enjoy more sustained attention on your domain of <span>interest! <a href="#5">[5]</a></span>
<h3>Show me a simple example of a program that leaks</h3>
The <a href="http://hackage.haskell.org/package/leaky">leaky</a> package contains a small Haskell 98 program known to leak even with -O2 optimisation under GHC 7.8.3.
It also contains build flavours which test some new tools (<a href="http://hackage.haskell.org/package/deepseq-bounded">deepseq-bounded</a> and <a href="http://hackage.haskell.org/package/seqaid">seqaid</a>).
Installing <tt>seqaid</tt> and running <tt>seqaid demo</tt> is a good way to get started experimenting with <tt>leaky</tt>.
<!--Installing <a href="http://hackage.haskell.org/package/seqaid">seqaid</a> and running <tt>seqaid demo</tt> is a good way to get started experimenting with <a href="http://hackage.haskell.org/package/leaky">leaky</a>.-->
<!--
<p>
<div style="margin-top: -24px;"><a id="dig02s" class="dig-toggle-show" style="margin-left: 20px; border-top: 0px; margin-top: 6px; margin-bottom: 6px;" href='javascript:toggle("dig02");'>Show</a></div>
<div id="dig02" class="digression" style="margin-left: 20px; border-top: 0px; margin-top: 6px; margin-bottom: 12px;">
<a id="dig02h" class="dig-toggle-hide" href='javascript:toggle("dig02");'>Hide</a><p>
!--div style="font-size: 12pt; margin: 45px 20% 35px 20px;"--
The purpose of this wiki page is to help ensure that a space leak example which actually leaks is always available.
The maintainer of the <a href="http://hackage.haskell.org/package/leaky">leaky</a> package is committed to its good upkeep, so a working example leak should always be there, based on the most current information collected here.
<p>
If you have any comments, or information relating to the behaviour of this code under Haskell implementations other than GHC, please feel free to add to this page.
General discussion is on the <a href="">talk page</a> for this article.
Deletions from the page should first be discussed there.
</div>
-->
<p>
<a id="r6"></a>
<!--
The code that follows on this page is community edited, so may differ from the hackage repository.
-->
As new GHC releases come out, there may be some lag in case the upgraded compiler automatically optimises the leak out of <tt>leaky</tt>.
This is a natural progress, and reflects the importance of the space leak <span>problem. <a href="#6">[6]</a></span>
<p>
<div style="margin-top: 20px;">
<!--a href="code.html" style="margin-left: 30px;">leaky-min-cppd.hs</a-->
<pre style="width: 800px;">
-- This leaks with GHC 7.8.3 -O2, strict field notwithstanding.
duration = 5000000 -- XXX tune for your hardware
period = duration `div` 10
data State = St !Bool
toggle (St b) = St (not b)
main = do
putStrLn "Leaky started."
rslt <- duty (St False) 0
(return $! rslt) >>= return
putStrLn "Finished."
duty :: State -> Int -> IO State
duty state i = do
let state' = toggle state
if 0 == i `mod` period then return () else return ()
if i < duration then duty state' (1+i) else return state'
</pre>
</div>
<p>
And <a href="leaky-min.hs">leaky-min.hs</a> is the same program with some extras to tinker with.
<p>
<a id="dig01s" class="dig-toggle-show" href='javascript:toggle("dig01");'>Show</a>
<div id="dig01" class="digression">
<a id="dig01h" class="dig-toggle-hide" href='javascript:toggle("dig01");'>Hide</a><p>
<!--div style="margin-top: 20px;"-->
<!--a href="code.html" style="margin-left: 30px;">leaky-min.hs</a-->
<pre style="width: 800px;">
-------------------------------------------------------------------------------
-- So, with the following configuration, -O2 is smart enough
-- to produce the correct Bool output, without seeming to
-- do any work. (But not with -O0 or even with -O.)
--- #define STATS 0
--- #define NO_PERIODIC_BRANCH 1
--- #define STRICT_FIELDS 1
--
-- In fact, -O0, -O and -O2 all have distinct behaviour:
-- -O2 returns the result "instantly"
-- -O returns the result in a second or two
-- -O0 returns only after a long run
-------------------------------------------------------------------------------
{-# LANGUAGE CPP #-} -- (or run cpp manually if need be)
-------------------------------------------------------------------------------
-- Whether to run getStats computation (and output status lines).
-- Note that when STATS is 1, this constitutes a forcing factor:
-- Strictness is a bit like QM that way...
#define STATS 1
-- If you explicitly performGC at the start of each getStats, you
-- get a more regular sequence of status lines; but you are also
-- tampering with the natural behaviour of the garbage collector.
#define PERFORM_GC 1
-- This switch is offered because, only when set, is there a
-- difference between -O and -O2 evident. (-O0 differs in any case.)
-- And only when un-set will this program leak at -O2.
-- (Only applicable when STATS is 0.)
#define NO_PERIODIC_BRANCH 0
-- This leak is not plugged by strict fields!
-- (In the case of STATS 0 and NO_PERIODIC_BRANCH 1, the leak is
-- not manifest with -O2, but this is not due to the strict field.)
#define STRICT_FIELDS 1
-- Superfluous I guess.
#define RECORD_SYNTAX 0
-------------------------------------------------------------------------------
#if STATS
-- XXX This doesn't work!
-- Please GHC-compile with -rtsopts -with-rtsopts=-s -with-rtsopts=-T
-- (-s not -T are independent; nice to see -s summary info.)
{-# OPTIONS_GHC -rtsopts #-}
{- OPTIONS_GHC -with-rtsopts=-s #-}
{-# OPTIONS_GHC -with-rtsopts=-T #-}
#endif
-------------------------------------------------------------------------------
import Control.Exception ( evaluate ) -- (\x -> (return $! x) >>= return)
import GHC.Stats
import GHC.Int ( Int64 )
import System.Mem ( performGC )
-------------------------------------------------------------------------------
duration = 5000000 -- XXX tune for your hardware
report_period = duration `div` 10
--report_period = 500000 -- GHC 7.8.3 -O2 is two smart (when STATS=0)
-------------------------------------------------------------------------------
#if RECORD_SYNTAX
#if STRICT_FIELDS
data State = St { st :: !Bool }
#else
data State = St { st :: Bool }
#endif
#else
#if STRICT_FIELDS
data State = St !Bool
#else
data State = St Bool
#endif
#endif
toggle (St b) = St (not b)
-------------------------------------------------------------------------------
main = do
putStrLn "Leaky started."
#if STATS
putStrLn $ "\n" ++ pad "live heap" ++ " " ++ pad "just alloc'd"
#endif
rslt <- duty (St False) 0 0
evaluate rslt
putStrLn "\nFinished."
-------------------------------------------------------------------------------
duty :: State -> Int -> Int64 -> IO State
duty state i last_total_bytes_allocated = do
#if RECORD_SYNTAX
let state' = state { st = not (st state) }
#else
let state' = toggle state
-- let state' = (\(St b)->St (not b)) state
-- let state' = let St b = state in St (not b)
#endif
#if STATS
new_total_bytes_allocated
<- if 0 == i `mod` report_period
then do
#if PERFORM_GC
performGC
#endif
stats <- getGCStats
let bytes = bytesAllocated stats
putStrLn $ pad (show (currentBytesUsed stats)) ++ " "
++ pad (show (bytes - last_total_bytes_allocated))
return $ bytesAllocated stats
else return last_total_bytes_allocated
#else
let new_total_bytes_allocated = last_total_bytes_allocated
#if ! NO_PERIODIC_BRANCH
if 0 == i `mod` report_period
-- if 0 == i `mod` 2 -- GHC 7.8.3 -O2 is two smart
then do
-- putStrLn "." -- unnecessary
return ()
else return ()
#endif
#endif
if i < duration
then duty state' (1+i) new_total_bytes_allocated
else return state'
-------------------------------------------------------------------------------
pad :: String -> String
pad s = (take (15 - length s) $ repeat ' ') ++ s
-------------------------------------------------------------------------------
</pre>
</div>
<h3>Explanation of Output</h3>
If you actually build the <tt>leaky</tt> package with Cabal, the version built is further elaborated, and demonstrates <tt>seqaid</tt>.
The output is <a href="output.html">discussed here</a>.
<!--
<h3>Formal distinction between memory leak and space leak?</h3>
<p>
Space leak is not really well-differentiated from the better known <em>memory leak</em> phenomenon, common across all substantial programs such as web browsers.
Any attempt to pin down a difference seems flawed.
You might say, space leak begins where memory leak ends.
Both are a result of programmer error, but the errors differ in subtlety.
<p>
Memory leak harks back to the days when the programmer was explicitly in charge of allocating and freeing memory.
In particular, the programmer has instructed the runtime to consume space, and failed to reclaim it.
So far as the execution environment is concerned, the space is still needed;
but the programmer (and program) is oblivious to its existence.
Managed memory (garbage collection) has helped by removing <em>some</em> such possibilities for disparity between programmer belief and implementation reality.
<div style="display: none;">Memory leak involves the gradual consumption of memory (space) that would never be reclaimed so long as the offending program ran, since neither the programmer nor the implementation believe it to exist.<p></div>
<p>
Space leak is also due to programmer error, but the error is "anything less blatant than allocating memory and then failing to deallocate it".
Space leak is usually due to a failure of the programmer to give due consideration to the space behaviour of their code.
How much consideration is "due" will depend on how smart your compiler and execution environment are, and how good your language and libraries are.
<p>
Space leak is frequently characterised by non-locality - you can influence leak at a smattering of sites within the AST.
Some edits will plug a leak; others will exacerbate it, or introduce new leak; most edits will do nothing at all, quite often against our expectations.
This makes it difficult to talk about "a" (particular) space leak, although of course multinefarious leak aspects ("multiple leaks") can coexist independently in a program.
<p>
And although the causes are subtle, the effects can be catastrophic - steep linear growth (or even superlinear growth) of live memory is required to make progress.
<p>
In a way this is not the fault of the programmer, but of the language or API.
The programmer should not <em>have</em> to think too hard about whether a fold is strict or not.
All the programmer really wants is to receive timely output from the program as it's demanded.
The ideal language/implementation relieves as many concerns about the "how" as possible, letting the human focus on the "what".
<p>
<div class="digression" style="display: none;">
<div class="red">
I cannot seem to put my finger on the difference...
Having that much trouble to find /anything/ to say that might differentiate space and memory leak is telling...
Of what though? That there is no difference? Or that I'm too ignorant to imagine it?...
</div>
<p>
This is a worst-case scenario:
<p>
Subtle programmer error, or results
<p>
That most classic of space leak examples, <tt>foldl</tt> <em>vs.</em> <tt>foldl'</tt>, is proof enough that space leaks are not necessarily due to faults of the runtime system.
<p>
You get what you ask for, and the appropriate choice can depend on use case.
<p>
(But has anyone ever shown a viable example of where foldl would be preferred over foldl'?...)
<p>
Within a managed memory model (such as any Haskell implementation), the runtime (and the programmer, to any
<p>
<span class="red">Probably false</span> In contrast, space leaks when the runtime implementation (and the programmer, in principle) are accounting for the retained memory, only reclamation is taking longer than expected.
<p>
<span class="red">FALSE!</span> A space leak may grow without bound; a memory leak always grows without bound.
</div>
-->
<h3 style="margin-top: 50px; margin-bottom: 8px;">Notes</h3>
<!--div class="red">
I've changed my mind (todo): Don't use links for [1] etc. here. The user will use their back button if they want to jump back. (Personally, I frequently scroll back up...). Instead, offer a caret at the END of the note. <a href=""><tt><b>^</b></tt></a>
<p>
Unfortunately, it looks like ass - it's so small it's hard to see the blue colour.
</div-->
<table>
<tr id="1">
<td>
[1]
</td>
<td>
Given the non-locality of space leak phenomena in lazy languages, it is usually more appropriate to speak of "space leak" as an holistic, abstract quality of a program, rather than to speak of "a space leak" in particular.
When I speak of "a leak", this refers to a particular leaking program as a whole, or to a particular run of a leaking program.
Sometimes we leave out the word "space" and just speak of "leak", since space leak is the dominant form of resource leak plaguing <span>Haskell. <a href="#r1">⇪</a></span>
</td>
</tr>
<tr id="2">
<td>
[2]
</td>
<td>
Current state of the art, 2014.
One indicator of the pervasiveness of the space leak problem is the popularity of the <a href="http://packdeps.haskellers.com/reverse/deepseq">deepseq</a> package, despite its notoriety and ill repute.
(It has over 400 reverse dependencies on hackage, making it one of the most popular libraries of all time, coming in well ahead of <tt>lens</tt> <span>even!) <a href="#r2">⇪</a></span>
</tr>
</td>
<tr id="3">
<td>
[3]
</td>
<td>
One eventually enters the vast and nebulous realm of program optimisation, where the criterion "retains memory longer than expected" ramifies and <span>effervesces. <a href="#r3">⇪</a></span>
</td>
</tr>
<tr id="4">
<td>
[4]
</td>
<td>
At least, the GHC implementation of Haskell is <span>lazy. <a href="#r4">⇪</a></span>
</td>
</tr>
<tr id="5">
<td>
[5]
</td>
<td>
Otherwise, your domain of interest slides gradually, out of necessity or frustration, towards programming language theory and implementation.
Not a bad thing of itself, but it's not entirely satisfying to have your goals deflected, even if the shift was toward the noble pursuit of better <span>tools. <a href="#r5">⇪</a></span>
</td>
</tr>
<tr id="6">
<td>
[6]
</td>
<td>
For instance, Haskell's most famous space leak, <a href="http://blog.ezyang.com/2011/05/anatomy-of-a-thunk-leak">Anatomy of a Thunk Leak</a>, no longer leaks with GHC 7.8 and <span>-O2. <a href="#r6">⇪</a></span>
</td>
</tr>
</table>
<h3 id="Related">Related</h3>
Wiki Books - Haskell pages:
<ul>
<li><a href="http://en.wikibooks.org/wiki/Haskell/Laziness">
Laziness</a>
</ul>
haskellwiki pages:
<ul>
<li><a href="https://www.haskell.org/haskellwiki/Memory_leak">
Memory leak</a>
<li><a href="https://www.haskell.org/haskellwiki/Performance/Space">
Space</a>
<li><a href="https://www.haskell.org/haskellwiki/Performance/Laziness">
Laziness</a> (different than the above!)
<li><a href="https://www.haskell.org/haskellwiki/Performance/Strictness">
Strictness</a>
<li><a href="https://www.haskell.org/haskellwiki/How_to_profile_a_Haskell_program">
How to profile a Haskell program</a>
<li><a href="https://www.haskell.org/haskellwiki/Performance/Accumulating_parameter">
Accumulating parameter</a>
<li><a href="https://www.haskell.org/haskellwiki/Performance/Data_types">
Data types</a>
</ul>
<div class="footer">
Andrew Seniuk 2014
<br>
<tt>rasfar@gmail.com</tt>
</div>
</div>
<script language="javascript">
function toggle(id1){
var ele_s = document.getElementById(id1+"s");
var ele_h = document.getElementById(id1+"h");
var ele = document.getElementById(id1);
if( ele.style.display == "inline-block" ){
ele.style.display = "none";
ele_s.style.display = "inline-block";
ele_h.style.display = "none";
}else{
ele.style.display = "inline-block";
ele_s.style.display = "none";
ele_h.style.display = "block";
}
}
</script>
</body>
</html>