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.