Reasoning about Complexity of Object-Oriented Programs
Heinz W. Schmidt, Wolf Zimmermann · 1994
This report develops an appropriate fundamental approach towards performance estimation, measurement and metering in OO approaches. We use examples written in the Sather language to demonstrate the concepts of so-called OO-machines, which lend themselves to performance metrics, and a calculus for reasoning about performance. A language binding of these concepts is then sketched in the form of cost annotations that allow programmers to file classes in libraries well-documented with cost related specifications. These annotations can optionally be used for instrumenting code that meters cost and checks whether the taken measurements are consistent with the given specification. In this way programmers can benefit from cost annotations by means of documentation and rigorous testing without requiring a deep familiarity with the theoretical underpinnings. Keywords: Object-Oriented Languages, Complexity, Amortized Complexity