Skip to content

Instantly share code, notes, and snippets.

@nishidy
Last active December 10, 2016 08:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nishidy/97a4a3faea7413da7fdd7592d37a614d to your computer and use it in GitHub Desktop.
Save nishidy/97a4a3faea7413da7fdd7592d37a614d to your computer and use it in GitHub Desktop.
Merge sort with multi-threaded (without lock)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <pthread.h>
#include <errno.h>
unsigned long mem_size;
unsigned int malloc_cnt;
void* _malloc(size_t size){
mem_size += size;
malloc_cnt ++;
return malloc(size);
}
void print(int* a, int n){
int i=0;
printf("[");
for(i=0;i<n;i++){
if(i>0) printf(",");
printf("%d",*(a+i));
}
printf("]\n");
}
double print_time(struct timeval *s, struct timeval *e){
int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
return (double)(ei-si)/1000.0;
}
int* sample(int n){
int* sample_data = (int*)malloc(sizeof(int)*n);
int i=0;
int j=0;
while(j<n){
if(rand()%2){
*(sample_data+j) = i;
j++;
}
if(rand()%100>0){
i++;
}
}
return sample_data;
}
int* shuffle(int* data, int n, int* random_data){
memcpy(random_data,data,sizeof(int)*n);
int s = rand()%n;
int i, d, tmp;
for(i=0;i<n;i++){
d = rand()%n;
tmp = *(random_data+d);
*(random_data+d) = *(random_data+s);
*(random_data+s) = tmp;
s = d;
}
return random_data;
}
int assert(int* a, int* b, int n){
if(memcmp(a,b,n)){
return 0;
}else{
return 1;
}
}
typedef struct {
int *data;
int n;
} merge_arg;
int th_count=0;
int th_max_count=2;
void* merge_sort(void* _merge_arg){
merge_arg *arg = (merge_arg*)_merge_arg;
if(arg->n<=1) return NULL;
int *total = (int*)_malloc(sizeof(int)*arg->n);
int half = arg->n/2;
int *left = total;
int *right = left+half;
int i;
for(i=0;i<half;i++){
*(left+i) = *(arg->data+i);
}
for(i=half;i<arg->n;i++){
*(right+i-half) = *(arg->data+i);
}
int left_p=-1, right_p=-1;
pthread_t *left_merge, *right_merge;
merge_arg *left_arg = (merge_arg*)_malloc(sizeof(merge_arg));
merge_arg *right_arg = (merge_arg*)_malloc(sizeof(merge_arg));
left_arg->data = left;
left_arg->n = half;
right_arg->data = right;
right_arg->n = arg->n-half;
if(th_count<th_max_count){
left_merge = (pthread_t*)_malloc(sizeof(pthread_t));
if((left_p=pthread_create(left_merge,NULL,merge_sort,(void*)left_arg))==0)
th_count++;
else
merge_sort(left_arg);
}else{
merge_sort(left_arg);
}
if(th_count<th_max_count){
right_merge = (pthread_t*)_malloc(sizeof(pthread_t));
if((right_p=pthread_create(right_merge,NULL,merge_sort,(void*)right_arg))==0)
th_count++;
else
merge_sort(right_arg);
}else{
merge_sort(right_arg);
}
if(left_p==0)
pthread_join(*left_merge,NULL);
if(right_p==0)
pthread_join(*right_merge,NULL);
int left_idx=0;
int right_idx=0;
while(left_idx<half || right_idx<arg->n-half){
if(left_idx == half){
*(arg->data+left_idx+right_idx) = *(right+right_idx);
right_idx++;
}else if(right_idx == arg->n-half){
*(arg->data+left_idx+right_idx) = *(left+left_idx);
left_idx++;
}else if( *(left+left_idx) < *(right+right_idx) ){
*(arg->data+left_idx+right_idx) = *(left+left_idx);
left_idx++;
}else{
*(arg->data+left_idx+right_idx) = *(right+right_idx);
right_idx++;
}
}
free(total);
if(left_p==0){
free(left_merge);
free(left_arg);
}
if(right_p==0){
free(right_merge);
free(right_arg);
}
return NULL;
}
void do_assert(int* sample_data, int* sorted_data, int n){
if(assert(sample_data,sorted_data,n)){
printf("Sorted check OK.\n");
}else{
print(sample_data,n>100?100:n);
print(sorted_data,n>100?100:n);
}
}
int main(int argc, char *argv[]){
if(argc<2){ printf("Give # of samples.\n"); exit(1); }
if(argc>2)
th_max_count = atoi(argv[2]);
int n = atoi(argv[1]);
int *sample_data;
struct timeval s, e;
//srand((unsigned) time(NULL));
srand(100);
sample_data = sample(n);
int* random_data = (int*)malloc(sizeof(int)*n);
shuffle(sample_data,n,random_data);
mem_size = 0;
malloc_cnt = 0;
merge_arg* arg = (merge_arg*)malloc(sizeof(merge_arg));
arg->data = random_data;
arg->n = n;
gettimeofday(&s,NULL);
merge_sort(arg);
gettimeofday(&e,NULL);
printf("Merge sort with multi-thread: %.2lf sec.\n",print_time(&s,&e));
do_assert(sample_data,random_data,n);
printf("mem_size = %luMB, malloc_cnt = %d\n",mem_size/(1024*1024),malloc_cnt);
printf("# of threads = %d\n",th_count);
return 0;
}
@nishidy
Copy link
Author

nishidy commented Dec 10, 2016

$ gcc -W -O3 thread_merge_sort.c -o thread_merge_sort
$ ./thread_merge_sort 100000000
Merge sort with multi-thread: 24.32 sec.
Sorted check OK.
mem_size = 10722MB, malloc_cnt = 227099604
# of threads = 2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment