File MultiwayMerge.h

↰ Parent directory (ADS/priority)

The engineered merge of k sorted sequences, beyond the book [see File LoserTree.h for the tree of losers of the notes]: FlatLoserTree, the tree of losers with the keys in its nodes, for the merges whose sequences arrive a block at a time, and multiwayMerge(), the merge of k sorted ranges in memory, by a funnel of binary mergers.

Definition (ADS/priority/MultiwayMerge.h)

Detailed Description

  • FlatLoserTree keeps in each of its :math:` K - 1 ` internal nodes, K the power of two not below k, the key of the loser of the match played there and its source, instead of the index of the player alone: a replay walks the :math:` log_2 K ` nodes from the leaf of the winner to the root, and each match reads the key in the node, which lies in the array of the tree, never in the sequence of the loser. A key of at most 16 bytes copied as bytes is kept by value, a larger one by its address, which must stay valid while it is in the tree. On the integers in their natural order a match compares the pairs :math:` ( x , s ) ` of key and source as one integer of 128 bits, and an exhausted source has the largest key and its index with the highest bit set, so that the matches are made of flags and the swaps of the winner with the loser of a node of masks, with no jump: the matches of a random merge are won by either side with probability 1/2, which a branch mispredicts half of the time. Equal keys are won by the lower source, so that a merge is stable; a replay makes :math:` lceil log_2 k rceil ` matches.

  • multiwayMerge() on contiguous ranges of items copied as bytes builds a tree of binary mergers, the halves of the sources below each node, with a buffer of 4 KiB at each internal node, filled lazily (the lazy funnel of Brodal, Fagerberg and Vinther with binary mergers): a node merges its two children into its buffer when the buffer runs out, a child being refilled when it runs out in turn. A merge goes by stretches as long as the least of the room left in its two inputs and its output, :math:` m = min{ | X | , | Y | , | O | } , since each step takes one item from one input, so that its m steps check no end; each step is a comparison, a store of the item picked by a mask and the advance of the input by the flag, with no jump. An item climbs :math: lceil log_2 k rceil ` mergers, :math:` O( n log k ) ` time with the constant of a merge of two sequences, the buffers taking :math:` 4 ( k - 1 ) ` KiB, in the cache for the fan-ins of the external sorts. Items of more than 16 bytes in 3 or 4 ranges are merged by computing at each step the least head of each pair and the least of the two, with no jump, over stretches as long as the shortest range, so that an item is copied once. Two ranges are merged by the same step with no jump, one range is copied, and the other iterators and types go through FlatLoserTree, :math:` O( n log k + k ) ` time.

Compared with the literature: the tree of losers with the keys in the nodes is that of Knuth (5.4.1), whose cache behaviour Sanders analysed for his sequence heaps; the multiway merge of the MCSTL of Singler, Sanders and Putze, in the parallel mode of libstdc++ and in tlx, has the same tree, with branches on the matches, and special merges of 3 and 4 sequences. The funnel is the k-merger of the cache-oblivious funnelsort of Frigo, Leiserson, Prokop and Ramachandran, made of binary mergers as Brodal, Fagerberg and Vinther engineered it; with no jump in its steps it beats the tree of losers by about 1.7 times on random keys, where every match of the tree is a coin toss for the predictor.

The contracts [see File Contract.h]: k >= 1 sources; top(), winner() and the replays on a tree that is not empty; the ranges of multiwayMerge() sorted by less, an audit, and the output their items sorted, a stable merge, an audit. The functions are defined in MultiwayMerge.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.4.1

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

  1. Singler, P. Sanders, F. Putze, MCSTL: the multi-core standard template library, Euro-Par 2007, LNCS 4641, 682-694, 2007, doi:10.1007/978-3-540-74466-5_72

  1. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran, Cache-oblivious algorithms, ACM Transactions on Algorithms 8(1), 1-22, 2012, doi:10.1145/2071379.2071383

    1. Brodal, R. Fagerberg, K. Vinther, Engineering a cache-oblivious sorting algorithm, ACM Journal of Experimental Algorithmics 12, 1-23, 2008, doi:10.1145/1227161.1227164

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Variables