|
Hi,
I made a small program which sorts a Vector of 100000 ints.
I use a quicksort , not the recursive one.
With the single thread version I takes about 22s to complete.
-now the problem and the question:
I have written a second version which
1. first make a partitioning
2. start an independent thread on eatch subpartition = 2Threads
So the sorting continues on 2 separate threads with no locks or anythig to block;
I got almost the same time when running.
Why happens to run in same interval of time.
Will Windows7 be very smart to optimize the code to run on multiple cores even if it is a single thread?
I have a x6 Cpu.
here is the sample code (test code)
class VectorSafeConcurency
{
int[] V;
const int sizeV = 100000;
void push2(Stack<int> s, int a, int b)
{
s.Push(b);
s.Push(a);
}
public VectorSafeConcurency()
{
V= new int[sizeV];
int value= sizeV;
for (int i = 0; i < sizeV; ++i)
V[i] = value--;
}
void exchange(ref int x, ref int y)
{
int temp= x;
x= y;
y= temp;
}
int partition(int[] A, int l, int r)
{
int i = l - 1;
int j = r;
int v= A[r];
for(;;)
{
while(A[++i] <v);
while (v < A[--j]) if (j == l) break;
if (i >= j) break;
exchange(ref A[i], ref A[j]);
}
exchange(ref A[i], ref A[r]);
return i;
}
struct ThData
{
public int[] A;
public int l;
public int r;
public ThData(int []a, int i, int j)
{
A = a; l = i; r = j;
}
}
void thWorkerParititoner(object data)
{
int[] A = ((ThData)data).A;
int l = ((ThData)data).l;
int r = ((ThData)data).r;
quicksort(A, l, r);
}
void StartQuicksort(int[] A, int l, int r)
{
if (r <= l) return;
int i = partition(A, l, r);
Thread t1 = new Thread(thWorkerParititoner);
t1.Start(new ThData (A, l, i-1));
Thread t2 = new Thread(thWorkerParititoner);
t2.Start(new ThData(A, i+1, r));
}
void quicksort(int[] A, int l, int r)
{
Stack<int> Indexes = new Stack<int>();
push2(Indexes, l, r);
while (Indexes.Count > 0)
{
l = Indexes.Pop(); r = Indexes.Pop();
if (r <= l) continue;
int i = partition(V, l, r);
push2(Indexes, l, i - 1);
push2(Indexes, i + 1, r);
}
}
public void StartSort()
{
quicksort(V, 0, V.Length - 1);
int d = 1;
}
}
modified 18-Jan-13 6:59am.
|
|
|
|
|
22 seconds to sort 100,000 integers?? Are you running this on an Atari 800? That's horrible performance for a Quicksort.
I've got a Mergesort implementation in my toolbox that'll sort 10,000,000 integers in less than 12 seconds - single threaded.
Windows will not automatically rework your code to run in on multiple cores. No O/S will do that. YOU have to do that my rewriting your code. I'd concentrate on reworking your implementation to get better performance on a single thread first before you start to worry about how you're going to multithread this. Multithreading a poor implementation doesn't get you anything but more threads running poorly.
|
|
|
|
|
Hi,
This quick sort couldn't be so bad. Ok, it is not an optimized QuickSort.
I think it depends also on the input data you provide. I have used other sorting algorithms with these data set and I get comparative results.
But still I don't have any answer here.
modified 18-Jan-13 11:12am.
|
|
|
|
|
George Nistor wrote: This quick sort couldn't be so bad
Oh yeah?? Quick sort normally has about 95% of the performance of Merge sort, given a proper implementation. Try recoding to use arrays only and skill all the stack collection garbage.
|
|
|
|
|
I think the stack operations are slowing your algorithm. Quicksort only needs a simple array.
The generic operations that are "array-like" will reallocate a NEW array and copy all the elements to this array when the old array isn't long enough to hold a new element. This gives O(n^2) performance, which is slow. (Quicksort should be O(n log n)).
Using multiple threads to speed Quicksort is a good idea because the partitioning lets the threads work independently, without requiring synchronization. You just have to make sure your basic operations aren't wasting time.
|
|
|
|
|
thanks Alan, I have realized after I looked on the
Stack<t>(Int32) Constructor.
I fixed the problem and now I was able to run it 2 times faster, in 9-10 seconds for the same dataset.
|
|
|
|
|
That's still horrible performance for Quick sort.
|
|
|
|
|
Considering a Quick sort should run about 1,500 times faster than what you're now reporting, you've got major problems. 10,000 integers should take less than 0.01 seconds on todays hardware - single threaded.
Try reading Scalable Multithreaded Programming with Thread Pools[^] for a threaded Quick sort example.
|
|
|
|
|
I use as test a vector with 100 000 ints. It is ordered in Descending order.
(another problem I have choosed partition element at one end, result in a small partition on a Descending order data set )
I have tried an optimized Insertion and it sorts it in 20s. c++
I think I test the worst case scenario which is N2 for both inserion and quicksort.
In average cases it works super fast, in less than a second;
I got like you with 10 mils of ints around 3 sec.
int[] V;
const int sizeV = 10000000;
Random rnd = new Random();
for (int i = 0; i < sizeV; ++i)
V[i] = rnd.Next(0, 9999999);
modified 18-Jan-13 16:37pm.
|
|
|
|
|
OK, Solved.
It works really fast even without a selection first.
(I can sort 50 millions of ints in 15 seconds)
|
|
|
|