3
\$\begingroup\$

Before I tried this, my impression was that (bottom up) merge sort would be memory (actual RAM) bound, and not affected much by multithreading, but a 4 thread sort is about 3.0 times as fast as a single thread sort, and an 8 thread sort is about 3.9 times as fast. This is on a 4 core Intel 3770k (3.5 ghz), Win 7, 64 bit mode, Visual Studio 2015. One gain of the 4/8 threads is using all 4 L1 and L2 caches local to each core, but L3 and main memory are shared. This example sorts 16 million 32 bit positive integers, taking about 0.36 seconds for 8 thread version, 0.47 seconds for 4 thread version, 1.41 seconds for 1 thread version.


Most of the time is spent in the // merge data loop in BottomUpMerge() (compare two elements from two sub-arrays, move smaller to output array). My assumption was that this relatively small loop would be fast enough to be main memory bandwidth limited, but this isn't true. For the 16 million 32 bit integers, the 24 passes to merge sort read/writes 3221225472 (3GB) bytes of data, so the single thread bandwidth is ~2.2845 GB/sec, the 4 thread bandwidth is ~6.8535 GB/sec, 8 thread is ~8.9478 GB/sec. Max bandwidth for 3770k is 25.6 GB/sec. Actual bandwidth for an assembly move memory (rep movsd ;to move 16MB data), is about 18 GB/sec.

So the issue is that the merge sort is CPU bound, not memory (RAM) bound, even with a relatively tight loop, at least on my system.

I tried a similar comparison on an older (2004) system, Intel Pentium 4 EE (3.73 ghz, 2 cores) on a Intel 975 motherboard, and a 2 thread merge sort is about 1.65 times as fast as a single thread sort. Single threaded bandwidth is ~1.6433 GB/sec, two threaded is ~2.7115 GB/sec, assembly move is ~3.1236 GB/sec. Four threaded is a bit slower than two threaded with this system.


Example code for the 4 thread version, the single threaded sort uses the same functions for the merge sort. Size is assumed to be multiple of 4 (else a minor change to handling the last "quarter" size could be done).

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <windows.h>

#define SIZE (16*1024*1024)             // must be multiple of 4

static HANDLE hs0;                      // semaphore handles
static HANDLE hs1;
static HANDLE hs2;
static HANDLE hs3;
static HANDLE ht1;                      // thread handles
static HANDLE ht2;
static HANDLE ht3;

static DWORD WINAPI Thread0(LPVOID);    // thread functions
static DWORD WINAPI Thread1(LPVOID);
static DWORD WINAPI Thread2(LPVOID);
static DWORD WINAPI Thread3(LPVOID);

static int  *pa;                        // pointers to buffers
static int  *pb;

void BottomUpMergeSort(int a[], int b[], size_t n);
void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee);
size_t GetPassCount(size_t n);

int main()
{
int *array = new int[SIZE];
int *buffer = new int[SIZE];
clock_t ctTimeStart;                    // clock values
clock_t ctTimeStop;
    pa = array;
    pb = buffer;
    for(int i = 0; i < SIZE; i++){      // generate pseudo random data
        int r;
        r  = (((int)((rand()>>4) & 0xff))<< 0);
        r += (((int)((rand()>>4) & 0xff))<< 8);
        r += (((int)((rand()>>4) & 0xff))<<16);
        r += (((int)((rand()>>4) & 0x7f))<<24);
        array[i] = r;
    }

    hs0 = CreateSemaphore(NULL,0,1,NULL);
    hs1 = CreateSemaphore(NULL,0,1,NULL);
    hs2 = CreateSemaphore(NULL,0,1,NULL);
    hs3 = CreateSemaphore(NULL,0,1,NULL);
    ht1 = CreateThread(NULL, 0, Thread1, 0, 0, 0);
    ht2 = CreateThread(NULL, 0, Thread2, 0, 0, 0);
    ht3 = CreateThread(NULL, 0, Thread3, 0, 0, 0);

    ctTimeStart = clock();
    ReleaseSemaphore(hs0, 1, NULL);     // start sorts
    ReleaseSemaphore(hs1, 1, NULL);
    ReleaseSemaphore(hs2, 1, NULL);
    ReleaseSemaphore(hs3, 1, NULL);
    Thread0((LPVOID)NULL);              // run and "wait" for thread 0
    WaitForSingleObject(ht2, INFINITE); // wait for thread 2
    // merge 1st and 2nd halves
    BottomUpMerge(pb, pa, 0, SIZE>>1, SIZE);
    ctTimeStop = clock();
    std::cout << "Number of ticks " << (ctTimeStop - ctTimeStart) << std::endl;

    for(int i = 1; i < SIZE; i++){      // check result 
        if(array[i-1] > array[i]){
            std::cout << "failed" << std::endl;
        }
    }
    CloseHandle(ht3);
    CloseHandle(ht2);
    CloseHandle(ht1);
    CloseHandle(hs3);
    CloseHandle(hs2);
    CloseHandle(hs1);
    CloseHandle(hs0);
    delete[] buffer;
    delete[] array;
    return 0;
}

static DWORD WINAPI Thread0(LPVOID lpvoid)
{
    WaitForSingleObject(hs0, INFINITE); // wait for semaphore
    // sort 1st quarter
    BottomUpMergeSort(pa + 0*(SIZE>>2), pb + 0*(SIZE>>2), SIZE>>2);
    WaitForSingleObject(ht1, INFINITE); // wait for thead 1
    // merge 1st and 2nd quarter
    BottomUpMerge(pa + 0*(SIZE>>1), pb + 0*(SIZE>>1), 0, SIZE>>2, SIZE>>1);
    return 0;
}

