Graph transformation algorithms for array memory optimization in applicative languages
James R. McGraw, John E. Ranelletti · 1987
In applicative language implementations, the potential copying of array elements can severely restrict the efficiency of the run-time code. In many instances, copy avoidance can be achieved through memory preallocation. This PhD dissertation presents a compile-time graph algorithm strategy, for use with the SISAL programming language, that identifies cases where preallocating memory storage locations for array aggregates is possible. The preallocation actions to be taken are specified by providing intermediate language graph transformations that designate the run-time creation of memory buffers prior to array creation. The preallocation analysis algorithms predict a significant savings in the execution time of selected sample programs: more than 90% of the array copying operations can be removed from existing unoptimized implementations. The results indicate that array memory allocation for some applicative language programs can be efficient.