Create quicksort.hs

haskell quicksort with mutable arrays.

Sorting 10M ints timing compared with C:

 $ time cat tsort.txt | ./quicksort2 +RTS  -sstderr > /tmp/h1.txt
  12,472,761,688 bytes allocated in the heap
     188,757,008 bytes copied during GC
      80,053,224 bytes maximum residency (4 sample(s))
       9,644,184 bytes maximum slop
             159 MB total memory in use (3 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     23665 colls,     0 par    0.29s    0.29s     0.0000s    0.0001s
  Gen  1         4 colls,     0 par    0.01s    0.01s     0.0037s    0.0142s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    5.50s  (  5.50s elapsed)
  GC      time    0.31s  (  0.31s elapsed)
  EXIT    time    0.01s  (  0.01s elapsed)
  Total   time    5.85s  (  5.82s elapsed)

  %GC     time       5.2%  (5.3% elapsed)

  Alloc rate    2,266,595,984 bytes per MUT second

  Productivity  94.7% of total user, 95.2% of total elapsed


real    0m5.846s
user    0m5.574s
sys     0m0.348s
 $ time cat tsort.txt | ./qsort +RTS -sstderr > /tmp/c1.txt

real    0m5.297s
user    0m5.118s
sys     0m0.297s
 $ diff -ubp /tmp/c1.txt /tmp/h1.txt
 $ wc -l /tmp/h1.txt
10000000 /tmp/h1.txt

--

C version use bultin qsort, full source code:

#include <stdlib.h>
#include <stdio.h>

unsigned getuint(void)
{
  unsigned r = 0;
  unsigned bits = 0;
  int c;

  while(1) {
    c = fgetc_unlocked(stdin);
    if (c == ' ' || c == '\n') {
      if (bits > 0)
        break;
    } else if (c == EOF) {
      break;
    } else {
      r = 10*r + (c - '0');
      ++bits;
    }
  }
  return r;
}

int cmp(const void* p, const void* q)
{
        unsigned a = *(unsigned*)p;
        unsigned b = *(unsigned*)q;

        if (a < b) return -1;
        else if (a == b) return 0;
        else return 1;
}

int process(void)
{
        unsigned nr, i;
        unsigned* arr;
        unsigned c = 0;
        const unsigned bufsiz=65536;
        char buffer[bufsiz+128];

        i = scanf("%u\n", &nr);

        arr = malloc( (1+nr) * sizeof(unsigned));

        for (i = 0; i < nr; i++) {
                arr[i] = getuint();
        }

        qsort(arr, nr, sizeof(unsigned), cmp);

        for (i = 0; i < nr; i++) {
                c += snprintf(buffer + c, (bufsiz + 128) - c, "%u\n", arr[i]);

                if (c >= bufsiz) {
                 fwrite(buffer, 1, c, stdout);
                 c = 0;
                }
        }

        if (c > 0) {
                fwrite(buffer, 1, c, stdout);
        }
        fflush(stdout);

        return 0;
}

int main(int argc, char* argv[])
{
        process();

        return 0;
}