Split Quick
This sort does the Quick-sort on Multiple-processors.
This was inspired by a comment that a friend made years ago that when Microsoft made their libraries thread safe, he also wished they would just be multi-threaded. His comment was "I don't want to do the multi-threading I thought that is what you were going to be doing". This is created with that idea in mind of "I as the programmer have a big task, I would like you the library to use resources to get it done". In much the same way when you call into a library and you don't give it a deadline or set amount of memory it is allowed to use, this just goes out and makes threads to use the extra cores if it thinks it would help.
Basic Design
This sort is based on pivot sort. We just allow multiple processors to help.
It works with several observations:
1. We can statistically gather a sample and then approximate what an ideal pivot would be.
2. The sooner we can get an additional core to help the better. We do not want only one core to act as the dispatcher.
3. The fewer Joins the better. We want each core to be able to complete it's work without interruption.
When a core gets the job of sorting a range in the array it will immediately verify it has permission to spit the work by looking to see if its magnitude is greater than zero and that the work is big enough to justify being split.
If it does have permission to split the work it will collect a sample and find an approximate middle pivot and then split the work into two sets. It will then give one of the sets to another thread along with all relevant information. If it still has permission to split the work further it will continue doing so.
When the work is done it will wait for all the threads it asked for help from to return and then return itself.
This sort has similar advantages to Quick Sort but is much faster on machines with multiple cores.
The following debug messages may help explain the process the sort uses:
When a thread gets part of the task it will find an approximate pivot and then will split the work. As soon as some of the work can be given away, he will pass it on. When the work has followed the magnitude formula enough that it is all about the same size the thread will get to work sorting its section of the code.
It might be helpful to think of it like children trying to share bread. The first child will split the loaf and give about half if it away. Then he will split it again and give away the other half and so on until he has a piece about the same size as everyone else.
Debuging information:
did split in 0: 0 524431 999999
made new thread 2
did split in 0: 0 258968 524431
made new thread 1
did split in 2: 524433 773525 999999
made new thread 3
doing quicksort in 2: 524433 773525
doing quicksort in 0: 0 258968
doing quicksort in 1: 258970 524431
doing quicksort in 3: 773527 999999
Observed Results
This data was created by running may different runs on the same computer.
The sort usually does not achieve hundred percent utilization.
Peaks in the graph represent when the program was doing multi-threading. The Valleys represent just standard single threaded operations.
Conclusion
While experimental this multi threaded quick-sort was able to outperform it's single threaded comparison version.
Implementation
/*
Sorting. This performs multithreaded quicksort
Copyright (C) 2021 Karl Kendall
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#include <Windows.h>
#include <vector>
#include <algorithm>
#include <process.h>
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
bool m_debug = false; // should be off by default;
class Timer
{
LARGE_INTEGER time_begin , time_end;
double frequency;
public:
Timer()
{
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
frequency = (double)freq.QuadPart;
}
void start()
{
QueryPerformanceCounter(&time_begin);
}
double stop()
{
QueryPerformanceCounter(&time_end);
return ((time_end.QuadPart - time_begin.QuadPart)/frequency);
}
operator double()
{
return ((time_end.QuadPart - time_begin.QuadPart)/frequency);
}
};
// full
//Default rand is not providing enough random bits
//This spreads makes it so I get 31 random bits.
unsigned int full()
{
unsigned int full = 0;
full = rand() & 127;
for (int i = 0 ; i < 3; i++)
{
full = full << 8;
//int random = rand();
full = full | (rand() & 255);
}
return full;
}
// myrandom
// simple function needed for random_shuffle to work
// - noticed that random shuffle was not working when trying to debug a failure in a million item vector
int myrandom (unsigned int i) { return full()%i;}
//The very useful threading reference used was
//https://www.bogotobogo.com/cplusplus/multithreading_win32A.php
struct PARAMETERS
{
int magnitude;
int name;
int* array;
int low;
int high;
};
void quickSort(int *array, int low, int high)
{
int i = low;
int j = high;
int pivot = array[(i + j) / 2];
int temp;
while (i <= j)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (j > low)
quickSort(array, low, j);
if (i < high)
quickSort(array, i, high);
}
void splitN(int *array, int low, int& j, int& i, int high, int pivot)
{
i = low;
j = high;
//int pivot = array[(i + j) / 2];
int temp;
while (i <= j)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
}
unsigned int __stdcall total(void* param)
{
PARAMETERS* params = (PARAMETERS*)param;
int magnitude = params->magnitude;
int name = params->name;
int* array = params->array;;
int low = params->low;
int high = params->high;
int selection = 513;
if(magnitude > 5) magnitude = 5; // this is arbitrary.
int i = 0;
HANDLE myhandle[6];
PARAMETERS outparams[6];
// magnitude can only be upto five.
// assert (magnitude <= 6)
//0 = one thread, 1 = two threads, 2 = 4, 3 = 8, 4 = 16, 5 = 32
while( magnitude > 0 && high - low > selection)
{
std::vector<int> candidates;
int temp1, temp2;
for(int j = 0; j < selection; j++)
{
candidates.push_back( array[ low + myrandom(high - low)]);
}
std::sort (candidates.begin(), candidates.end());
int temp = candidates[candidates.size()/2];
splitN (array, low , temp1, temp2, high, candidates[candidates.size()/2]);
if(m_debug) printf("did split %d: %d %d %d\n",name << magnitude , low, temp1, high);
//offload
name = name << 1;
outparams[i].name = name | 1;
magnitude--;
outparams[i].magnitude = magnitude;
outparams[i].array = params->array;;
outparams[i].low = temp2;
outparams[i].high = high;
low = low;
high = temp1;
if(m_debug) printf("made new thread %d\n", outparams[i].name << magnitude);
myhandle[i] = (HANDLE)_beginthreadex(0, 0, &total, &outparams[i], 0, 0);
i++;
}
quickSort(array, low, high);
if(m_debug) printf("doing quicksort in %d: %d %d\n", name, low, high);
//printf( "in name %i\n" , name);
// close all the connected threads
if(i)
{
WaitForMultipleObjects(i, myhandle, true, INFINITE);
for(int j = 0; j < i; j++)
CloseHandle(myhandle[j]);
}
return 0;
}
void splitQuick (vector<int> & arr_total, int magnitude = 3 )
{
HANDLE handleTotal;
PARAMETERS params;
params.magnitude = magnitude;
params.name = 0;
params.array = &arr_total[0];
params.low = 0;
params.high = arr_total.size() - 1;
handleTotal = (HANDLE)_beginthreadex(0, 0, &total, ¶ms, 0, 0);
WaitForSingleObject(handleTotal, INFINITE);
CloseHandle(handleTotal);
return;
}
int main()
{
bool failed = false;
int mysize = 3000000;
Timer timer_total;
Timer timer_quick;
Timer timer_normal;
unsigned int seed;
seed = time(NULL);
srand (seed);
std::vector<int> arr;
for(int i = 0; i < mysize; i++)
{
int temp = i;
arr.push_back(temp);
}
std::random_shuffle ( arr.begin(), arr.end(), myrandom);
std::vector<int> arr_quick = arr;
std::vector<int> arr_total = arr;
std::vector<int> normal_sort = arr;
//m_debug = true;
//if(m_debug) printf("\nworking on magnitude %d\n", i);
//printf("\nworking on magnitude %d\n", i);
timer_total.start();
splitQuick ( arr_total, 3 );
timer_total.stop();
for(int j = 0; j < arr_total.size(); j++)
{
if (arr_total[j] != j)
{
failed = true;
cout << "bad problem happend in total sort, position, " << j << endl;
}
}
timer_quick.start();
quickSort( &arr_quick[0], 0, arr_quick.size() - 1);
timer_quick.stop();
timer_normal.start();
std::sort (normal_sort.begin(), normal_sort.end());
timer_normal.stop();
cout << "size: " << mysize << endl;
cout << "Time taken by quick was : " << timer_quick << endl;
cout << "Time taken by built in sort was : " << timer_normal << endl;
cout << "Time taken by SplitQuick was : " << timer_total << endl;
std::vector<int> debug;
mysize = 1000000;
std::random_shuffle ( debug.begin(), debug.end(), myrandom);
for(int i = 0; i < mysize; i++)
{
int temp = i;
debug.push_back(temp);
}
//cout << "\nDebuging information:" << endl;
//m_debug = true;
//splitQuick ( debug, 2 );
system("pause");
return 0;
}
This code is still experimental and may be updated.
Updated 4/1/2021, added graphs.
Updated 4/16/2021 worked on wording added into section