ezyang's blog

the arc of software bends towards understanding

Visualizing a block allocator

October 30, 2013

GHC’s block allocator is a pretty nifty piece of low-level infrastructure. It offers a much more flexible way of managing a heap, rather than trying to jam it all in one contiguous block of memory, and is probably something that should be of general interest to anyone who is implementing low-level code like a runtime. The core idea behind it is quite old (BIBOP: Big Bag of Pages), and is useful for any situation where you have a number of objects that are tagged with the same descriptor, and you don’t want to pay the cost of the tag on each object.

Managing objects larger than pages is a bit tricky, however, and so I wrote a document visualizing the situation to help explain it to myself. I figured it might be of general interest, so you can get it here: http://web.mit.edu/~ezyang/Public/blocks.pdf

Some day I’ll convert it into wikiable form, but I don’t feel like Gimp’ing the images today…

6 Comments

  1. Steve M
    The text in the pdf is garbled on my iOS 7 platform.
  2. Angel Alvarez

    It also seems to have trouble displaying in Mac OS…

    Even that, thats a good article, thanks so much

  3. Edward Z. Yang
    Dammit, I even tried to pick a universal font. I’ll try to fix it.
  4. Edward Z. Yang
    OK, apparently this bug doesn’t show up if I use a Type 1 font. So reuploaded, with a different font.
  5. Anonymous
    One question: is there a significance to the 2D shape of the diagrams? I.e., is the problem to allocate 2D squares of memory, or are we ultimately allocating contiguous sections? Thanks.
  6. Edward Z. Yang
    No, the memory is contiguous. I decided to use squares, because it makes it easier to show the fractal nature of the block descriptor table and the blocks themselves.