Bug-fix for QSort...

[manor]

Dear address@hidden,

A while back Rick posted a bug-report about the QSort object in Swarm.

I checked, and there was indeed an error in the usage of the Unix qsort
routine which I fixed (the new QSort.h and QSort.m are provided below).
I also added the ability to specify a selector with which to do the
sorting, as suggested by Rick's RSort -> QSort simply assumed the use
of the -compare: method.

(Note by the way that all swarmobjects know how to -compare:, this
method is used by the collections library (for Maps and stuff),
so if you have some ordering/comparison which makes sense for your
objects then you should probably provide it by subclassing the
-compare: method).

In any case, the QSort.h file specifies the following methods:

  +(void) sortObjectsIn: aCollection ;
  +(void) sortObjectsIn: aCollection using: (SEL) aSelector ;

  +(void) sortNumbersIn: aCollection ;
  +(void) sortNumbersIn: aCollection
                  using: (int(*)(const void*,const void*)) comp_fun ;

The fixed version of QSort matches RSort in functionality and far
exceeds it in speed (approx. 660 times faster for 5000 objects on
a Linux box as described below). Note also that the user no longer
needs to provide a Zone for the temporary memory requirements of
the sorting routine: this is because the QSort object uses a special
Zone provided by Roger called the scratchZone (since the user can
not 'walk away' with any of this temporarily allocated memory, it
is reasonably safe to use the scratchZone).

In order to compare QSort and RSort I instrumented the main.m in
Rick's test code:

  http://pscs.physics.lsa.umich.edu//Software/Contents.html

(the file is provided below) and added the following options:

  testsort [-useQSort|-useRSort] [-printCollections] [-numBugs n]
           [-showShuffleTime]

Both for small and moderately sized collections the core Unix
qsort routine seems to compare very well with RSort (approx.
25 times faster for 32 heatbugs, and 660 times faster for 5000
heatbugs):

   > testsort


   ----- Testing Q/R sort on Lists -----

   Sorting took approx. 0 seconds and 7349 microseconds.


   ----- Testing Q/R sort on Arrays -----

   Sorting took approx. 0 seconds and 7748 microseconds.


   ----- Testing user provided selector -----

   Sorting took approx. 0 seconds and 3160 microseconds.


   > testsort -useQSort


   ----- Testing Q/R sort on Lists -----

   Sorting took approx. 0 seconds and 298 microseconds.


   ----- Testing Q/R sort on Arrays -----

   Sorting took approx. 0 seconds and 301 microseconds.


   ----- Testing user provided selector -----

   Sorting took approx. 0 seconds and 287 microseconds.


   > testsort -numBugs 5000


   ----- Testing Q/R sort on Lists -----

   Sorting took approx. 39 seconds and 808595 microseconds.


   ----- Testing Q/R sort on Arrays -----

   Sorting took approx. 47 seconds and 637232 microseconds.


   ----- Testing user provided selector -----

   Sorting took approx. 15 seconds and 587511 microseconds.


   > testsort -numBugs 5000 -useQSort


   ----- Testing Q/R sort on Lists -----

   Sorting took approx. 0 seconds and 74582 microseconds.


   ----- Testing Q/R sort on Arrays -----

   Sorting took approx. 0 seconds and 71184 microseconds.


   ----- Testing user provided selector -----

   Sorting took approx. 0 seconds and 86395 microseconds.

I side-effectually discovered that Shuffler is extremely
inefficient with Lists (it should notice when the argument
is a List and copy it temporarily to an Array, then do its
thing):

  > testsort -numBugs 5000 -showShuffleTime


  ----- Testing Q/R sort on Lists -----

  Shuffle took approx. 24 seconds and 675033 microseconds.
  Sorting took approx. 40 seconds and 251812 microseconds.


  ----- Testing Q/R sort on Arrays -----

  Shuffle took approx. 0 seconds and 32291 microseconds.
  Sorting took approx. 47 seconds and 781052 microseconds.


  ----- Testing user provided selector -----

  Shuffle took approx. 0 seconds and 32838 microseconds.
  Sorting took approx. 15 seconds and 504971 microseconds.

Here are the new source files for QSort (simply place them
in (wherever)/swarm/src/simtools then type make)...

************************* QSort.h  ***************************
// Swarm library. Copyright (C) 1997 Santa Fe Institute.
// This library is distributed without any warranty; without even the
// implied warranty of merchantability or fitness for a particular purpose.
// See file LICENSE for details and terms of copying.

// QSort -> QuickSorts a collection!
//
// The values will appear in ascending order.

#import <swarmobject/SwarmObject.h>

@interface QSort : SwarmObject {
}

