Python algorithm mimicking mark/sweep garbage collection 2.0

Question

Here I have incorporated the excellent feedback from this question to improve a small program that simulates a Mark/Sweep G.C. Algorithm.

The code overall is much cleaner and the functionality is improved. Specifically I moved inline comments to a larger Documentation Block at the top of each function (though I'm not sure if those became too verbose), cleaned up my formatting, and restructured the storage of the Memory-blocks and pointer-variables to allow for a more efficient algorithm.

Here is the revised program, if it looks significantly longer, that's just the added documentation:

import argparse
import re
import sys

class MemoryObject():
    def __init__(self):
        self.marked = 0
        self.references = []  # list of <MemoryObject> references

def arg_parse():
    # Sets up a parser object for handling arguments passed to the program
    parser = argparse.ArgumentParser(description='Some description')
    parser.add_argument('filename', help='Filename parameter for input file')
    return parser.parse_args()


def is_int(s):
    # Determines if the given string contains only an integer value
    # Primarily used to distinguish memory-blocks from named 
    # pointer variables
    try:
        return int(s)
    except ValueError:
        return False


def node_trace(current_node, node_dict):
    # This function recursively simulates the "mark" phase of
    # Mark/Sweep G.C. using a dictionary of <MemoryObject>
    # each element therin containing its list of references
    #
    # Each node traversed is marked, and the function returns
    # if the node has already been checked
    #
    # This function assumed the inital call was passed the RootMemoryBlock
    # as it's starting point, which garuntees only accessible memory will
    # be marked since RootMemoryBlock only references pointers which 
    # in turn, by definition, only reference chains of accessible memory

    if current_node.marked == 1:
        return
    else:
        current_node.marked = 1

        for node in current_node.references:
            node_trace(node, node_dict)


def get_nodes():
    # This function creates a dictionary of memory-blocks and named 
    # pointer-variables ncluding a "RootMemoryBlock" that hold the  
    # pointer-variables. The number of memory blocks/variables is
    # determined by the contents of the input file.
    # 
    # Each object is stored in the dictionary as a <MemoryObject>
    #
    # The contents of the input file are then used to determine all references
    # between variables->blocks and blocks->blocks, with the only object 
    # referencing named-variables being the RootMemoryBlock. The format
    # of the file garuntees that memory_blocks are listed as integers, and
    # variables as strings that start with either a letter or an underscore '_'
    # 
    # is_int is therefor used to determing if an object is a variable or a
    # memory-block when populating the reference lists for the elements
    # of the <MemoryObject> dictionary
    #
    # Each object's reference list is stored in its <MemoryObject>::references
    # as a list of references to <MemoryObject>
    #
    # The dictionary is then passed into the node_trace function along with the 
    # RootMemoryBlock <MemoryObject> which recursively performs the 
    # "mark" phase of Mark/Sweep G.C.
    #
    # Finally a new dictionary is created and JUST the info for the 
    # memory-blocks (not variables, or the RootBlock) is copied into it.
    #
    # That dictionary is then returned to the calling function.
    node_pointers = []
    node_dict = {}
    args = arg_parse()
    input_file = args.filename

    with open(input_file) as in_file:
        node_count = 0
        for line in in_file:
            if node_count == 0:
                node_count = int(line)
            else:
                split_line = line.rstrip()
                split_line = re.split(r'[,]', split_line)
                node_pointers.append([split_line[0], int(split_line[1])])

    root_node_key = node_count
    array_size = node_count + 1
    for i in range (array_size):
        node_dict[i] = MemoryObject()

    # The format of the input file garuntees that each item will
    # describe a link of the form [source, target]
    SOURCE = 0  # The source of a reference link 
    TARGET = 1   # The target of a reference link

    for item in node_pointers:
        if is_int(item[SOURCE]):
            node_dict[int(item[SOURCE])].references.append(node_dict[item[TARGET]])
        else:
            if item[SOURCE] not in node_dict.keys():
                node_dict[item[SOURCE]] = MemoryObject()

            node_dict[item[SOURCE]].references.append(node_dict[item[TARGET]])
            node_dict[root_node_key].references.append(node_dict[item[SOURCE]])

    node_trace(node_dict[root_node_key], node_dict)

    node_dict_final = {}

    for element in node_dict.keys():
        if is_int(element) and element != root_node_key:
            node_dict_final[element] = node_dict[element]

    return node_dict_final


def print_result(message, value, nodes):
    # Displays the results of the mark/sweep algorithm
    # as stored in the dictionary "nodes"
    #
    # Prints all marked nodes if value == 1
    # Prints all reclaimed nodes if value == 0
    print(message)
    for element in nodes.items():
        if element[1].marked == value:
            if is_int(element[0]):
                print(element[0])


def main():
    # Entry Point function. Calls get_nodes which processes
    # the input_file, then runs the simluated mark/sweep
    # algorithm.
    #
    # It then displays the returned results of the mark/sweep

    nodes = get_nodes()
    print_result('\nMarked: ', 1, nodes)
    print_result('\nReclaimed: ', 0, nodes)
    print()


if __name__ == '__main__':
    main()

My remaining questions are:

Is my solution for store the RootMemoryBlock, the normal memory blocks, the named pointer-variables, and all their reference links still needlessly inelegant, unintuitive, or "hackey"? This is especially in regards to the code that populates the reference lists for the elements in the dictionary, though I tried pretty hard to make it as readable as possible without any inline comments.

The continued use of is_int() to differentiate between a pointer and a memory-block is due to the fact that there are no established naming conventions for the pointers, and they could be anything from ptr to _dif94tdifj_fgjd. I don't think I made this very clear in the original post.

AND

Did I achieve the goal of O(N) complexity? Ideally this is something I should be able to determine on my own, but I don't trust myself 100% on this.

Answer 1

In this answer I'm going to discuss the general design of the garbage collection algorithm. Of course what you have here is just an exercise, not a real collector, so this is kind of academic, but I think the points here are worth knowing about.

1. The algorithm in the post stores the mark bit inside the object being collected. In real garbage collection settings this approach has a couple of problems. First, the objects you are collecting may not be under your control and so there might not be anywhere convenient inside the objects to put the mark bit. Second, setting the mark bit has to update the memory containing the objects being collected, which can be bad for cache performance on multi-core systems (because the page containing the objects gets marked dirty and flushed from the cache on other cores, even though the objects themselves did not change, just their mark bits).

   For these reasons it can be worth storing a table of mark bits externally to the objects being collected.

2. The node_trace function calls itself recursively as it traces the graph of references. But that can lead to arbitrary amounts of recursion, which could overflow Python's stack. (See sys.getrecursionlimit.)

   Also, by following references in a depth-first order, the marking algorithm is unlikely to benefit from locality of reference. Ideally we want to mark nearby objects (which are likely to be in the processor cache) before marking distant objects.

Here's an illustration of the alternative approach, which maintains an extenal table of marked objects, and operated in breadth-first rather than depth-first order:

def mark(root):
    """Mark all objects reachable from root. Return set of marked objects."""
    queue = deque([root])    # Queue of objects marked but not expanded.
    marked = set(queue)      # Set of marked objects.
    while queue:
        obj = queue.popleft()
        for ref in references(obj):
            if ref not in marked:
                queue.append(ref)
                marked.add(ref)
    return marked