File SequenceHeap.h

↰ Parent directory (ADS/priority)

The sequence heap of Sanders, beyond the book: a priority queue of plain items for many items, which works on sorted sequences merged in large batches instead of on a tree walked from the root at each operation, so that its memory is read and written in order and the caches see few misses where a heap [see File DaryHeap.h] misses at each level of a large tree.

Definition (ADS/priority/SequenceHeap.h)

Detailed Description

The new items go to an insertion heap of at most m items, small enough to stay in the first level of the cache; the best items wait in a deletion buffer, sorted. When the insertion heap is full, its items are sorted into a sequence that joins the group 1. The group i holds up to k sorted sequences, of at most :math:` m k^{i-1} ` items each, and a buffer of its best items, refilled by merging its sequences; when a group is full, its sequences are merged into one that joins the group i + 1 together with the buffer of that group. The deletion buffer is refilled by merging the buffers of the groups. The invariants are that the deletion buffer holds items not worse than any other item but those of the insertion heap, and that the buffer of a group holds items not worse than those of the sequences of its group; to keep them, a new sequence from the insertion heap is first merged with the deletion buffer and with the buffer of the group 1, which keep the best of the three. The best item is the better of the top of the insertion heap and of the first item of the deletion buffer.

With R groups, :math:` R = lceil log_k ( n / m ) rceil , each item is merged once per group it goes through, and the merges of k sequences cost :math: O( log k ) ` per item, so that push() and pop() take :math:` O( log m + log k cdot R ) = O( log n ) ` amortized comparisons, as a binary heap, but with :math:` O( ( 1 / B ) log_{M / B} ( n / M ) ) ` amortized misses per item in a cache of M items in blocks of B, against the :math:` O( log ( n / M ) ) ` of a heap (Sanders, theorem 1, with m and k chosen as :math:` Theta( M ) ` and :math:` Theta( M / B ) ). Here m = 4096, so that the insertion heap of the pairs of two words fills the first level of the cache and its sequences the second, and k = 16. The merges are done by trees of losers [see :ref:`file_ADS_priority_LoserTree.h] with the first keys of the sequences at hand and their matches decided by conditional moves; the merge of a new sequence with the two buffers is a merge of two (the deletion buffer and the buffer of the group 1 make one sorted sequence), and a new sequence whose best item is not better than both joins the group with no merge. The numbers and the pairs of numbers ordered by std::less or std::greater are compared in the merges by their keys [see File OrderKey.h], one comparison of words with no jump, and their sequences sorted by the radix sort [see File RadixSort.h]; the insertion heap is 4-ary, as DaryHeap, and compares by better(), whose jumps the processor predicts ahead where the conditional moves of the keys would chain the loads of the walk down.

The pushes into an empty heap, before any top() or pop(), go to a bulk, an array in the order of the pushes: an insertion is a store. The first look at a large bulk finds its best item by a scan of the array, which costs one read per item and serves a top() or a pop() after a load; at the next one the bulk becomes an incremental quicksort, which splits the array, by the median of three, into the better items, the pivot and the others, keeps the places of the pivots on a stack and splits again only the leftmost part, until it holds at most m items, which are sorted into the buffer of the bulk, a further source of the deletion buffer besides the groups: :math:` O( n + k log k ) ` expected time for the k best items of n, and :math:` O( log n ) ` amortized per extraction (Paredes and Navarro), with the passes over the array in order and a split with no jump, a swap at every step. The items equal to a pivot that has no better one are split off with it, so that many equal keys cost no quadratic time. A small bulk goes to the insertion heap, which is made a heap only when a top() or a pop() needs it.

There are no handles and no decrease-key, as in DaryHeap: an item whose key improves is pushed again and the stale copy skipped.

The contracts [see File Contract.h]: top() and pop() need a heap that is not empty; the invariant, checked on heaps of at most 4096 items, is that the sequences and the buffers are sorted, that the deletion buffer is not worse than the groups and the bulk, the buffer of a group not worse than its sequences and that of the bulk not worse than the bulk, and that the parts count size() items. The operations are defined in SequenceHeap.tpp.

  1. Sanders, Fast priority queues for cached memory, ACM Journal of Experimental Algorithmics 5, article 7, 2000, doi:10.1145/351827.384249

  1. Paredes, G. Navarro, Optimal incremental sorting, Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX), 171-182, 2006, doi:10.1137/1.9781611972863.16

  1. Navarro, R. Paredes, On sorting, heaps, and minimum spanning trees, Algorithmica 57(4), 585-620, 2010, doi:10.1007/s00453-010-9400-6

  1. LaMarca, R. E. Ladner, The influence of caches on the performance of heaps, ACM Journal of Experimental Algorithmics 1, article 4, 1996, doi:10.1145/235141.235145

  1. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev, Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Springer, 2019, chapter 6, doi:10.1007/978-3-030-25209-0

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes