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/