Compressing the Graphs in the G-machine by Tag-Forwarding

Abstract

G-machine is an efficient implementation of lazy functional languages. It is a fast way to perform the graph reduction. However, it needs a lot of space to store the graphs, which seems an inherent deficiency of graph reduction. In this paper, we propose a way to compress the graphs by forwarding the tag of a graph node to the location of a pointer pointing to the node. A tag is forwarded with the relative address which is used to find the location of data fields of the node. The tag-forwarding is possible only when a graph is allocated at once. Hence, it cannot be applied when some nodes of a graph are allocated before the construction of the whole graph. Nonetheless, we can reduce the heap usage to a certain amount by applying the tag-forwarding to the part of a graph which is allocated at once. The overhead of decoding the tag-forwarded graphs is imposed at run-time. To estimate the overhead some experiments are performed. According to the experimental results, the total heap space used is reduced about thirty percent on average and the run-time overhead of decoding is tolerable comparedd to the griginal G-machine.