Opened 3 years ago

Closed 3 years ago

Last modified 3 weeks ago

#8703 closed feature request (wontfix)

Use guard pages rather than heap checks

Reported by: schyler Owned by: simonmar
Priority: normal Milestone:
Component: Runtime System Version:
Keywords: Cc: simonmar
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

By mmap'ing memory using MAP_ANONYMOUS (or /dev/zero) as PROT_NONE (Windows has an equivalent functionality with VirtualAlloc), it's possible to create a page that will fault when read or written to. It may be possible to remove the heap checks in the runtime, speeding up allocations, and instead expand the heap when a fault is raised.

This is likely cheaper for large pages full of many small allocations than the cost of the heap checking branch.

Change History (8)

comment:1 Changed 3 years ago by simonmar

Resolution: wontfix
Status: newclosed

This is a lot harder to do than you might imagine - the problem is not the memory protection itself, but how to handle the fault when the invalid page is accessed. This requires all kinds of platform-specific hackery.

GHC's heap is constructed of linked lists of pages, so at the end of each page we have to swing the heap pointer to the next page in the list, which is often not contiguous with the previous page. Using the page fault trick is even harder when the memory must grow through non-contiguous pages, because the fault handler has to also update the current heap pointer.

I'm not saying it can't be done, but it is (a) very tricky, (b) non-portable, and (c) after you've surmounted all the obstacles, it probably doesn't save that much time, if any. And because it's non-portable, you still have to keep the old way of doing things.

I'm closing the ticket. But if you want to implement this and demonstrate that it is indeed a win, be my guest!

comment:2 Changed 6 weeks ago by varosi

hm, it's not a hackery, but platform specific. Is it needed all pages to be linked in a linked list? I mean that it is possible to realloc() current page until it is possible to resize it. That way we'll have less jumps and guard pages. So we'll have linked list, but from larger memory chunks.

comment:3 Changed 6 weeks ago by simonmar

Go ahead and try it!

comment:4 Changed 5 weeks ago by varosi

I'm not that into GHC runtime and implications, but we could make some discussions on this topic and put it as opened issue for future work?

Here is some talk: https://www.reddit.com/r/haskell/comments/6bpf3p/guard_pages_instead_of_heapstack_limit_checks_in/

Sorry about the question, but why GHC's heap is linked list? Why not use linear virtual memory? Thread's stack could be linear, too. This will make much more easier and faster to access it.

comment:5 Changed 5 weeks ago by simonmar

For rationale on why GHC's heap is divided into blocks, see this paper: http://simonmar.github.io/bib/papers/parallel-gc.pdf

Changing the structure of the heap is a MASSIVE change. If you really think it's worthwhile, I suggest building a proof-of-concept prototype and obtain some measurements.

comment:6 Changed 5 weeks ago by simonpj

FWIW I believe that in other systems (e.g. ML) they started using guard pages, and moved away from it becuase it was SO HARD to make it work: on different archiectures and OSs, accommodating the non-standard calling conventions we use; dealing with correct GC of the registers that are saved on the trap; dealing with the fact that the stack we have is tiny, unlike the OS stack.

If I had 1,000 hours to invest, I would invest it elsewhere. I'm not saying you couldn't make progress here, just that I think you'll find a better cost/benefit ratio elsewhere.

comment:7 Changed 4 weeks ago by varosi

Fantastic paper! Thanks for the thorough answers!

Did that plan from the paper happened already in the latest GHC: 7.2 Privatising minor collections

This looks like a very good fit for per-core caches.

comment:8 Changed 3 weeks ago by simonmar

For local minor collections, see http://simonmar.github.io/bib/papers/local-gc.pdf

We didn't merge this work into the released GHC branch because the implementation was incredibly complicated and the gains were relatively small and inconsistent.

Note: See TracTickets for help on using tickets.