CODEWITHSUNDEEP
haskellgarbage-collectionghc
sevo
sevo

Reputation: 4609

Does GHC support GC-less programming?

With -S option and a simple program:

main = do
   print "Hello"
   main

I can see that it produces some garbage:

[...]
  1024232      4904     45992  0.000  0.000    0.428    0.530    0    0  (Gen:  1)
        0                      0.000  0.000

   1,242,080,056 bytes allocated in the heap
         271,656 bytes copied during GC
[...]

But after removing print it apparently doesn't. Is there a alloc-free subset of core libraries that could be used to write GC-less programs?

EDIT: There is also recent work regarding linear-types which seems to have potential to enable such feature.

Upvotes: 2

Views: 361

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 50819

You can very occasionally produce small programs that perform little-to-no garbage collection. For example, the following program:

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

if compiled with -O2 should run without allocating much or performing any GC worth mentioning.

However, this is generally restricted to programs that can be compiled into tight loops with "unboxed" data types (in this case, unboxed Int# values) without algebraic data structures (in this case, the list is fused out of existence). There is a limited set of more complex data structures (e.g., unboxed Vectors) that can also be manipulated without allocation, and if you are very careful, you might be able to write algorithms that operate on such structures without allocating much.

For example, the following program:

import Control.Monad
import qualified Data.Vector.Unboxed.Mutable as V

main :: IO ()
main = do
  v <- V.new 1000000
  forM_ [0..999999] $ \i -> do
    V.write v i i
  replicateM_ 999 $
    forM_ [0..499999] $ \i -> do
      V.swap v i (999999 - i)
  print =<< V.read v 123

allocates a million-integer array and then runs through it 999 times reversing all the elements.

Compiled with GHC version 8.4.3 and -O2 it allocates about 8 gigs at the beginning but doesn't do any additional allocation while running the list reversals. My guess is that you could implement something useful, like an in-place quicksort, using similar techniques without doing any allocations and so skipping any GC.

As a general rule, though, allocation is such a fundamental part of the way Haskell code compiled by GHC actually runs, that there's no reasonable subset of libraries or programming techniques that can guarantee GC-free programming.

Upvotes: 7

Related Questions