ATLAS: Automated Amortised Complexity Analysis of Self-adjusting Data Structures
Authors:
Open Access
- 15 July 2021
- book chapter
- Published by Springer Nature
- p. 99-122
Abstract
Being able to argue about the performance of self-adjusting data structures such as splay trees has been a main objective, when Sleator and Tarjan introduced the notion ofamortisedcomplexity.Analysing these data structures requires sophisticated potential functions, which typically contain logarithmic expressions. Possibly for these reasons, and despite the recent progress in automated resource analysis, they have so far eluded automation. In this paper, we report on the first fully-automated amortised complexity analysis of self-adjusting data structures. Following earlier work, our analysis is based on potential function templates with unknown coefficients.We make the following contributions: 1) We encode the search for concrete potential function coefficients as an optimisation problem over a suitable constraint system. Our target function steers the search towards coefficients that minimise the inferred amortised complexity. 2) Automation is achieved by using a linear constraint system in conjunction with suitable lemmata schemes that encapsulate the required non-linear facts about the logarithm. We discuss our choices that achieve a scalable analysis. 3) We present our tool $$\mathsf {ATLAS}$$ and report on experimental results forsplay trees,splay heapsandpairing heaps. We completely automatically infer complexity estimates that match previous results (obtained by sophisticated pen-and-paper proofs), and in some cases even infer better complexity estimates than previously published.
Keywords
This publication has 45 references indexed in Scilit:
- Multivariate amortized resource analysisACM Transactions on Programming Languages and Systems, 2012
- Boolean lexicographic optimization: algorithms & applicationsAnnals of Mathematics and Artificial Intelligence, 2011
- Multivariate amortized resource analysisACM SIGPLAN Notices, 2011
- The reachability-bound problemACM SIGPLAN Notices, 2010
- Closed-Form Upper Bounds in Static Cost AnalysisJournal of Automated Reasoning, 2010
- Static prediction of heap space usage for first-order functional programsACM SIGPLAN Notices, 2003
- A systematic analysis of splayingInformation Processing Letters, 1993
- Skip lists: a probabilistic alternative to balanced treesCommunications of the ACM, 1990
- Self-adjusting binary search treesJournal of the ACM, 1985
- Amortized Computational ComplexitySIAM Journal on Algebraic Discrete Methods, 1985