Python algorithm mimicking mark/sweep garbage collection

Question

I don't have much experience with Python and would love some feedback on my implementation of this program.

I am given a file with an integer representing a number of memory-cells, followed by a list of ordered pairs representing links between either a pointer and a memory-cell, or memory-cell and a memory-cell. You could use the list to draw diagram akin to those used in text-book "which cells are marked and which are reclaimed" problems regarding mark/sweep GC.

I was tasked with creating a Python script that takes in such a list, and runs a simulated mark/sweep on it and my solution (below) is fully functional.

Here's an example input file:

6
ptr1,0
0,1
1,2
ptr2,3
3,2
4,5

And here is the script:

import sys
import re

def RepresentsInt(s):
    try: 
        int(s)
        return True
    except ValueError:
        return False

#recursive function that traces through a mem-node structure
#setting each node's check_flag to 1 if traversed
def node_trace(pointer, node_pointer_list, nodes_dict):
    if RepresentsInt(pointer[0]):
        if nodes_dict[pointer[0]][1] == 1:
            #returns if the current node has been traversed already
            return
        else:
            #checks the current node as marked and traversed
            nodes_dict[pointer[0]][0] = 1
            nodes_dict[pointer[0]][1] = 1

    for x in node_pointer_list:
    #recurs for each node the current node points to
        if x[0] == pointer[1] and nodes_dict[x[0]][1] == 0:
            node_trace(x, node_pointer_list, nodes_dict)

        #catches the node at the end of a chain
        if RepresentsInt(x[0]):
            if nodes_dict[x[0]][1] == 1:
                nodes_dict[x[1]][0] = 1
                nodes_dict[x[1]][1] = 1
        else:
        #catches a single-link chain from a variable to a mem-block
            nodes_dict[x[1]][0] = 1
            nodes_dict[x[1]][1] = 1


sysArgs = list(sys.argv)
inputFile = sysArgs[1]
inFile = open(inputFile)
node_pointer_list = []
nodes_dict_0 = {}      #contains node records of the format, ['mem-cell': traversed_flag, marked_flag]
                       #traversed/marked _flag is 0 if unchecked, 1 if checked

#read, parse, and store the contents of the input file
node_count = 0
for line in inFile:
    #grabs the number of nodes which is stored in the first line of the file
    if node_count == 0:
        node_count = int(line)
    else:
        #read and parse a line as required
        splitLine = line.rstrip()
        splitLine = re.split(r'[,]', splitLine)

        node_pointer_list.append([splitLine[0], splitLine[1]])



#create a dictionary for all nodes, with flags for "checked" and "traversed"
#initialized to 0
count = 0
while count < node_count:
    nodes_dict_0[str(count)] = [0, 0]
    count += 1

#simulates the mark phase of a mark-sweep algorithm using the
#reference structure described in the input file
for item in node_pointer_list:
    if not RepresentsInt(item[0]):
        #if the link begins with a variable pointer
        #follow the trace marking all nodes along the way
        node_trace(item, node_pointer_list, nodes_dict_0)

