Judy arrays much faster than standard sort?

[Leszek Dubiel]

I have found that Judy arrays are faster than standard "sort" program 
about 10 times. This is a little bit strange, because I expected sort to 
be fastest tool ever.

Heres is my session:

   address@hidden wc input
   1000000 1000000 5659335 input

   address@hidden time ./judy < input > output_judy
   The JudySL array used 360076 bytes of memory

   real    0m0.603s
   user    0m0.528s
   sys    0m0.028s
   address@hidden time sort < input > output_sort

   real    0m6.026s
   user    0m5.912s
   sys    0m0.072s

   address@hidden diff output_*


Judy arrays are described at http://judy.sourceforge.net/, and program 
"judy" is compiled from example shown on that site:


#include <stdio.h>
#include <Judy.h>

#define MAXLINE 1000000                 // max string (line) length

uint8_t   Index[MAXLINE];               // string to insert

int     // Usage:  JudySort < file_to_sort
main()
{
   Pvoid_t   PJArray = (PWord_t)NULL;  // Judy array.
   PWord_t   PValue;                   // Judy array element.
   Word_t    Bytes;                    // size of JudySL array.

   while (fgets(Index, MAXLINE, stdin) != (char *)NULL)
   {
       JSLI(PValue, PJArray, Index);   // store string into array
       if (PValue == PJERR)            // if out of memory?
       {                               // so do something
           printf("Malloc failed -- get more ram\n");
           exit(1);
       }
       ++(*PValue);                    // count instances of string
   }
   Index[0] = '\0';                    // start with smallest string.
   JSLF(PValue, PJArray, Index);       // get first string
   while (PValue != NULL)
   {
       while ((*PValue)--)             // print duplicates
           printf("%s", Index);
       JSLN(PValue, PJArray, Index);   // get next string
   }
   JSLFA(Bytes, PJArray);              // free array

   fprintf(stderr, "The JudySL array used %lu bytes of memory\n", Bytes);
   return (0);
}