Date: Tue, 21 Sep 2010  
From: Jyrki Katajainen <jyrki@diku.dk>
Subject: Master's thesis on code tuning

Oral defence of master's thesis: Tuning the CPH STL component structures 
for meldable priority queues

Defender: Asger Bruun
Censor: Rolf Fagerberg
Supervisor: Jyrki Katajainen
Extra examiner: Amr Elmasry
Time: Tuesday, 28 September 2010 at 11.00–12.00
Place: Meeting room A 2-0-04+06

Defence will be held in Danish

Abstract:

In this thesis, combinations of heap structures and heap stores in the 
designs of J. Vuillemin, M.R. Brown, and the CPH STL (Copenhagen 
Standard Template Library) on addressable meldable priority queues are 
investigated and the components are further developed. The objective was 
to attain an effective combination in a clean way in the program-library 
setting.

We participated at the 9th International Symposium on Experimental 
Algorithms held in May 2010 in Italy and confirmed in an experimental 
study that the CPH STL weak queue was performance-wise competitive. The 
results are published in the article "Policy-based benchmarking of weak 
heaps and their relatives", which is included in this thesis.

The two-pointer structures by M.R. Brown consume one pointer less per 
element than the ordinary three-pointer perfect weak-heap substructure 
and are able to execute at almost comparable speed. The work of M.R. 
Brown furthermore contains interesting space-optimization opportunities 
for a generic program library, like the CPH STL, offering fast 
algorithms and compact data structures.

Generic policies play an important role in the design of the CPH STL. 
Constructive criticism is raised against its current way of specifying 
generic policies and possible solutions to some of the existing problems 
are proposed.

In conclusion, the study showed that the more complex two-pointer 
structures, although effective, should be only used in cases where these 
structures save more storage than the space of a single pointer per 
element, i.e. when the structures achieve a better memory alignment.

The thesis is available online at 
http://www.diku.dk/~jyrki/PE-lab/Asger/

PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/