Personal tools

Yhc/RTS/PointerReversal

From HaskellWiki

< Yhc | RTS
Revision as of 18:56, 12 May 2006 by TomShackell (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Part of Yhc

(Download)

Marking the heap is a recursive process but a naive recursive implementation of this can quickly exhaust the C stack. So a common trick here is 'pointer reversal' whereby the heap itself is used as a stack.

The following diagram explains how it works. We mark the root node by taking this heap layout:

        +-- Current Node
        |
  root  V                 node A
+--------+              +---------+---------+---------+
|       --------------->|   XXX   |         |         |
+--------+              +---------+----|----+----|----+
                                       |         | 
                     +-----------------+         |
                     V                           V
                +---------+---------+         +----------+
        node B  |   YYY   |         --------->|    ZZZ   |
                +---------+---------+         +----------+
                                                 node C

and changing it to (the hashes indicate the word is marked).

            Current Node-+
                         |
  root                   V node A
+--------+              ###########---------+---------+
|  XXX   |<---------------        #         |         |
+--------+              ###########----|----+----|----+
                                       |         | 
                     +-----------------+         |
                     V                           V
                +---------+---------+         +----------+
        node B  |   YYY   |         --------->|   ZZZ    |
                +---------+---------+         +----------+
                                                 node C

We then mark all the arguments of node a, starting from the right most one:

  root                    node A
+--------+              ###########---------+---------+
|  XXX   |<---------------        #         |   ZZZ   |
+--------+              ###########----|----+---------+
                                       |         ^         Current Node
                     +-----------------+         |             |
                     V                           |             |
                +---------+---------+         ###|########     |
        node B  |   YYY   |         --------->#          #<----+
                +---------+---------+         ############
                                                 node C

There are no more arguments to mark so we 'return'

                             Current Node ------+
                                                |
  root                     node A               V
+--------+              ###########---------+---------+
|  XXX   |<---------------        #         |         |
+--------+              ###########----|----+----|----+
                                       |         | 
                     +-----------------+         |
                     V                           V
                +---------+---------+         ############
        node B  |   YYY   |         --------->#   ZZZ    #
                +---------+---------+         ############
                                                 node C

We now decrement current node to the first argument of node A and mark that node.

  root                     node A              
+--------+              ###########---------+---------+
|  XXX   |<---------------        #   YYY   |         |
+--------+              ###########---------+----|----+
                                       ^         | 
                     +-----------------+         |
                     |                           V
                #####|#####---------+         ############
        node B  #         #         --------->#   ZZZ    #
                ###########---------+         ############
                     ^                           node C
  Current Node ------+


And descend into the first argument of node B.

  root                    node A
+--------+              ###########---------+---------+
|  XXX   |<---------------        #   YYY   |         |
+--------+              ###########---------+----|----+
                                       |         |         Current Node
                     +-----------------+         |             |
                     |                           V             |
                #####|#####---------+         ############     |
        node B  #         #   ZZZ   |<---------          #<----+
                ###########---------+         ############
                                                 node C

This node is already marked, so we return.

  root                    node A
+--------+              ###########---------+---------+
|  XXX   |<---------------        #   YYY   |         |
+--------+              ###########---------+----|----+
                                       |         |        
                     +-----------------+         |        
                     |                           V        
                #####|#####---------+         ############
        node B  #         #        ---------->#   ZZZ    #
                ###########---------+         ############
                              ^                  node C
            Current Node------+

We can now decrement current node, however this takes us to the head of node B (we can tell it's the head of a node because it's marked). There are no more arguments in node B, so we return.

                                     +--- Current Node
  root                    node A     V
+--------+              ###########---------+---------+
|  XXX   |<---------------        #         |         |
+--------+              ###########----|----+----|----+
                                       |         |        
                     +-----------------+         |        
                     V                           V        
                ###########---------+         ############
        node B  #   YYY   #        ---------->#   ZZZ    #
                ###########---------+         ############
                                                node C

We now decrement current node, again we're at the head of node A. No more arguments left so we return.

        +--- Current Node
        |                            
  root  V                 node A     
+--------+              ###########---------+---------+
|       --------------->#   XXX   #         |         |
+--------+              ###########----|----+----|----+
                                       |         |        
                     +-----------------+         |        
                     V                           V        
                ###########---------+         ############
        node B  #   YYY   #        ---------->#   ZZZ    #
                ###########---------+         ############
                                                node C

We're back at our starting point so we can stop.