[GHC] #9706: New block-structured heap organization for 64-bit

[GHC]

#9706: New block-structured heap organization for 64-bit
-------------------------------------+-------------------------------------
       Reporter:  ezyang             |                   Owner:  simonmar
           Type:  task               |                  Status:  new
       Priority:  normal             |               Milestone:
      Component:  Runtime System     |                 Version:  7.8.3
       Keywords:                     |        Operating System:
   Architecture:  Unknown/Multiple   |  Unknown/Multiple
     Difficulty:  Unknown            |         Type of failure:
     Blocked By:                     |  None/Unknown
Related Tickets:                     |               Test Case:
                                     |                Blocking:
                                     |  Differential Revisions:
-------------------------------------+-------------------------------------
 I was having some discussion about GHC's block structured heap with Sergio
 Benitez and Adam Belay, and during the discussion it was suggested that
 the way GHC manages the block structured heap is suboptimal when we're on
 64-bit architectures.

 At the moment, we allocate memory from the operating system per-megablock,
 storing metadata in the very first megablock. We have to do this because,
 on 32-bit, we can't generally be too picky about what address our memory
 ends up living. On 64-bits, we have a lot more flexibility.

 Here is the proposal:

 1. Statically decide on a maximum heap size in a power of two.
 2. Next, probe for some appropriately aligned chunk of available virtual
 address space for this. On POSIX, we can mmap /dev/null using PROT_NONE
 and MAP_NORESERVE. On Windows, we can use VirtualAlloc with MEM_RESERVE.
 (There are few other runtimes which do this trick, including GCC Go.)
 3. Divide this region into blocks as before. The maximum heap size is now
 the megablock size, and the block size is still the same as before.
 Masking to find the block descriptor works as before.
 4. To allocate, we keep track of the high-watermark, and mmap in 1MB pages
 as they are requested. We also keep track of how much metadata we need,
 and mmap extra pages to store metadata as necessary.

 We still want to request memory from the operating system in conveniently
 sized chunks, but we can now abolish the notion of a megablock and the
 megablock allocator, and work purely with block coalescing. Additionally,
 the recorded heap location means that we can check if a pointer is
 HEAP_ALLOCED using a mask and equality check, solving #8199.

 What do people think?

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9706>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler