home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / net / fastsort < prev    next >
Internet Message Format  |  1989-03-08  |  9KB
  1. From tmdonahu@athena.mit.edu Tue Mar  7 14:36:58 1989
  2. Path: uunet!labrea!bloom-beacon!athena.mit.edu!tmdonahu
  3. From: tmdonahu@athena.mit.edu (Terence M Donahue)
  4. Newsgroups: alt.sources
  5. Subject: A faster sort
  6. Message-ID: <9667@bloom-beacon.MIT.EDU>
  7. Date: 7 Mar 89 19:36:58 GMT
  8. Sender: daemon@bloom-beacon.MIT.EDU
  9. Reply-To: tmdonahu@athena.mit.edu (Terence M Donahue)
  10. Distribution: usa
  11. Organization: Massachusetts Institute of Technology
  12. Lines: 304
  13.  
  14.  
  15. I was curious about all of these "better faster stronger" sorting
  16. programs, so I decided to try them out myself using a Vaxstation 2000
  17. running Unix.
  18.  
  19. Functionality
  20. -------------
  21.  
  22. The man page for sort(1) says that it merges all the
  23. files together and sorts the entire mess.  Both fastsort and
  24. fastersort simply sort each file separately.
  25.  
  26. In addition, fastsort produced different output from sort and
  27. fastersort, as reported by diff.
  28.  
  29. Improvements
  30. ------------
  31.  
  32.     Use fputs() and putc() to output the sorted lines instead of fprintf()
  33.  
  34.     inline the strcmp function into compare().
  35.  
  36.     Ideally the compare() function should be built in to the qsort
  37.     routine, eliminating the significant amount of procedure call
  38.     overhead in the program.  This was not done in fastestsort
  39.     because my homemade quicksort is significantly slower than the
  40.     qsort in the C library here.  The qsort sources are not freely
  41.     distributable.  The inlining of the compare function would
  42.     result in a significant speed improvement.
  43.  
  44. Speed
  45. -----
  46.  
  47. All programs were compiled with gcc with optimization on. 
  48.  
  49. termcap is the first 1000 lines of /etc/termcap, a file with long lines
  50. dict is the first 10000 lines of /usr/dict/words in reverse order, a
  51. file with short lines.
  52. All times are in seconds
  53.  
  54. Method        termcap            dict
  55. ------        -------            ----
  56. sort         1.6u 0.5s 0:03        11.7u 0.4s 0:13
  57. fastsort    13.3u 1.2s 0:15     22.0u 1.9s 0:25
  58. fastersort     3.0u 0.2s 0:03        36.4u 0.4s 0:38
  59. fastestsort     1.2u 0.2s 0:01        13.1u 0.5s 0:14
  60.  
  61. So good old sort beats out fastsort and fastersort.  The latest version,
  62. fastestsort, does about as well as sort.
  63.  
  64.  
  65. Profiling
  66. ---------
  67.  
  68. fastsort on termcap
  69.   %   cumulative   self              self     total           
  70.  time   seconds   seconds    calls  ms/call  ms/call  name    
  71.  65.3       9.05     9.05        1  9050.00  9522.34  _qst [4]
  72.  10.3      10.48     1.43        1  1430.00 11010.00  _qsort [3]
  73.   7.6      11.54     1.06                             mcount (30)
  74.   5.8      12.34     0.80     2001     0.40     0.46  _fgets [5]
  75.   4.6      12.98     0.64     1007     0.64     0.68  __doprnt [7]
  76.   3.8      13.51     0.53    11095     0.05     0.05  _strcmp [8]
  77.  
  78. fastsort on dict
  79.   %   cumulative   self              self     total           
  80.  time   seconds   seconds    calls  ms/call  ms/call  name    
  81.  39.4      10.20    10.20                             mcount (25)
  82.  24.3      16.48     6.28   125441     0.05     0.05  _strcmp [5]
  83.  13.2      19.91     3.43        1  3430.00  9209.27  _qst [4]
  84.  10.2      22.54     2.63    10007     0.26     0.27  __doprnt [7]
  85.   4.8      23.77     1.23    20001     0.06     0.07  _fgets [8]
  86.   3.4      24.66     0.89        1   890.00 15690.00  _main [2]
  87.  
  88. fastersort on termcap
  89.   %   cumulative   self              self     total           
  90.  time   seconds   seconds    calls  ms/call  ms/call  name    
  91.  35.7       1.27     1.27                             mcount (21)
  92.  16.0       1.84     0.57     1000     0.57     0.62  __doprnt [7]
  93.  14.0       2.34     0.50    10900     0.05     0.05  _strcmp [8]
  94.   9.3       2.67     0.33    10900     0.03     0.08  _compare [5]
  95.   8.4       2.97     0.30        1   300.00  1037.79  _qst [4]
  96.   8.1       3.26     0.29        1   290.00  2290.00  _main [2]
  97.  
  98. fastersort on dict
  99.   %   cumulative   self              self     total           
  100.  time   seconds   seconds    calls  ms/call  ms/call  name    
  101.  47.6      23.96    23.96                             mcount (23)
  102.  21.0      34.54    10.58   218572     0.05     0.05  _strcmp [6]
  103.  12.5      40.83     6.29   218572     0.03     0.08  _compare [5]
  104.   9.9      45.82     4.99        1  4990.00 21027.27  _qst [4]
  105.  
  106. fastestsort on termcap
  107.   %   cumulative   self              self     total           
  108.  time   seconds   seconds    calls  ms/call  ms/call  name    
  109.  27.1       0.61     0.61                             mcount (22)
  110.  19.1       1.04     0.43    10900     0.04     0.04  _compare [5]
  111.  18.7       1.46     0.42        1   420.00   802.23  _qst [4]
  112.  10.7       1.70     0.24        1   240.00  1640.00  _main [2]
  113.   8.9       1.90     0.20        1   200.00   200.00  _read [6]
  114.   4.9       2.01     0.11     1000     0.11     0.17  _fputs [7]
  115.   4.0       2.10     0.09        6    15.00    15.00  _write [9]
  116.   2.2       2.15     0.05        2    25.00    25.00  _open [10]
  117.   2.2       2.20     0.05        1    50.00   900.00  _qsort [3]
  118.  
  119. fastestsort on dict
  120.   %   cumulative   self              self     total           
  121.  time   seconds   seconds    calls  ms/call  ms/call  name    
  122.  44.9      12.34    12.34                             mcount (21)
  123.  29.2      20.38     8.04   218572     0.04     0.04  _compare [5]
  124.  17.8      25.26     4.88        1  4880.00 12523.14  _qst [4]
  125.   2.8      26.02     0.76        1   760.00 15150.00  _main [2]
  126.   2.2      26.62     0.60    10000     0.06     0.07  _fputs [6]
  127.   1.0      26.89     0.27        1   270.00 13190.00  _qsort [3]
  128.  
  129. Fastestsort
  130. -----------
  131.  
  132. --------------------------- fastestsort.c ------------------------------
  133. /*
  134. *
  135. * fastsort - sort a file in place - fast!
  136. *
  137. * Written 03/01/89 by Edwin R. Carp
  138. *
  139. * Copyright 1989 by Edwin R. Carp
  140. *
  141. *
  142. * John F. Haugh II, modified 3/3/89
  143. *
  144. * Completely rehacked to remove the two pass garbage
  145. * and quit pushing strings about in memory.  Reads
  146. * entire file in with one call, splits into lines and
  147. * saves pointers to each.  Then sorts pointers and
  148. * outputs lines.
  149. *
  150. * No big deal ...
  151. *
  152. *
  153. * Terence M. Donahue, modified 3/4/89
  154. *
  155. * Uses fputs() instead of fprintf() to output the sorted lines
  156. * Inlined the string compare into the compare() function.
  157. *
  158. * It is now about as fast as sort on my machine...
  159. *
  160. * There is a slow homemade quicksort routine #ifdef'ed out.
  161. * Once it is fast enough, compile -DHOMEMADE to have it replace qsort
  162. */
  163.  
  164. #include <stdio.h>
  165. #include <sys/types.h>
  166. #include <sys/stat.h>
  167. #include <fcntl.h>
  168.  
  169. nomem (s)
  170. char    *s;
  171. {
  172.     fprintf (stderr, "Can't get memory for %s\n", s);
  173.     exit (1);
  174. }
  175.  
  176. #ifdef HOMEMADE
  177. /*
  178. ** This homemade quicksort is currently much slower than qsort,
  179. ** especially for large arrays.
  180. **
  181. ** Future improvements:
  182. **
  183. **    inline the strcmps
  184. **    do the recursive sort call on the smaller partition
  185. **    switch to an insertion sort on partitions smaller than 8 elements
  186. */
  187.  
  188. #define exch(x,y) (temp = x, x = y, y = temp)
  189.  
  190. void sort(v,left,right)
  191.      char *v[];
  192.      int left,right;
  193. {
  194.   int i, last;
  195.   char *temp;
  196.  
  197.   while (left < right) {
  198.     /* Determine pivot by taking the median of left, middle, and right */
  199.     i = (left+right)>>1;
  200.     if (strcmp(v[left],v[right]) > 0) {
  201.       if (strcmp(v[left],v[i]) < 0)       i = left;
  202.       else if (strcmp(v[right],v[i]) > 0) i = right;
  203.     }
  204.     else {
  205.       if (strcmp(v[left],v[i]) > 0)       i = left;
  206.       else if (strcmp(v[right],v[i]) < 0) i = right;
  207.     }
  208.  
  209.     exch(v[left],v[i]);
  210.  
  211.     last = left;
  212.     for (i=left+1; i <= right; i++)
  213.       if (strcmp(v[i],v[left]) < 0)
  214.     if (i != ++last) { exch(v[last],v[i]); }
  215.  
  216.     exch(v[left],v[last]);
  217.  
  218.     if (left < last-1) sort(v, left, last-1);
  219.     left = last+1;
  220.   }
  221. }
  222.  
  223. #else
  224.  
  225. compare(sp1,sp2)
  226.      char **sp1,**sp2;
  227. {
  228.   char *s1,*s2;
  229.  
  230.   s1 = *sp1; s2 = *sp2;
  231.   while(*s1 == *s2++)
  232.     if(*s1++ == '\0') return 0;
  233.   return(*s1 - *--s2);
  234. }
  235. #endif
  236.  
  237. main(argc, argv)
  238. int argc;
  239. char **argv;
  240. {
  241.     int    fd;
  242.     char    *malloc ();
  243.     char    *realloc ();
  244.     char    *cp;
  245.     char    *buf;
  246.     char    **lines;
  247.     int    cnt, cur, max;
  248.     struct    stat    statbuf;
  249.     FILE    *fp;
  250.  
  251.     if (argc < 2) {
  252.         fprintf (stderr, "usage: fastsort files ...\n");
  253.         exit (1);
  254.     }
  255.     while (*++argv) {
  256.         if (stat (*argv, &statbuf)) {
  257.             perror(*argv);
  258.             continue;
  259.         }
  260.         if (! (buf = malloc ((unsigned) statbuf.st_size + 1)))
  261.             nomem (*argv);
  262.  
  263.         if ((fd = open (*argv, O_RDONLY)) < 0) {
  264.             perror (*argv);
  265.             continue;
  266.         }
  267.         if (read (fd, buf, statbuf.st_size) != statbuf.st_size) {
  268.             perror (*argv);
  269.             free (buf);
  270.             continue;
  271.         }
  272.         close (fd);
  273.  
  274.         *(cp = &buf[statbuf.st_size]) = '\0';
  275.  
  276.         cur = 0;
  277.         max = 10;
  278.  
  279.         if (! (lines = (char **) malloc (sizeof (char *) * max)))
  280.             nomem (*argv);
  281.  
  282.         while (--cp != buf) {
  283.             if (*cp == '\n') {
  284.                 *cp = '\0';
  285.                 if (cur == max)
  286.                     if (! (lines = (char **) realloc (lines, sizeof (char *) * (max += 10))))
  287.                         nomem (*argv);
  288.                 lines[cur++] = cp + 1;
  289.             }
  290.         }
  291.         lines[0] = buf;        /* fix our earlier mistake :-) */
  292.  
  293. #ifdef HOMEMADE
  294.         sort (lines, 0, cur-1);
  295. #else
  296.         qsort ((char *) lines, cur, sizeof (char *), compare);
  297. #endif
  298.  
  299.         if (! (fp = fopen (*argv, "w"))) {
  300.             perror (*argv);
  301.             continue;
  302.         }
  303.         for (max = cur, cur = 0;cur < max;cur++) {
  304.             fputs (lines[cur], fp);
  305.             putc ('\n', fp);
  306.         }
  307.  
  308.         fflush (fp);
  309.         fclose (fp);
  310.         free (lines);
  311.         free (buf);
  312.     }
  313.     exit (0);
  314. }
  315. ------------------------- end of fastestsort.c ---------------------------
  316.  
  317. Terry Donahue                  tmdonahu@athena.mit.edu
  318.  
  319.  
  320.