Fixing a space leak in a Haskell program: an experience report.

Wow! It is exciting to find and fix a space leak in my Haskell program, YAPB

 - https://github.com/kwanghoon/yapb : Commit #57c03df

1. Background

As a background, YAPB is a programmable parser building system based on LALR(1). I have been working on this for a few years. You can directly write parser specifications  in Haskell, not in Happy, Yacc, MLYacc, and so on. 

Using this tool, I have developed several parsers: PolyRPC, Small Basic, and C11. 

 - PolyRPC: an experimental (multi-tier) functional programming language (94 production rules)

 - Small Basic: Microsoft Small Basic (60 production rules)

 - C11: C11 standard (334 production rules)

For the three parser specifications, YAPB has successfully produced LALR(1) automations. 

(Note: I have also experiment this tool with Haskell (815 production rules) but in this case, I did not write a parser specification but I used the automation generated by Happy.)

2. A Space Leak Problem and a Solution

For PolyRPC and Small Basic parser specifications, YAPB shows no problem at all in terms of memory usages, though it does not mean that the implementation of LALR(1) algorithms in YAPB is done in an optimized way. :)

However, for the C11 paser specification, YAPB was abnormally terminated in the middle of LALR(1) automation production. Precisely speaking, there was a space leak in the implementation of constructing LALR(1) items from LR(0) items with spontaneous lookaheads and lookahead propagation. 

 - For a technical account for the construction algorithm, you may refer to the Dragon book (Section 4.7.5 Efficient Construction of LALR Parsing Tables, 2nd Edition)

Simply speaking, LALR(1) items have lookaheads while LR(0) items do not have ones. While LALR(1) items could be constructed from LR(1) items, the construction of LR(1) items demand much more space. A noble idea is to construct LALR(1) items from LR(0) items, which are much smaller than LR(1) items. 

Roughly, LR(0) items become LALR(1) items when proper lookaheads are added to them. Here the ideas of spontaneous lookaheads and lookahead propagation are used. 

The reason for the space leak was a bit surprising. After my implementation constructs an initial LALR(1) items with spontaneous lookaheads, it has to add more lookaheads using the lookahead propagation. In the previous implementation,

let   newLookaheads = if some condition is satisfied

                                      then propagatedLookaheds else []

in    existingLookaheads ++ newLookaheads

This code has a space leak because even when no propagated lookaheads are added, it has to have (... ++ ...) lazily! Moreover, the propagated lookaheads may be already contained in the existing lookaheads. Then the space leak will be more larger. (The duplicated lookaheads are eliminated in a later stage.)

So, I have changed this code into a new one as:

if some condition is satisfied

then accumLks propagatedLookaheds existingLookaheads else existingLookaheads

accumLks [] lookaheads = lookaheads

accumLks (lk:lks) lookaheads

  | lk `elem` lookaheads = accumLks lks lookaheads

  | otherwise = accumLks lks (lk : lookaheads)

After the change, there is no more (++) operations being accumulated, and there is no more duplicate addition of lookaheads.  

In an LALR(1) automation construction with the C11 parser specification, the new version takes only about 2GB memory while the previous leaked version took more than 16GB, which is the size of the memory in my Laptop.

3. How I was able to find the space leak problem

I've found this space leak by running a C11 parser using YAPB in parallel with viewing memory and swam usages ( available in Ubuntu)

With the C11 parser, I had added  a series of 'putStrLn's to print intermediate results from the beginning. For example, it was fine until it prints LR(0) items. There was no noticeable rise in the memory usage. After that, computing and printing spontaneous lookaheads from the LR(0) items were fine. Also, computing and printing a lookahead propagation relation was good. I still did not see any memory usage problem. 

The next step was to compute LALR(1) kernel items from LR(0) items with the spontaneous lookaheads and the lookahead propagation relation. I added a putStrLn to print the result, LALR(1) kernel items. After running this, there was a series of rising patterns in the memory usage from 2GB (the initial memory occupancy) to 16GB (the size of the laptop RAM memory) and the program was killed abnormally by the operating system. This was why I realized that there is a space leak in the stage of computing LALR(1) kernel items!

After that, I reviewed the relevant Haskell program line by line, and, very luckily, found out the space leak explained above. 

4. In retrospect

Actually, I have tried to apply the GHC profiling utility in the beginning, but it was in vain. The reason is that the abnormal terminal doesn't seem to produce a profiling result file properly. There could be my mistake in using the GHC profiling tool because I am not so familiar with it. If you have any suggestion, please leave your message. 

Anyway, I hope this article may give you a hint on how to find and fix a space leak in your Haskell programs!