Memory-Efficient and Thread-Safe Quasi-Destructive Graph Unification

Memory-Efficient and Thread-Safe Quasi-Destructive Graph Unification Marcel P. van Lohuizen Department of Information Technology and Systems Delft University of Technology mpvl@acm.org Abstract In terms of both speed and mem- ory consumption, graph unification remains the most expensive com- ponent of unification-based gram- mar parsing. We present a tech- nique to reduce the memory usage of unification algorithms consider- ably, without increasing execution times. Also, the proposed algorithm is thread-safe, providing an efficient algorithm for parallel processing as well. 1 Introduction Both in terms of speed and memory consump- tion, graph unification remains the most ex- pensive component in unification-based gram- mar parsing. Unification is a well known algo- rithm. Prolog, for example, makes extensive use of term unification. Graph unification is slightly different. Two different graph nota- tions and an example unification are shown in Figure 1 and 2, respectively. In typical unification-based grammar parsers, roughly 90% of the unifications fail. Any processing to create, or copy, the result graph before the point of failure is b e A C F D   A = b C = 1 � D = e � F = 1   Figure 1: Two ways to represent an identical graph. redundant. As copying is the most expensive part of unification, a great deal of research has gone in eliminating superfluous copying. Examples of these approaches are given in (Tomabechi, 1991) and (Wroblewski, 1987). In order to avoid superfluous copying, these algorithms incorporate control data in the graphs. This has several drawbacks, as we will discuss next. Memory Consumption To achieve the goal of eliminating superfluous copying, the aforementioned algorithms include adminis- trative fields—which we will call scratch fields—in the node structure. These fields do not attribute to the definition of the graph, but are used to efficiently guide the unifica- tion and copying process. Before a graph is used in unification, or after a result graph has been copied, these fields just take up space. This is undesirable, because memory usage is of great concern in many unification-based grammar parsers. This problem is especially of concern in Tomabechi’s algorithm, as it in- creases the node size by at least 60% for typ- ical implementations. In the ideal case, scratch fields would be stored in a separate buffer allowing them to be reused for each unification. The size of such a buffer would be proportional to the maximum number of nodes that are involved in a single unification. Although this technique reduces memory usage considerably, it does not re- duce the amount of data involved in a single unification. Nevertheless, storing and loading nodes without scratch fields will be faster, be- cause they are smaller. Because scratch fields are reused, there is a high probability that they will remain in cache. As the difference � A = � B = c � D = � E = f � � ⊔   A = 1 � B = c � D = 1 G = � H = j �  …

Content truncated to 500 words