6

Is there any algorithm that makes it parallel sorting of a linked list worth it?

It's well known that Merge Sort is the best algorithm to use for sorting a linked list.

Most merge sorts are explained in terms of arrays, with each half recursively sorted. This would make it trivial to parallelize: sort each half independently then merge the two halves.

But a linked list doesn't have a "half-way" point; a linked list goes until it ends:

Head → [a] → [b] → [c] → [d] → [e] → [f] → [g] → [h] → [i] → [j] → ...

The implementation i have now walks the list once to get a count, then recursively splits the counts until we're comparing a node with it's NextNode. The recursion takes care of remembering where the two halves are.

This means the MergeSort of a linked list progresses linearly through the list. Since it seems to demand linearly progression through a list, i would think it then cannot be parallelized. The only way i could imagine it is by:

  • walk the list to get a count O(n)
  • walk half the list to get to the halfway point O(n/2)
  • then sort each half O(n log n)

But even if we did parallelize sorting (a,b) and (c,d) in separate threads, i would think that the false sharing during NextNode reordering would kill any virtue of parallelization.

Is there any parallel algorithms for sorting a linked list?

Array merge sort algorithm

Here is the standard algorithm for performing a merge sort on an array:

algorithm Merge-Sort
    input:
        an array, A (the values to be sorted)
        an integer, p (the lower bound of the values to be sorted)
        an integer, r (the upper bound of the values to be sorted)

    define variables:
        an integer, q (the midpoint of the values to be sorted)

    q ← ⌊(p+r)/2⌋
    Merge-Sort(A, p, q)   //sort the lower half
    Merge-Sort(A, q+1, r) //sort the upper half   
    Merge(A, p, q, r)     

This algorithm is designed, and meant, for arrays, with arbitrary index access. To make it suitable for linked lists, it has to be modified.

Linked-list merge sort algorithm

This is (single-threaded) singly-linked list, merge sort, algorithm i currently use to sort the singly linked list. It comes from the Gonnet + Baeza Yates Handbook of Algorithms

algorithm sort:
    input:
        a reference to a list, r (pointer to the first item in the linked list)
        an integer, n (the number of items to be sorted)
    output:
        a reference to a list (pointer to the sorted list)
    
    define variables:
        a reference to a list, A (pointer to the sorted top half of the list)
        a reference to a list, B (pointer to the sorted bottom half of the list)
        a reference to a list, temp (temporary variable used to swap)

    if r = nil then
        return nil

    if n > 1 then
        A ← sort(r, ⌊n/2⌋ )
        B ← sort(r, ⌊(n+1)/2⌋ )
        return merge( A, B )

    temp ← r
    r ← r.next
    temp.next ← nil
    return temp

A Pascal implementation would be:

function MergeSort(var r: list; n: integer): list;
begin
   if r = nil then 
       Result := nil
   else if n > 1 then
      Result := Merge(MergeSort(r, n div 2), MergeSort(r, (n+1) div 2) )
   else
   begin
      Result := r;
      r := r.next;
      Result.next := nil;
   end
end;

And if my transcoding works, here's an on-the-fly C# translation:

list function MergeSort(ref list r, Int32 n)
{
   if (r == null)
      return null;

    if (n > 1)
    {
       list A = MergeSort(r, n / 2);
       list B = MergeSort(r, (n+1) / 2);
       return Merge(A, B);
    }
    else
    {
       list temp = r;
       r = r.next;
       temp.next = null;
       return temp;
    }
}

What i need now is a parallel algorithm to sort a linked list. It doesn't have to be merge sort.

Some have suggested copying the next n items, where n items fit into a single cache-line, and spawn a task with those.

Sample data

algorithm GenerateSampleData
    input:
        an integer, n (the number of items to generate in the linked list)
    output:
        a reference to a node (the head of the linked list of random data to be sorted)

    define variables:
        a reference to a node, head (the returned head)
        a reference to a node, item (an item in the linked list)
        an integer, i (a counter)

    head ← new node
    item ← head        

    for i ← 1 to n do
        item.value ← Random()
        item.next ← new node
        item ← item.next

    return head

