My Parallel Sort Library was updated to version 3.6

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From	Horizon68 <horizon@horizon.com>
Newsgroups	comp.programming
Subject	My Parallel Sort Library was updated to version 3.6
Date	Sun, 24 Mar 2019 06:34:44 -0700
Organization	A noiseless patient Spider
Lines	56
Message-ID	<q7811k$5a0$4@dont-email.me> (permalink)
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	7bit
Injection-Date	Sun, 24 Mar 2019 13:34:44 -0000 (UTC)
Injection-Info	reader02.eternal-september.org; posting-host="adbb471bd2eabba4f05d3a11d30a2804"; logging-data="5440"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/ptX4hPwXBG+tN1k3cHh1dEWzAwvMRol4="
User-Agent	Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.0
Cancel-Lock	sha1:btNYcu37j5ZXJo9ZeVPuzM+RM8Y=
Content-Language	en-US
X-Mozilla-News-Host	news://news.eternal-september.org:119
Xref	csiph.com comp.programming:9832

Show key headers only | View raw

Hello,


My Parallel Sort Library was updated to version 3.6

I have enhanced it more, and now it scales more and it is
faster.

Description:

My Parallel Sort Library that supports Parallel Quicksort, Parallel 
HeapSort and Parallel MergeSort on Multicores systems.

Parallel Sort Library uses my Thread Pool Engine and sort many array 
parts - of your array - in parallel using Quicksort or HeapSort or 
MergeSort and after that it finally merge them - with the merge() 
procedure -

In the previous parallelsort version i have parallelized only the sort 
part, but in this new parallelsort version i have parallelized also the 
merge procedure part and it gives better performance.

My new parallel sort algorithm has become more cache-aware, and i have 
done some benchmarks with my new parallel algorithm and it has given up 
to 5X scalability on a Quadcore when sorting strings, other than that i 
have cleaned more the code and i think my parallel Sort library has 
become a more professional and industrial parallel Sort library , you 
can be confident cause i have tested it thoroughly and no bugs have 
showed , so i hope you will be happy with my new Parallel Sort library.

My algorithm of Parallel merge is O(log(min(|A|,|B|))), where |A| is the 
size of A, since the binary search is performed within the smaller array 
and is O(lgN).

The idea:

Let's assume we want to merge sorted arrays X and Y. Select X[m] median 
element in X. Elements in X[ .. m-1] are less than or equal to X[m]. 
Using binary search find index k of the first element in Y greater than 
X[m]. Thus Y[ .. k-1] are less than or equal to X[m] as well. Elements 
in X[m+1..] are greater than or equal to X[m] and Y[k .. ] are greater. 
So merge(X, Y) can be defined as concat(merge(X[ .. m-1], Y[ .. k-1]), 
X[m], merge(X[m+1.. ], Y[k .. ])) now we can recursively in parallel do 
merge(X[ .. m-1], Y[ .. k-1]) and merge(X[m+1 .. ], Y[k .. ]) and then 
concat results.


You can download it from:

https://sites.google.com/site/scalable68/parallel-sort-library



Thank you,
Amine Moulay Ramdane.

Back to comp.programming | Previous | Next | Find similar | Unroll thread

Thread

My Parallel Sort Library was updated to version 3.6 Horizon68 <horizon@horizon.com> - 2019-03-24 06:34 -0700

csiph-web