static DWORD WINAPI Thread1(LPVOID lpvoid)
{
    WaitForSingleObject(hs1, INFINITE); // wait for semaphore
    // sort 2nd quarter
    BottomUpMergeSort(pa + 1*(SIZE>>2), pb + 1*(SIZE>>2), SIZE>>2);
    return 0;
}

static DWORD WINAPI Thread2(LPVOID lpvoid)
{
    WaitForSingleObject(hs2, INFINITE); // wait for semaphore
    // sort 3rd quarter
    BottomUpMergeSort(pa + 2*(SIZE>>2), pb + 2*(SIZE>>2), SIZE>>2);
    WaitForSingleObject(ht3, INFINITE); // wait for thread 3
    // merge 3rd and 4th quarter
    BottomUpMerge(pa + 1*(SIZE>>1), pb + 1*(SIZE>>1), 0, SIZE>>2, SIZE>>1);
    return 0;
}

static DWORD WINAPI Thread3(LPVOID lpvoid)
{
    WaitForSingleObject(hs3, INFINITE); // wait for semaphore
    // sort 4th quarter
    BottomUpMergeSort(pa + 3*(SIZE>>2), pb + 3*(SIZE>>2), SIZE>>2);
    return 0;
}

void BottomUpMergeSort(int a[], int b[], size_t n)
{
size_t s = 1;                               // run size 
    if(GetPassCount(n) & 1){                // if odd number of passes
        for(s = 1; s < n; s += 2)           // swap in place for 1st pass
            if(a[s] < a[s-1])
                std::swap(a[s], a[s-1]);
        s = 2;
    }
    while(s < n){                           // while not done
        size_t ee = 0;                      // reset end index
        while(ee < n){                      // merge pairs of runs
            size_t ll = ee;                 // ll = start of left  run
            size_t rr = ll+s;               // rr = start of right run
            if(rr >= n){                    // if only left run
                do                          //   copy left run
                    b[ll] = a[ll];
                while(++ll < n);
                break;                      //   end of pass
            }
            ee = rr+s;                      // ee = end of right run
            if(ee > n)
                ee = n;
            BottomUpMerge(a, b, ll, rr, ee);
        }
        std::swap(a, b);                    // swap a and b
        s <<= 1;                            // double the run size
    }
}

void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
    size_t o = ll;                          // b[]       index
    size_t l = ll;                          // a[] left  index
    size_t r = rr;                          // a[] right index
    while(1){                               // merge data
        if(a[l] <= a[r]){                   // if a[l] <= a[r]
            b[o++] = a[l++];                //   copy a[l]
            if(l < rr)                      //   if not end of left run
                continue;                   //     continue (back to while)
            do                              //   else copy rest of right run
                b[o++] = a[r++];
            while(r < ee);
            break;                          //     and return
        } else {                            // else a[l] > a[r]
            b[o++] = a[r++];                //   copy a[r]
            if(r < ee)                      //   if not end of right run
                continue;                   //     continue (back to while)
            do                              //   else copy rest of left run
                b[o++] = a[l++];
            while(l < rr);
            break;                          //     and return
        }
    }
}

size_t GetPassCount(size_t n)               // return # passes
{
    size_t i = 0;
    for(size_t s = 1; s < n; s <<= 1)
        i += 1;
    return(i);
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

You've tagged the question with C, but your code includes a lot of C++ features that are not available in C:

  • new operator
  • std::swap
  • std::cout

As Visual Studio has no problem with C++ (even defaults to it), embracing it's facilities can make your code much cleaner:

  • RAII and smart pointers remove the need for remembering to delete buffers or close handles
  • Threading support in the C++(11+) standard library makes your code portable and cleaner (you can pass functions with any types of parameters for starting threads)
  • Classes and lambdas allow for better encapsulation, no more global state
  • Templates, standard iterator and comparison objects allow you to more easily integrate your code with other code bases and make it more generic (sort any kind of objects with arbitrarily complex comparisons)
  • #include <random> provides better pseudo-random generators.
\$\endgroup\$
6
  • \$\begingroup\$ I didn't tag it as C, not sure who did that. It's fixed now. As for the rest of your answer, all valid points, but the question is about the performance improvement of multi-threading on an algorithm that I thought would be memory (ram) bandwidth limited, not about the specifics of the example code used to demonstrate the issue, and making the suggested changes would have little effect on the performance. \$\endgroup\$
    – rcgldr
    Nov 25, 2016 at 11:21
  • 1
    \$\begingroup\$ @rcgldr but making the changes would have a large effect on readability/maintainability of the code. Which for something that only takes 1 sec to run is much more important. \$\endgroup\$ Nov 28, 2016 at 9:13
  • \$\begingroup\$ @rcgldr why would you think there is a memory bandwidth problem when you have such a large range? Each of the caches loads in sections not single byte ranges. Thus most memory requests are resolved from the cache not from main memory. And there is no overlap with theses ranges so no cache invalidation to slow things down. \$\endgroup\$ Nov 28, 2016 at 9:16
  • \$\begingroup\$ @LokiAstari - I updated my question. I thought that the key small loop would be memory bound, but it's cpu bound instead. \$\endgroup\$
    – rcgldr
    Nov 28, 2016 at 19:42
  • 1
    \$\begingroup\$ @D.Jurcau - I also tried an 8 thread merge sort, which was faster, but only increased the speed from 3.0 to 3.9. This uses 2 hyperthreads on each of the 4 cores, so L1 and L2 cache are shared between two threads, but these are 8 way set associative caches, and I assume each thread mostly consumes 3 data cache lines, 2 for the two input sub-arrays, 1 for the output array. \$\endgroup\$
    – rcgldr
    Nov 28, 2016 at 22:47

Your Answer

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

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