Xavier Leroy

Collège de France

Science du logiciel

Année 2022-2023

Structures de données persistantes

Séminaire - Arthur Charguéraud : Comment allier persistance et performance

Cet exposé explore trois approches permettant d'optimiser les performances de programmes exploitant des structures persistantes. La première approche consiste à optimiser les structures purement fonctionnelles en augmentant l'arité des feuilles et des nœuds des arbres. La deuxième approche consiste à exploiter les effets de bords pour réaliser la persistance. La troisième approche consiste à modifier l'interface en autorisant des versions transitoires non persistantes, selon la technique dite de « transience ». Je montrerai comment mettre en pratique ces trois approches sur des diverses structures : piles, files, tableaux, et séquences sécables et concaténables.