Changeset 2287


Ignore:
Timestamp:
09/05/11 18:30:08 (13 years ago)
Author:
KohjiNakamura
Message:

modernQSort bug fix

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/parallel/src/TableTraverse.cpp

    r2284 r2287  
    7373#endif
    7474
     75#ifdef HAVE_QSORT_R
     76
     77static int compWithComparator(void *arg, const void *a, const void *b)
     78{
     79        return ((asap::Comparator *)arg)->compare(a, b);
     80}
     81
     82#else
     83
    7584static inline void swap_(char *a, char *b, size_t size)
    7685{
     
    91100}
    92101
    93 static void sort_(char *left, char *right, const size_t size,
     102// returning NULL means, already sorted.
     103static inline char *quickFindPivot(char *const left, char *const right,
     104                                   const size_t size, asap::Comparator *comp)
     105{
     106  char *const m = &left[(((right - left) / size) / 2 ) * size];
     107  char *result = NULL;
     108  if (left == m) { // This means there are at most 2 elements.
     109    int diff = (left == right) ? 0 : comp->compare(left, right);
     110    if (diff > 0) {
     111      swap_(left, right, size);
     112    }
     113    if (diff != 0) {
     114      return right;
     115    }
     116    return result;
     117  }
     118
     119  int diff = comp->compare(left, m);
     120  if (diff > 0) {
     121    swap_(left, m, size);
     122  }
     123  int diff2 = comp->compare(m, right);
     124  if (diff == 0 && diff2 == 0) {
     125    return result;
     126  }
     127  result = m;
     128  if (diff2 > 0) {
     129    swap_(right, m, size);
     130    int diff3 = comp->compare(left, m);
     131    if (diff3 > 0) {
     132      swap_(left, m, size);
     133    } else if (diff3 == 0) {
     134      result = right;
     135    }
     136  } else if (diff == 0) {
     137    result = right;
     138  }
     139  return result;
     140}
     141
     142static inline char *findPivot(char *const start, char *const end,
     143                              size_t size, asap::Comparator *comp)
     144{
     145  char *result = quickFindPivot(start, end, size, comp);
     146  if (result || &start[2*size] >= end) {
     147    return result;
     148  }
     149
     150  for (char *pivot = start + size; pivot <= end; pivot += size) {
     151    int diff = comp->compare(start, pivot);
     152    if (diff < 0) {
     153      return pivot;
     154    } else if (diff > 0) {
     155      swap_(start, pivot, size);
     156      return pivot;
     157    }
     158  }
     159  return NULL; // all values are same.
     160}
     161
     162static void sort_(char *const left, char *const right, const size_t size,
    94163                  asap::Comparator *comp, int level)
    95164{
    96   const size_t len = (right - left) / size;
    97   if (len < 2) {
     165  char *const m = findPivot(left, right, size, comp);
     166  if (m == NULL) {
    98167    return;
    99168  }
    100   size_t mid = len >> 1;
    101169  char *l = left;
    102   char *r = right - size;
     170  char *r = right;
    103171  char pivot[size]  __attribute__ ((aligned (16)));
    104   cpy(pivot, &left[mid*size], size);
     172  cpy(pivot, m, size);
    105173  while (true) {
    106174    while (l < r && comp->compare(l, pivot) < 0) {
    107175      l += size;
    108176    }
    109     while (l < r && comp->compare(r, pivot) > 0) {
     177    while (l < r && comp->compare(pivot, r) <= 0) {
    110178      r -= size;
    111         }
     179    }
    112180    if (l >= r) {
    113181      break;
     
    117185    r -= size;
    118186  }
    119   sort_(left, l, size, comp, level + 1);
     187  if (l == r && comp->compare(l, pivot) < 0) {
     188    l += size;
     189  }
     190  sort_(left, l - size, size, comp, level + 1);
    120191  sort_(l, right, size, comp, level + 1);
    121192}
     193
     194#endif
    122195
    123196static inline void modernQSort(void *base, size_t elements, size_t size,
    124197                               asap::Comparator *comp)
    125198{
    126   sort_((char *)base, &((char *)base)[elements * size], size, comp, 0);
     199  if (elements > 1) {
     200#ifdef HAVE_QSORT_R
     201    qsort_r(base, elements, size, comp, compWithComparator);
     202#else
     203    sort_((char *)base, &((char *)base)[(elements - 1) * size], size, comp, 0);
     204#endif
     205  }
    127206}
    128207
     
    224303}
    225304
    226 #if 0
     305#if 0 && TIMING
     306#include <assert.h>
     307
     308#define elementsof(x) (sizeof(x)/sizeof(*x))
     309
    227310using namespace asap ;
    228311
    229 class MyComp: public Comparator {
     312class IntComp: public Comparator {
    230313public:
    231314  virtual int compare(const void *a, const void *b) {
     
    234317};
    235318
     319static int compare(const void *a, const void *b) {
     320  return (*(int*)a) - (*(int*)b);
     321}
     322
    236323int main()
    237324{
     325  IntComp myComp;
    238326  srand((int)currenttime());
    239   int x[100];
    240   printf("init\n");
    241   for (int i = 0; i < 100; i++) {
    242     x[i] = rand() % 100;
    243   }
    244   MyComp myComp;
    245   printf("sorting\n");
     327  const size_t N = 1024*1024*100;
     328  int *x = new int[N];
     329  int xx[] = {
     330    5, 3,0,  1, 2,4, 4, 4
     331  };
     332#if 0
     333  {
     334    int x[] = {1};
     335    char *p = findPivot((char *)x, (char *)&x[0], sizeof(x[0]), &myComp);
     336    assert(p == NULL);
     337  }
     338  {
     339    int x[] = {1, 1};
     340    char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp);
     341    assert(p == NULL);
     342  }
     343  {
     344    int x[] = {2, 1};
     345    char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp);
     346    assert((int*)p == &x[1] && x[0] == 1 && x[1] == 2);
     347  }
     348  {
     349    int x[] = {1, 2};
     350    char *p = findPivot((char *)x, (char *)&x[1], sizeof(x[0]), &myComp);
     351    assert((int*)p == &x[1] && x[0] == 1 && x[1] == 2);
     352  }
     353  {
     354    int x[] = {1, 1, 1};
     355    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     356    assert(p == NULL);
     357  }
     358  {
     359    int x[] = {2, 1, 1};
     360    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     361    assert((int*)p == &x[2]);
     362    assert(x[0] == 1 && x[1] == 1 && x[2] == 2);
     363  }
     364  {
     365    int x[] = {1, 2, 1};
     366    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     367    assert((int*)p == &x[2]);
     368    assert(x[0] == 1 && x[1] == 1 && x[2] == 2);
     369  }
     370  {
     371    int x[] = {1, 1, 2};
     372    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     373    assert((int*)p == &x[2]);
     374    assert(x[0] == 1 && x[1] == 1 && x[2] == 2);
     375  }
     376  {
     377    int x[] = {2, 2, 1};
     378    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     379    assert((int*)p == &x[1]);
     380    assert(x[0] == 1 && x[1] == 2 && x[2] == 2);
     381  }
     382  {
     383    int x[] = {2, 1, 2};
     384    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     385    assert((int*)p == &x[1]);
     386    assert(x[0] == 1 && x[1] == 2 && x[2] == 2);
     387  }
     388  {
     389    int x[] = {1, 2, 2};
     390    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     391    assert((int*)p == &x[1]);
     392    assert(x[0] == 1 && x[1] == 2 && x[2] == 2);
     393  }
     394  {
     395    int x[] = {1, 2, 3};
     396    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     397    assert((int*)p == &x[1]);
     398    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     399  }
     400  {
     401    int x[] = {2, 1, 3};
     402    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     403    assert((int*)p == &x[1]);
     404    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     405  }
     406  {
     407    int x[] = {1, 3, 2};
     408    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     409    assert((int*)p == &x[1]);
     410    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     411  }
     412  {
     413    int x[] = {3, 1, 2};
     414    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     415    assert((int*)p == &x[1]);
     416    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     417  }
     418  {
     419    int x[] = {3, 2, 1};
     420    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     421    assert((int*)p == &x[1]);
     422    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     423  }
     424  {
     425    int x[] = {2, 3, 1};
     426    char *p = findPivot((char *)x, (char *)&x[2], sizeof(x[0]), &myComp);
     427    assert((int*)p == &x[1]);
     428    assert(x[0] == 1 && x[1] == 2 && x[2] == 3);
     429  }
     430  {
     431    int x[] = {36, 39, 42, 41, 36};
     432    char *p = findPivot((char *)x, (char *)&x[4], sizeof(x[0]), &myComp);
     433    assert((int*)p == &x[4]);
     434    assert(x[4] == 42);
     435  }
     436
     437  //assert(("assert enabled: OK", false));
     438  modernQSort(x, 8, sizeof(x[0]), &myComp);
     439  for (int i = 0; i < 8; i++) {
     440    fprintf(stderr, "%d\n", x[i]);
     441  }
     442#endif
     443  fprintf(stderr, "init\n");
     444  for (int i = 0; i < N; i++) {
     445    x[i] = rand();
     446  }
     447  fprintf(stderr, "sorting\n");
    246448  modernQSort(x, 1, sizeof(x[0]), &myComp);
    247449  modernQSort(x, 2, sizeof(x[0]), &myComp);
    248450  modernQSort(x, 3, sizeof(x[0]), &myComp);
    249   modernQSort(x, 100, sizeof(x[0]), &myComp);
    250   for (int i = 0; i < 100; i++) {
     451  if (! getenv("QSORT")) {
     452    double _s = currenttime();
     453    modernQSort(x, N, sizeof(x[0]), &myComp);
     454    double _e = currenttime();
     455    fprintf(stderr, "modernSorted %.3f\n", _e - _s);
     456  } else {
     457    double _s = currenttime();
     458    qsort(x, N, sizeof(x[0]), compare);
     459    double _e = currenttime();
     460    fprintf(stderr, "qsorted %.3f\n", _e - _s);
     461  }
     462  fprintf(stderr, "outputting\n");
     463  for (int i = 0; i < N; i++) {
    251464    printf("%d\n", x[i]);
    252465  }
    253 }
    254 #endif
     466  delete[] x;
     467}
     468#endif
Note: See TracChangeset for help on using the changeset viewer.