+(void) sortObjectsIn: aCollection ;
+(void) sortObjectsIn: aCollection using: (SEL) aSelector ;
+(void) sortNumbersIn: aCollection ;
+(void) sortNumbersIn: aCollection
                using: (int(*)(const void*,const void*)) comp_fun ;

@end
**************************************************************

************************* QSort.m  ***************************
// Swarm library. Copyright (C) 1997 Santa Fe Institute.
// This library is distributed without any warranty; without even the
// implied warranty of merchantability or fitness for a particular purpose.
// See file LICENSE for details and terms of copying.

/*
Name:         QSort.m
Description:  Sort Routine
Library:      simtools
*/

#define __USE_FIXED_PROTOTYPES__  // for gcc headers
#import <stdlib.h>
#import <simtools.h>

@implementation QSort

static id *flat ;
static int size ;
static SEL comp_selector ;

+(void) _flatten_: aCollection {
  id index ;  //atOffset would cause repetitive traversal in lists etc.
  int i ;

  size = [aCollection getCount] ;
  if(size){
    flat = malloc(sizeof(int)*size) ;

    index = [aCollection begin: scratchZone] ;

    for(i = 0 ; i < size ; i++)
      flat[i] = [index next] ;

    [index drop] ;
  }
}

+(void) _unFlatten_: aCollection {
  id index ; //atOffset would cause repetitive traversal in lists etc.
  int i ;

  index = [aCollection begin: scratchZone] ;
  for(i = 0 ; i < size ; i++){
    [index next] ;
    [index put: flat[i]] ;
  }

  [index drop] ;
  free(flat) ;
}

int defaultCmpObjs(id *a,id *b){
  return [*a compare: *b] ;
}

int cmpInts(int *a,int *b){

  if (*a > *b)
    return 1 ;

  if (*a == *b)
    return 0 ;

  return -1 ;
}

int cmpObjs(id *a,id *b){
  return (int) [*a perform: comp_selector with: *b] ;
}

+(void) sortObjectsIn: aCollection {

  [self _flatten_: aCollection] ;

  if(size){
    qsort(flat,size,sizeof(id),
          (int (*)(const void *, const void *)) defaultCmpObjs) ;
    [self _unFlatten_: aCollection] ;
  }
}

+(void) sortNumbersIn: aCollection {

  [self _flatten_: aCollection] ;

  if(size){
    qsort(flat,size,sizeof(int),
          (int (*)(const void *, const void *)) cmpInts) ;
    [self _unFlatten_: aCollection] ;
  }
}

+(void) sortObjectsIn: aCollection using: (SEL) aSelector {

  [self _flatten_: aCollection] ;

  if(size){
    comp_selector = aSelector ;
    qsort(flat,size,sizeof(id),
          (int (*)(const void *, const void *)) cmpObjs) ;
    [self _unFlatten_: aCollection] ;
  }

}

+(void) sortNumbersIn: aCollection
                using: (int(*)(const void*,const void*)) comp_fun {

  [self _flatten_: aCollection] ;

  if(size){
    qsort(flat,size,sizeof(int),
          (int (*)(const void *, const void *)) comp_fun) ;
    [self _unFlatten_: aCollection] ;
  }

}

@end
**************************************************************

Here is the main.m file to be used in conjunction with Rick's code:

************************** main.m ****************************
#import <stdlib.h>
#import <simtools.h>
#import <swarmobject.h>
#import <collections.h>

#import "Heatbug.h"
#import "Shuffler.h"
#import "RSort.h"

#include <sys/time.h>
#include <unistd.h>

id bugList, bugArray;
void printBugList ( char *s, id list );

