Maks Verver - Evaluation of a Cache-Oblivious Data Structure

author:Maks Verver
title:Evaluation of a Cache-Oblivious Data Structure
keywords:cache efficiency, locality of reference, algorithms
graduation date:June 2008


In modern computer hardware architecture memory is organized in a hierarchy consisting of several types of memory with different memory sizes, block transfer sizes and access times. Traditionally, data structures are evaluated in a theoretical model that does not take the existence of a memory hierarchy into account. The cache-oblivious model has been proposed as a more accurate model. Although several data structures have been described in this model relatively little empirical performance data is available. This paper presents the results of an empirical evaluation of several data structures in a realistic scenario and aims to provide insight into the applicability of cache-oblivious data structures in practice.