Automatically Choosing Implementations for Abstract Data Types

Sammanfattning: The data structures that are used in a program can have a significant effect on how well it performs. The main objective of this degree project is to make the choice of data structures automatic by using abstract data types and developing an algorithm that applies static program analysis to make an as optimal choice as possible. As a result, we hope to achieve programs with better runtime characteristics without relying on the knowledge or dedication of programmers. We evaluate the design of our solution by implementing a concrete version as part of an interpreter. More specifically, we assess our solution based on its efficiency and suitability. With the efficiency of our solution, we try to determine if it is fast enough to be useful. Our results show that even though our solution makes the interpreter slower, we can potentially earn this overhead back, and even end up gaining time, if we select suitable data structures. Therefore, we draw the conclusion that our solution is efficient enough. The suitability of our solution instead is concerned with whether our solution successfully predicts and selects the data structures that have the best runtime characteristics on different programs. From our results we draw the conclusion that our solution can not be said to be suitable and that we might as well select data structures randomly. When evaluating the cost system that we use to estimate the performance of data structures, we determine that it is too simplistic and has to be further developed or combined with other techniques, such as dynamic program analysis.