int main(int argc, char ** argv) {
  int i ;
  id  bug, shuffler;
  int useRSort = 1 ;
  int printCollections = 0 ;
  int numBugs = 32 ;
  int showShuffleTime = 0 ;

  struct timeval before, after ;

  initSwarm(argc, argv);

  for(i = 1 ; i < argc ; i++){

    if(!strcmp(argv[i],"-useRSort")){
      useRSort = 1 ;
      continue ;
    }

    if(!strcmp(argv[i],"-useQSort")){
      useRSort = 0 ;
      continue ;
    }

    if(!strcmp(argv[i],"-printCollections")){
      printCollections = 1 ;
      continue ;
    }

    if(!strcmp(argv[i],"-showShuffleTime")){
      showShuffleTime = 1 ;
      continue ;
    }

    if(!strcmp(argv[i],"-numBugs")){
      numBugs = atoi(argv[++i]) ;
      continue ;
    }

  fprintf(stderr,"  %s: Unknown command-line option '%s'\n",argv[0],argv[i]) ;
    fprintf(stderr,
      "  %s [-useQSort|-useRSort] [-printCollections] [-numBugs n]\n\
           [-showShuffleTime]\n",
      argv[0]);
    exit(-1) ;

  }

  bugList = [List create: globalZone];
  bugArray = [Array create: globalZone setCount: numBugs];

  for ( i = 0; i < numBugs; ++i ) {
    bug = [Heatbug createBegin: globalZone];
    [bug setIdealTemperature: i % 5];
    [bug setOutputHeat: numBugs-i];
    bug = [bug createEnd];
    [bugList addLast: bug];
    [bugArray atOffset: i put: bug];
  }

  shuffler = [Shuffler createBegin: globalZone];
  [shuffler setUniformRandom: uniformDblRand];
  shuffler = [shuffler createEnd];

  fprintf(stderr,"\n\n----- Testing Q/R sort on Lists -----\n\n");

  gettimeofday(&before,NULL) ;

  [shuffler shuffleList: bugList Num: [bugList getCount]];

  gettimeofday(&after,NULL) ;

  if(showShuffleTime){
    if(after.tv_usec > before.tv_usec){
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
    } else {
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec - 1,
            1000000 + after.tv_usec - before.tv_usec) ;
    }
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the shuffle:",bugList);
    fprintf(stderr,"\n") ;
  } ;

  gettimeofday(&before,NULL) ;

  if(useRSort){
    [RSort sortObjectsIn: bugList
                   usingCompare: M(compareID:) inZone: globalZone];
  } else {
    [QSort sortObjectsIn: bugList] ;
  }

  gettimeofday(&after,NULL) ;

  if(after.tv_usec > before.tv_usec){
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
  } else {
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec - 1,
          1000000 + after.tv_usec - before.tv_usec) ;
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the sort:",bugList);
    fprintf(stderr,"\n") ;
  } ;



  fprintf(stderr,"\n\n----- Testing Q/R sort on Arrays -----\n\n");

  gettimeofday(&before,NULL) ;

  [shuffler shuffleList: bugArray Num: [bugArray getCount]];

  gettimeofday(&after,NULL) ;

  if(showShuffleTime){
    if(after.tv_usec > before.tv_usec){
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
    } else {
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec - 1,
            1000000 + after.tv_usec - before.tv_usec) ;
    }
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the shuffle:",bugArray);
    fprintf(stderr,"\n") ;
  } ;

  gettimeofday(&before,NULL) ;

  if(useRSort){
    [RSort sortObjectsIn: bugArray
                   usingCompare: M(compareID:) inZone: globalZone];
  } else  {
    [QSort sortObjectsIn: bugArray] ;
  }

  gettimeofday(&after,NULL) ;

  if(after.tv_usec > before.tv_usec){
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
  } else {
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec - 1,
          1000000 + after.tv_usec - before.tv_usec) ;
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the sort:",bugArray);
    fprintf(stderr,"\n") ;
  } ;


  fprintf(stderr,"\n\n----- Testing user provided selector -----\n\n");

  gettimeofday(&before,NULL) ;

  [shuffler shuffleList: bugArray Num: [bugArray getCount]];

  gettimeofday(&after,NULL) ;

  if(showShuffleTime){
    if(after.tv_usec > before.tv_usec){
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
    } else {
      fprintf(stderr,"Shuffle took approx. %d seconds and %d microseconds.\n",
            after.tv_sec - before.tv_sec - 1,
            1000000 + after.tv_usec - before.tv_usec) ;
    }
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the shuffle:",bugArray);
    fprintf(stderr,"\n") ;
  } ;

  gettimeofday(&before,NULL) ;

  if(useRSort){
    [RSort sortObjectsIn: bugArray
                 usingCompare: M(compareIdealTemperature:) inZone: globalZone];
  } else {
    [QSort sortObjectsIn: bugArray using: M(compareIdealTemperature:)] ;
  }

  gettimeofday(&after,NULL) ;

  if(after.tv_usec > before.tv_usec){
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec, after.tv_usec - before.tv_usec) ;
  } else {
    fprintf(stderr,"Sorting took approx. %d seconds and %d microseconds.\n",
          after.tv_sec - before.tv_sec - 1,
          1000000 + after.tv_usec - before.tv_usec) ;
  }

  if(printCollections){
    fprintf(stderr,"\n") ;
    printBugList("After the sort:",bugArray);
    fprintf(stderr,"\n") ;
  } ;

  fprintf(stderr,"\n\n") ;

  return 0;
}

void printBugList ( char *s, id list ) {
        int i;
        int m = [list getCount];
        fprintf( stderr, s );
        for ( i = 0; i < m; ++i ) {
                fprintf(stderr,"  %d (iT=%d)", [[list atOffset: i] getID],
                                [[list atOffset: i] getIdealTemperature] );
        }
        fprintf(stderr, "\n" );
}

**************************************************************

Regards,

Manor.

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.
                  ==================================