hschumann2/TempleOS-Source-Code

1 2/*3On an 8-core machine, this takes the top 3-bits4of random numbers and distributes them to the 8 cores5for sorting.  Then, it merge sorts them.6*/7 8#define NUM     10000009 10I64 my_mp_cnt=1<<Bsr(mp_cnt);//Power of 211 12I32 *arg1,*arg2;13I32 *b[my_mp_cnt],bn[my_mp_cnt];14I64 mp_not_done_flags;15 16I64 Compare(I32 *e1,I32 *e2)17{18  return *e1-*e2;19}20 21U0 QSortU32(I32 *base,I64 num)22{//By customizing, we dramatically improve it!23//Cut and paste from QSortI64().24  I64 i;25  I32 *less,*greater,pivot;26  if (num>1) {27    do {28      less=base;29      greater=base+num;30      pivot=base[num/2];31      while (less<greater) {32        if (*less<=pivot)33          less++;34        else {35          greater--;36          SwapU32(less,greater);37        }38      }39      i=less-base;40      if (i==num) {//All less or equ to pivot41 42        //Point greater to first less43        do greater--;44        while (--i && *greater==pivot);45 46        if (i) {47          less=base+num/2; //Pivot was not moved, point to it48          if (less<greater)49            SwapU32(less,greater);50          num=i;51        } else //All equ52          break;53      } else if (i<num/2) {54        QSortU32(base,i);55        num-=i;56        base=greater;57      } else {58        QSortU32(greater,num-i);59        num=i;60      }61    } while (num>1);62  }63}64 65U0 MPSort(I64 dummy=0)66{67  no_warn dummy;68  QSortU32(b[Gs->num],bn[Gs->num]);69  LBtr(&mp_not_done_flags,Gs->num);70}71 72U0 MPRadixSortDemo(I64 dummy=0)73{74  no_warn dummy;75  I64 i,j,k1,k2;76  F64 t0;77  arg1=MAlloc(NUM*sizeof(I32));78  for (i=0;i<NUM;i++)79    arg1[i]=RandI32;80 81  arg2=MAlloc(NUM*sizeof(I32));82 83  "$GREEN$QSort$FG$\n";84  t0=tS;85  MemCpy(arg2,arg1,sizeof(I32)*NUM);86  QSort(arg2,NUM,sizeof(I32),&Compare);87  "Time:%9.6f\n",tS-t0;88  D(arg2+NUM/4);89 90  "$GREEN$QSortU32$FG$\n";91  t0=tS;92  MemCpy(arg2,arg1,sizeof(I32)*NUM);93  QSortU32(arg2,NUM);94  "Time:%9.6f\n",tS-t0;95  D(arg2+NUM/4);96 97  for (i=0;i<my_mp_cnt;i++) {98//We must do full size, just in case.99    //There will be uneven split between cores100    //depending on the distribution of rand numbers.101    b[i]=MAlloc(NUM*sizeof(I32));102    bn[i]=0;103  }104 105  if (my_mp_cnt<2) throw('MultCore');106 107  "$GREEN$MP Radix QSortU32$FG$\n";108  t0=tS;109  k1=32-Bsr(my_mp_cnt);110  k2=my_mp_cnt/2;111  for (i=0;i<NUM;i++) {112    j=arg1[i]>>k1+k2; //This is a preliminary radix sort.113    b[j][bn[j]++]=arg1[i];114  }115  mp_not_done_flags=1<<my_mp_cnt-1;116  for (i=0;i<my_mp_cnt;i++)117    Spawn(&MPSort,NULL,NULL,i);118  while (mp_not_done_flags)119    Yield;120  j=0;121  for (i=0;i<my_mp_cnt;i++) {122    MemCpy(&arg2[j],b[i],bn[i]*sizeof(I32));123    j+=bn[i];124  }125  "Time:%9.6f\n",tS-t0;126  D(arg2+NUM/4);127 128  Free(arg1);129  Free(arg2);130  for (i=0;i<my_mp_cnt;i++)131    Free(b[i]);132}133 134MPRadixSortDemo;135 136/* Results on 8 Cores 3.397GHz Core i7:137QSort138Time: 0.759998139QSortU32140Time: 0.093684141MP Radix QSortU32142Time: 0.045450143*/144