Date: 28 Feb 2006 From: jyrki@diku.dk Subject: PE-lab: Annual Report 2005 Performance Engineering Laboratory (PE-lab) http://www.diku.dk/~jyrki/PE-lab/ * Annual Report 2005 In 2005, the focus in the research done at the PE-lab was on efficient data structures. Both the theoretical and experimental efficiency of priority queues and hash tables was studied. For the research done, the following people were active contributors: Christopher Derek Curry (Industrial partner, Netcompany A/S) Amr Elmasry (External collaborator, Alexandria University) Claus Jensen (M.Sc. student) Jyrki Katajainen (Lab leader) Jørgen Havsberg Seland (M.Sc. student) Anders Thøgersen (B.Sc. student) Fabio Vitale (External M.Sc. student, University of Insubria). Other members of the PE-lab were: Andrei Bjarke Moskvitin Josephsen (M.Sc. student) Stephan Lynge Herlev Larsen (M.Sc. student) Jacob De Fine Skibsted (M.Sc. student) Research articles done under the auspices of the PE-lab are available via the CPH STL report series, see http://cphstl.dk. A more detailed description of the projects completed or started in 2005 is given below. * Priority queues [Amr, Claus, and Jyrki] The goal in this research was to develop efficient priority queues that support operations find-min(), insert(), decrease(), and delete(). That is, this work was done with the aim of finding alternatives to Fibonacci heaps and Run-relaxed heaps. Our focus was on simplicity as well as on the worst-case comparison complexity of delete() under the assumption that the other three operations have the worst-case cost of O(1). Currently, the best bound achieved by us is lg n + O(lg lg n) element comparisons. Three different data structures guaranteeing this performance were developed: multipartite relaxed binomial queue, two-tier pruned binomial queue, and relaxed weak queue. These were the first data structures which achieve the bound lg n + o(lg n) for the number of element comparisons performed by delete(). Of the three data structures, the last is the most space efficient requiring 3n + O(lg n) words of storage, in addition to the n elements stored. Research output: 3 articles * Double-ended priority queues [Amr, Claus, and Jyrki] In this study the comparison complexity of double-ended priority-queue operations was investigated. In addition to the normal priority-queue operations, a double-ended priority queue supports both find-min() and find-max(). Two general data-structural transformations were described which transform our efficient priority queues into double-ended priority queues. The resulting double-ended priority queues are the fastest among all known double-ended priority queues. Due to their generality, the data-structural transformations applied are of independent interest. Research output: 1 article * Experimental analysis of priority queues [Claus, Fabio, and Jyrki] The practical efficiency of various priority-queue structures was studied. The data structures considered include a navigation pile and a local heap which both had been devised by the members of the PE-lab. Several novel aspects about the representation of priority queues were considered: 1) How to make priority queues fully dynamic? 2) How to provide referential integrity? 3) How to improve the cache behaviour? 4) What is the relevance of pointer-based data structures? 5) What is the relevance of the compaction of data structures? Previously, these implementation issues had been studied sparsely, so our analyses provide a considerable increase in knowledge in this area. Research output: 2 papers * Experimental analysis of hash tables [Jørgen and Anders] The CPH STL is a high-performance C++ Standard Template Library implementation. In this project, we designed a modular framework for standards-compliant hash tables targeted for inclusion in the CPH STL. Within this framework, hash tables based on three different approaches, two of which were inspired by Per Åke Larson's "dynamic hashing", were implemented. The implementations were compared to existing hash-table implementations in exhaustive synthetic benchmarks. The conclusion was that none of the approaches were universally ideal, but that all had strong points, which made a case for our modular hash-table design. A few common hash-table optimizations were analysed, among them storing the results of hash-function computations, which greatly improved the cache performance of the tables, and the asymptotic running time when variable-length keys were used. Research output: 2 articles * Organizational design [Christopher and Jyrki] A preliminary version of the book "Reengineering a university department", which was internally distributed within our organization, was released in 2003. Now we revised the manuscript and submitted it to a publisher. Timely updates about the publication process will be available via the book's home page at http://www.diku.dk/~jyrki/bpr/. Research output: 1 book