print("\nMarked: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 1:
        print(item[0])

print("\nReclaimed: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 0:
        print(item[0])

Running the above script with the example input file produces the following output:

Marked:
0
1
2
3

Reclaimed:
4
5

which is correct.

My question simply this: Is the way I implemented this a reasonable solution or are there egregious inefficiencies, needlessly roundabout approaches etc that wouldn't be obvious to an novice that I could improve-on beyond just providing the required functionality?

More specifically: is a recursive algorithm the best approach in python? Is using a dictionary to track the marked status of nodes the most efficient way to do so? Is the way I structured the algorithm as efficient as it could be in terms of big-O?

Answer 1

There are several suboptimal areas of this solution that are interrelated. Please feel free to ask questions if anything I've written here is unclear.

The solution is not "modeling" memory and then performing mark-and-sweep as it probably should be. Instead it is preserving the data-input file in node_pointer_list and repeatedly walking it to find what is needed, because of your for x in node_pointer_list: in node_trace(). This is causing the solution to unnecessarily iterate over the node_pointer_list inside each call to node_trace(), which is making its running time O(N^2) when it should be O(N). It is also making the code 2-3x longer than it should be. Further, the solution is quite hard to read.

I'll try to break down those issues one at a time, though keep in mind they are all interrelated. I'm intentionally explaining rather than providing code, so you can do the learning work to make a better solution. I'll start by talking about code readability.

The way you use if not RepresentsInt(item[0]): to determine if a line is a "pointer" line is very non-intuitive. It would be easier to read if the literal "ptr" appeared somewhere near where you are testing if it is a line containing "ptr", such as:

if item[0].find("ptr") == 0:

Why do you have both "marked" and "traversed" flags? They contain the same information.

A code line like this below, is very hard for anyone to read the meaning of. Someone reading the code is forced to dig around to find out the meaning of the zeroes and ones to understand it.

nodes_dict[x[1]][0] = 1

To make it more readable, you need to get the word "TRAVERSED" in there somewhere, since what you are doing is setting a traversed flag. If you stick with your two element arrays, you can make a TRAVERSED_FLAG symbol to make it more readable, as in:

nodes_dict[x[1]][TRAVERSED_FLAG] = 1

Better style would be to define a class, and give the class a .traversed field. If you also make some of the other changes I highlight below, this access becomes:

current_object.traversed = 1

I don't know if you are comfortable with classes or not, so I'll provide one explanation based on classes, and one based on arrays...

With Classes

You can put the marked field, and the list of an object's references in a single class that represents a memory position in your heap. The class definition would look something like:

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

First you would instantiate an array of these for the number of memory-spaces according to your data-file, with an additional one as the RootMemoryObject. Then you would walk the file's references, adding to each MemoryObject's references list. You can either store an int reference in the list, and look it up later, or you can look up the MemoryObject now and store that directly in references. When you see a "ptr" entry, you put that in the RootMemoryObject.

The first step of mark-and-sweep is to walk all memory locations and set .marked=0. Then you would call node_trace(RootMemoryObject), which would mark the object visited, and recurse through the objects referenced by that object's .references. Because you have the list of that object's references, you don't need the inefficient loop for x in node_pointer_list:.

Without Classes

Instead of node_pointer_list, you want an array of lists of references. As you walk the datafile, you would insert each reference into the appropriate list for that pointer number. Further, you want an additional "root_references" list to hold references which appear in "ptr" entries.

To start the recursion, you would do for reference in root_references: node_trace(reference), which would mark the reference visited (returning if it was already visited), then look up each child reference and recursively call node_trace(child_reference) on it. Because you have the list of that object's references, you don't need the inefficient loop for x in node_pointer_list:.

Other Factors

The running time you are shooting for is O(N), where N is the number of nodes in your memory. You are currently O(N^2). After you remove the extra loop in node_trace(), you will be properly O(N) because you already have a check to be sure you're not traversing a set of children more than one.

Using recursion is good. An alternative is to use a work-list. To use a work list, you put the root(s) in a list, and then while the work-list is non-empty, you remove an item from the work-list and call node_trace() on it. node_trace puts any child nodes that need to be visited into the work list, and exits.

Both will have the same O(N) running time, but can potentially have different memory consumption. The recursive version's maximum memory consumption is proportional to the depth of object references. The work-list version's maximum memory consumption is hard to calculate, as it can be wildly different based on how you prioritize the work list and what your in-memory objects look like.

If you have 1000 objects in a linked list, each pointing to the next, the work-list will only require 1 entry, whereas the recursive version will require a 1000 depth stack. However, if instead you have 1 object with 999 pointers to leaf objects, then the recursive version will only require a maximum of 1 stack frame, while the work list will have a maximum of 999 entries. So you can see neither is better universally, there are just tradeoffs.

Answer 2

Because @David answered the performance part, I'll try to comment on the other aspects.

There are some things you could improve. I'll start as always with some PEP8 rules / best-practices:

• functions / variables names should be snake_cased
• there's usually a space between # and the string in the comments
• instead of using comments here and there, try to write docstrings which summarizes what the function does

That being said your code as you've written it, might look like this:

import sys
import re


def represents_int(s):
    try:
        int(s)
        return True
    except ValueError:
        return False


def node_trace(pointer, node_pointer_list, nodes_dict):
    if represents_int(pointer[0]):
        if nodes_dict[pointer[0]][1] == 1:
            return
        else:
            nodes_dict[pointer[0]][0] = 1
            nodes_dict[pointer[0]][1] = 1

    for x in node_pointer_list:
        if x[0] == pointer[1] and nodes_dict[x[0]][1] == 0:
            node_trace(x, node_pointer_list, nodes_dict)

        if represents_int(x[0]):
            if nodes_dict[x[0]][1] == 1:
                nodes_dict[x[1]][0] = 1
                nodes_dict[x[1]][1] = 1
        else:
            nodes_dict[x[1]][0] = 1
            nodes_dict[x[1]][1] = 1


sys_args = list(sys.argv)
input_file = sys_args[1]
in_file = open(input_file)
node_pointer_list = []
nodes_dict_0 = {}

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_pointer_list.append([split_line[0], split_line[1]])

count = 0
while count < node_count:
    nodes_dict_0[str(count)] = [0, 0]
    count += 1


for item in node_pointer_list:
    if not represents_int(item[0]):
        node_trace(item, node_pointer_list, nodes_dict_0)

print("\nMarked: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 1:
        print(item[0])

print("\nReclaimed: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 0:
        print(item[0])

---

More on the code

def RepresentsInt(s):
    try:
        int(s)
        return True
    except ValueError:
        return False

Can be rewritten as:

def is_int(s):
    try:
        return int(s)
    except ValueError:
        return False

Instead of manually handling the arguments of your program, use argparse module which does it for you. A really basic / simple example would be:

import argparse


def arg_parse():
    parser = argparse.ArgumentParser(description='Some description')
    parser.add_argument('filename', help='Filename parameter for input file')
    return parser.parse_args()

Then you can use it like this:

args = arg_parse()
# print(args.filename)

Don't use:

in_file = open(input_file)

But rather:

with open(input_file) as in_file:
    # do the rest here

You're not following DRY principles here:

print("\nMarked: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 1:
        print(item[0])

print("\nReclaimed: ")
for item in sorted(nodes_dict_0.items()):
    if item[1][1] == 0:
        print(item[0])

Build a function to remove the duplicate code:

def print_results(message, value):
    print(message)
    for item in sorted(nodes_dict_0.items()):
        if item[1][1] == value:
            print(item[0])

Then do:

print_results('\nMarked: ', 1)
print_results('\nReclaimed: ', 0)

---

Here is the rewritten code, with other small improvements like adding one / two more functions for readability:

import argparse
import re
import sys


def arg_parse():
    """Docstring here"""
    parser = argparse.ArgumentParser(description='Some description')
    parser.add_argument('filename', help='Filename parameter for input file')
    return parser.parse_args()


def is_int(s):
    """Docstring here"""
    try:
        return int(s)
    except ValueError:
        return False


def node_trace(pointer, nodes_pointers, nodes):
    """Docstring here"""
    if is_int(pointer[0]):
        if nodes[pointer[0]][1] == 1:
            return
        else:
            nodes[pointer[0]][0] = 1
            nodes[pointer[0]][1] = 1

    for x in nodes_pointers:
        if x[0] == pointer[1] and nodes[x[0]][1] == 0:
            node_trace(x, nodes_pointers, nodes)

        if is_int(x[0]):
            if nodes[x[0]][1] == 1:
                nodes[x[1]][0] = 1
                nodes[x[1]][1] = 1
        else:
            nodes[x[1]][0] = 1
            nodes[x[1]][1] = 1
    

def get_nodes():
    """Docstring here"""
    nodes_pointers, nodes = [], {}
    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)

                nodes_pointers.append([split_line[0], split_line[1]])

        count = 0
        while count < node_count:
            nodes[str(count)] = [0, 0]
            count += 1

        for item in nodes_pointers:
            if not is_int(item[0]):
                node_trace(item, nodes_pointers, nodes)

    return nodes


def print_result(message, value, nodes):
    """Docstring here"""
    print(message)
    for item in sorted(nodes.items()):
        if item[1][1] == value:
            print(item[0])


def main():
    """Docstring here"""
    nodes = get_nodes()
    print_result('\nMarked: ', 1, nodes)
    print_result('\nReclaimed: ', 0, nodes)


if __name__ == '__main__':
    main()