A machine learning approach for data structure selection

Abstract

Uma seleção de estrutura de dados adequada pode melhorar bastante o desempenho e uso de memória de um programa. Porém, é difícil entender o comportamento de uma estrutura de dados em uma aplicação antes de executá-la, o que torna complexa a tarefa de escolher a melhor estrutura de dados para o uso em um programa de computador. Esta dissertação apresenta um framework capaz de selecionar, de maneira automática, estruturas de dados para um programa e sua entrada. O framework é formado por quatro componentes: um componente para extração de dados, que coleta informação sobre o comportamento das estruturas de dados usadas no programa dado como entrada; um construtor de features, que transforma as informações extraídas em features para modelos de aprendizado de máquina; dois modelos de aprendizado de máquina que selecionam automaticamente estruturas de dados para serem usadas com o conjunto de programa e entrada; e um reconstrutor de programas que cria uma nova versão da aplicação dada como entrada usando as estruturas de dados selecionadas pelos modelos. O framework é avaliado em aplicações sintéticas e reais e é capaz de atingir a mesma acurácia que os desenvolvedores originais ao escolher estruturas de dados para as aplicações.