So we could generate a list of 300,000 random items by calling:

head := GenerateSampleData(300000);

Benchmarks

Time to generate 300,000 items    568 ms

MergeSort 
    count splitting variation   3,888 ms (baseline)

MergeSort
    Slow-Fast midpoint finding  3,920 ms (0.8% slower)

QuickSort
    Copy linked list to array       4 ms
    Quicksort array             5,609 ms
    Relink list                     5 ms
    Total                       5,625 ms (44% slower)

Bonus Reading

3
  • You could try to copy the list into an array, sort it in parallel, and recreate the linked list from the sorted array if necessary. It is hard to say without a benchmark whether it would be worth it.
    – jfs
    Nov 2, 2013 at 7:34
  • In a serial benchmark array-based variant (std::sort) is slightly faster than pure linked list analogs on my machine (to reproduce, compile benchmark.c as c++). Note: if the code is compiled as C then the qsort() function along (without array<->list conversion) is slower than any of the linked-list sort functions in this case.
    – jfs
    Nov 3, 2013 at 18:58
  • I've implemented my suggestion. In the parallel openmp-based merge-sort (List_sort_parallel_omp() function), array-based sort at the leafs (List_sorted_qsort) improves time performance two times compared to merge-sort that uses only linked lists (List_sort, List_sort_recursive functions).
    – jfs
    Nov 7, 2013 at 7:10

5 Answers 5

5

Mergesort is perfect for parallel sorting. Split the list in two halves and sort each of them in parallel, then merge the result. If you need more than two parallel sorting processes, do so recursively. If you don't happen to have infinitely many CPUs, you can omit parallelization at a certain recusion depth (which you will have to determine by testing).

BTW, the usual approach to splitting a list in two halves of roughly the same size is Floyd's Cycle Finding algorithm, also known as the hare and tortoise approach:

Node MergeSort(Node head)
{
   if ((head == null) || (head.Next == null))
      return head; //Oops, don't return null; what if only head.Next was null

   Node firstHalf = head;
   Node middle = GetMiddle(head);
   Node secondHalf = middle.Next;
   middle.Next = null; //cut the two halves

   //Sort the lower and upper halves
   firstHalf = MergeSort(firstHalf);
   secondHalf = MergeSort(secondHalf);

   //Merge the sorted halves 
   return Merge(firstHalf, secondHalf);
}

Node GetMiddle(Node head)
{
   if (head == null || head.Next == null)
       return null;

   Node slow = head;
   Node fast = head;
   while ((fast.Next != null) && (fast.Next.Next != null))
   {
       slow = slow.Next;
       fast = fast.Next.Next;
   }
   return slow;
}

After that, list and list2 are two lists of roughly the same size. Concatenating them would yield the original list. Of course, fast = fast->next->next needs further attention; this is just to demonstrate the general principle.

enter image description here

0
0

Merge-Sort is a Divide and Conquer Algorithm.

Arrays are good at dividing in the Middle.

Linked lists are innefficient to divide at the Middle, so instead, let's divide them while we walk through the list.

Take the first  element and put it in list 1.
Take the second element and put it in list 2.
Take the third  element and put it in list 1.
...

You have now divided the list in half efficiently, and with a bottom-up merge sort you can start the merging steps while you are still walking over the first list dividing it into odds and evens.

0

You can do merge sort in two ways. First you divide list in two half and then apply merge sort recursively on both parts and merge result. But there is another approach. You can split list into pairs and then merge pair of pairs recursively until you get single list which is result. See for example implementation of Data.List.sort in ghc haskell. This algorithm can be made parallel by spawning processes (or threads) for some appropriate amount of pairs at start and then also for merging their results until there is one.

0

For an inefficient solution, use the Quicksort algorithm: the first element in the list is used as a pivot, to partition the unsorted list into three (this uses O(n) of time). Then you recursively sort the lower and higher sublists in separate threads. The result is obtained by concatenating the lower sublist with the sublist of keys equal to the pivot and then the upper sublist in O(1) additional steps (instead of the slow merging).

0

i wanted to include a version that actually handles the parallel work (using native Windows thread-pool).

