Diseño, implementación y evaluación de una colección adaptativa

Abstract

La creación y manipulación de colecciones de valores está ampliamente soportada por los lenguajes de programación modernos. A pesar de que cada lenguaje viene con su propia implementación de colecciones, la mayoría de las implementaciones encontradas son muy similares en estructura y funcionalidad ofrecida. Una excepción notable es el caso de Lua, pues presenta una sola colección: la tabla. Esta estructura es la unificación de una colección expansible secuencial y un arreglo asociativo o diccionario. La tabla es una estructura híbrida, compuesta por una parte de hash y una parte de arreglo, y hará uso de sus estructuras internas según su uso: si es utilizada como lista hará uso del arreglo y si es usada como diccionario usará el hash. Esto permite flexibilidad y eficiencia pues las estructuras internas sólo se crean cuando requieren ser usadas. Este comportamiento adaptativo es interesante en cuanto sugiere buen rendimiento mientras que se muestra muy simple para el usuario. A pesar de que Lua ha logrado bastante popularidad, las tablas no han sido cuidadosamente estudiadas por la comunidad científica. La eficiencia no solo depende de la implementación de las colecciones, sino también de si se escoge la colección correcta, con los parámetros adecuados, para cada situación particular. La selección inadecuada de colecciones puede resultar en un sobrecosto severo. Por este motivo, contar con una forma automática de asignar la colección más adecuada para cada caso sería muy valioso en la práctica. El experimento Chameleon aborda este problema sobre la JVM, mediante la identificación automática de elecciones inadecuadas de colecciones a través de análisis en tiempo de ejecución. El reemplazo de las colecciones identificadas por otras más adecuadas permitió reducir el consumo de memoria hasta en un 55% y el tiempo de ejecución en un 60% en algunas aplicaciones. Este trabajo enfrenta el problema de determinar la aplicabilidad de la tabla de Lua, o un derivado de esta, en lenguajes con bibliotecas ricas de colecciones. Para esto se desarrollan tres colecciones en el lenguaje Pharo: SLua, SmartCollection y SmartCollection2. Estas luego se evalúan en comparación con las colecciones normales de Pharo y con una versión lazy de las mismas mediante distintos tipos de benchmarks que miden su tiempo de ejecución y consumo de memoria, y se realiza análisis dinámico para entender las diferencias en los resultados. Además, se aborda el problema de la selección adaptativa de colecciones y se replica el experimento Chameleon. Luego se usa la herramienta de selección y reemplazo automático de colecciones para evaluar las colecciones desarrolladas. Los resultados de los experimentos realizados mediante instrumentación muestran reducciones de hasta un 30% en consumo de memoria y hasta un 15% en tiempo de ejecución en algunos escenarios al reemplazar las colecciones tradicionales por las desarrolladas. Sin embargo, la evaluación posterior mediante la herramienta de reemplazo de colecciones a nivel de código fuente no reveló diferencias estadísticamente significativas entre los tiempos de ejecución y uso de memoria entre las distintas colecciones. Esto indica una amplificación de los resultados introducida por la instrumentación. Las colecciones de las librerías externas utilizadas por las aplicaciones estudiadas no fueron reemplazadas, por lo que se plantea estudiar el impacto del reemplazo de colecciones sobre estas como trabajo futuro.