Hostname: page-component-7c8c6479df-p566r Total loading time: 0 Render date: 2024-03-27T12:53:29.724Z Has data issue: false hasContentIssue false

Inductive benchmarking for purely functional data structures

Published online by Cambridge University Press:  29 August 2001

GRAEME E. MOSS
Affiliation:
Department of Computer Science, University of York, York, UK
COLIN RUNCIMAN
Affiliation:
Department of Computer Science, University of York, York, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Every designer of a new data structure wants to know how well it performs in comparison with others. But finding, coding and testing applications as benchmarks can be tedious and time-consuming. Besides, how a benchmark uses a data structure may considerably affect its apparent efficiency, so the choice of applications may bias the results. We address these problems by developing a tool for inductive benchmarking. This tool, Auburn, can generate benchmarks across a wide distribution of uses. We precisely define ‘the use of a data structure’, upon which we build the core algorithms of Auburn: how to generate a benchmark from a description of use, and how to extract a description of use from an application. We then apply inductive classification techniques to obtain decision trees for the choice between competing data structures. We test Auburn by benchmarking several implementations of three common data structures: queues, random-access lists and heaps. These and other results show Auburn to be a useful and accurate tool, but they also reveal some limitations of the approach.

Type
Research Article
Copyright
© 2001 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.