You don't want to put work into a threads all the way down the dividing recursion tree. You only want to schedule as much work as there are CPUs. This means you have to know how many (logical) CPUs there are. For example, if you had 8 cores, then the first

  • initial call: 1 thread
  • first recursion: becomes 2 threads
  • second recursion: becomes 4 threads
  • third recursion: becomes 8 threads
  • forth recursion: perform the work without splitting more threads

Handle this by querying for the number of processors in the system:

Int32 GetNumberOfProcessors()
{
   SYSTEM_INFO systemInfo;
   GetSystemInfo(ref systemInfo);
   return systemInfo.dwNumberOfProcessors;
}

And then we change the recursive MergeSort function to support a numberOfProcessors argument:

public Node MergeSort(Node head)
{
    return MergeSort(head, GetNumberOfProcessors());
}

Each time we recurse, we divide numberOfProcessors/2. When the recursive function stops seeing at least two processors available, it stops putting work into the thread pool, and calculates it on the same thread.

Node MergeSort(Node head, Int32 numberOfProcessors)
{
   if ((head == null) || (head.Next == null))
      return head;

   Node firstHalf = head;
   Node middle = GetMiddle(head);
   Node secondHalf = middle.Next;
   middle.Next = null;

   //Sort the lower and upper halves
   if (numberOfProcessors >= 2)
   {
      //Throw the work into the thread pool, since we have CPUs left
      MergeSortOnTheadPool(ref firstHalf, ref secondHalf, numberOfProcessors / 2);

      //i only split this into a separate function to keep 
      //the code short and easily readable
   } 
   else
   {
      firstHalf = MergeSort(firstHalf, numberOfProcessors);
      secondHalf = MergeSort(secondHalf, numberOfProcessors);

   }
   //Merge the sorted halves 
   return Merge(firstHalf, secondHalf);
}

This parallel work could be done using your favorite language-available mechanic. Since the language i actually use (which isn't the C# this code looks to be written in) doesn't support asynnc-await, the Task Parallel Library, or any other language integrated parallel system, we do it the old fashioned way: Event with Interlocked operations. It's a technique i read in an AMD whitepaper once; complete with their tricks to eliminate the subtle race conditions:

void MergeSortOnThreadPool(ref Node listA, ref Node listB)
{
   Int32 nActiveThreads = 1; //Yes 1, to stop a race condition
   using (Event doneEvent = new Event())
   {
      //Put everything the thread will need into a holder object
      ContextInfo contextA = new Context();
      contextA.DoneEvent = doneEvent;
      contextA.ActiveThreads = AddressOf(nActiveThreads);
      contextA.List = firstHalf;
      contextA.NumberOfProcessors = numberOfProcessors/2;
      InterlockedIncrement(nActiveThreads);
      QueueUserWorkItem(MergeSortThreadProc, contextA);

      //Put everything the second thead will need into another holder object
      ContextInfo contextB = new Context();
      contextB.DoneEvent = doneEvent;
      contextB.ActiveThreads = AddressOf(nActiveThreads);
      contextB.List = firstHalf;
      contextB.NumberOfProcessors = numberOfProcessors/2;
      InterlockedIncrement(nActiveThreads);
      QueueUserWorkItem(MergeSortThreadProc, contextB);

      //wait for the threads to finish
      Int32 altDone = InterlockedDecrement(nThreads);
      if (altDone > 0) then
         doneEvent.WaitFor(INFINITE);
   }

   listA = contextA.Result; //returned to the caller as ref parameters
   listB = contextB.Result; 
}

The thread pool thread procedure has to do some housekeeping as well; watching to see if it's the last thread, and setting the event on it's way out:

void MergeSortThreadProc(Pointer Data);
{
    Context context = Context(Data);

    Node sorted = MergeSort(context.List, context.ProcessorsRemaining);
    context.Result = sorted;

    //Now do lifetime management
    Int32 altDone = InterlockedDecrement(context.ActiveCount^);
    if (altDone <= 0)
       context.DoneEvent.SetEvent;
}

Note: Any code is released into the public domain. No attribution required.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.