Getting back to my discussion of merging multiple lists.

Testing relative performance of the different merge algorithms turned out to be more involved than I had originally thought it would be. I found the results somewhat surprising.

The short version is that in a normal procedural implementation, the pairwise merge is faster than the heap based merge, except in rare cases of many lists with very large differences in the lists’ lengths. But when it comes to LINQ implementation, the heap based merge is faster due to complications in the way that multiple criteria are handled.

I found the first result very surprising because the heap-based merge is provably optimum from a theoretical standpoint. But it turns out that managing the heap is expensive compared to just iterating lists. Even more surprising is that the difference in speed increases as the number of lists grows. That is, when merging five lists that are the same size the pairwise merge is perhaps 10% faster than the heap based merge. When merging 10 lists, it will be 15 to 20 percent faster. I found that result surprising.

At first I thought the difference was because my heap based merge implementation made use of my generic DHeap class, which adds some overhead. So I rewrote the merge to use a custom heap that’s optimized for this application. That made the heap merge faster, but not faster enough to overtake the pairwise merge.

The relative speed of the two implementations is somewhat sensitive to the keys being compared. As key comparisons become more expensive the heap based merge begins to outperform the pairwise merge. When merging strings, for example, the heap based merge is closer to the same speed as the pairwise merge. With very expensive comparisons, the heap based merge is clearly the faster of the two.

The reason for this is simple. The runtime complexity of the algorithms is based on the number of comparisons. The heap based merge will never do more than n log k comparisons, so when comparison speed becomes the limiting factor the algorithm that does the fewest comparisons will be the fastest.

After testing performance of the algorithms as standard method calls, I began creating LINQ-callable methods called MergeBy and PairwiseMergeBy. The heap based merge conversion was straightforward and doesn’t look fundamentally different from the MergeWithBy extension method that I presented a while back.

The pairwise merge works by creating a merging network that does multiple merges in parallel. That is, given eight lists to merge, labeled ListA through ListH, it creates the following merge operations:

Merge A and B to create AB
Merge C and D to create CD
Merge E and F to create EF
Merge G and H to create GH
Merge AB and CD to create ABCD
Merge EF and GH to create EFGH
Merge ABCD and EFGH to create ABCDEFGH

It creates an inverted tree of merges that looks like this:

    A     B   C     D   E     F   G     H
    |     |   |     |   |     |   |     |
    +--+--+   +--+--+   +--+--+   +--+--+
       |         |         |         |
       +----+----+         +----+----+
            |                   |
            +---------+---------+
                      |
                    Output

So I have seven different merges running concurrently. The first problem is that this requires twice as much memory as the heap based merge. The heap based merge requires memory proportional to the number of lists (N) times the number of keys (K). That is, N*K memory.

The pairwise merge has N-1 merges running in parallel, each of which requires (2 * K). So the pairwise merge memory requirement is (2 * (N-1) * K) for the keys, and (N – 1) for the iterators. That’s not a huge deal, because the number of lists and the number of keys are both typically small. If we were merging millions of lists this might be a concern. Still, the additional memory is a drawback.

The bigger problem turned out to be structuring the code so that it worked and was understandable. If you’ve been following along, you know that implementing the IOrderedEnumerable interface is complicated enough. Adding this complexity on top of it made things really convoluted. And by the time I got it all working, the pairwise merge just wasn’t consistently faster enough to justify the complexity. So I junked the idea. The final code uses the heap based merge.

The resulting MergeBy method is not an extension method. Rather, it’s a static method in the LinqExtensions namespace.

    public static IOrderedEnumerable MergeBy(
        <IEnumerable> lists,
        Func keyExtractor,
        IComparer comparer = null);

There is also a MergeByDescending method, and you can use the ThenBy and ThenByDescending methods to add multiple merge keys.

I’ll publish the final code in the next posting. That will contain all of the merging code I’ve developed in this series.