Comparing priority queues with support for priority updates at arbitrary indexes

Sammanfattning: The research software URDME makes use of a priority queue that has support for updating the priority of enqueued elements at arbitrary indexes. To achieve this URDME currently relies on a Binary Heap. In this thesis, we consider and evaluate other priority queues, with an awareness of spatial locality and cache performance, that could potentially replace the Binary Heap in URDME. Three different priority queue implementations were considered, Binomial Heaps, Fibonacci Heaps, and d-ary Heaps. The three heaps were then compared with a weighted combination of literature review,analysis of spatial locality, and analysis using the RAM-model. Due to a lot of the literature being critical of the practical performance of the Fibonacci Heap, as well as the poor spatiallocality exhibited by both the Fibonacci Heap and Binomial Heap, these two were excluded from further evaluation. An instance of the d-ary Heap, the 4-ary heap, showed great promise as it reduced the number of potential cache misses by cutting the height of the tree in half. The 4-ary Heap was then implemented and optimized for greater cache performance along with the Binary Heap. The optimized, as well as the non-optimized 4-ary Heap, performed better than their binary counterparts in our tests on large inputs.The optimized 4-ary Heap was almost 30% faster than the originalBinary Heap and 10% faster than the non-optimized 4-ary Heap. The non- optimized 4-ary Heap was 17% faster than the original Binary Heap. The optimization did not work for the Binary Heap. While the cache-optimization did improve the performance of the 4-ary Heap it did not work as intended. It was suggested that this difference in performance was instead due to a difference in response to compiler optimizations, specifically function cloning. It was concluded that while the optimized 4-ary Heap was the fastest in our tests, the results may vary from machine to machine, as such it might not be a wise choice for a software that is intended to be used on a variety of machines. Instead, it would be wiser to replace the Binary Heap with a non-optimized 4-ary Heap.