Stack vs. heap storage

Question

This program sorts input lines lexicographically, and I've come to this exercise in K&R:

Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?

The original program is the same, just it used alloc to maintain storage for lines.

So I edited it this way:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines, char buf[]);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

#define MAXSIZE 10000
int main(int argc, char *argv[])
{
     int nlines;
     char buf[MAXSIZE];

     if((nlines = readlines(lineptr, MAXLINES, buf)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          getchar();
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          getchar();
          return 1;
     }
}

#define MAXLEN 1000
int getline(char *, int);

int readlines(char *lineptr[], int maxlines, char buf[])
{
    int len, nlines;
    char *p = buf;
    char line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || MAXSIZE + buf - p < len)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
            p+=len;
       }

    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines-- > 0)
         printf("%s\n", *lineptr++);
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

void swap(char *v[], int i, int j)
{
     char *temp;
     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
}

void qsort(char *v[], int left, int right) {
    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

Is this what the author wanted, or did I do it wrong?

Also, measuring time diffrence, is it correct to just start the clock at the begining of the main and then stop it after reading lines is over, and compare the time taken?

Answer 1

It's hard to say without seeing the original code, but it looks correct.

For timing it, it depends on what type of clock you use. If all you do is read clock ticks from the global clock then this method is bad. If you are reading from the process's clock, then it will work.

edit: you might not see a great timing difference. However, try putting the array in a different function (let's name it foo()) and calling readlines from that function using the local array in foo(). Call foo() 5,000 times. Try the old method with alloc() 5,000 times.

This will likely yield different run-times because alloc() requires system calls, which are slow.

edit: this pseudo-c will tell you how to time dynamic memory allocation vs. stack allocation. This complicated by the fact that your process will likely block until the system gives it the memory it wants, so you may have to tinker with different clocks to get a better picture.

You'll want to compile this with no optimizations.

void call1()
{
    char* i;
    i = (char*)malloc(1000);
    //we should free(), but this would add timing overhead.
}

void call2()
{
   char x[1000];
}


int main()
 {
   int i=0;

   timer_start();
   for(i = 0; i < 5000; i++)
       call1();
   timer_stop();

   report_time();

   timer_start();
   for(i = 0; i < 5000; i++)
       call2();
    timer_stop();

  report_time();  
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINES 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

char *alloc(int n);

#define MAXSIZE 10000
int main(int argc, char *argv[])
{
     int nlines;

     if((nlines = readlines(lineptr, MAXLINES)) >= 0) {
          qsort(lineptr, 0, nlines-1);
          writelines(lineptr, nlines);
          getchar();
          return 0;
     } 
     else {
          printf("error: input too big to sort\n");
          getchar();
          return 1;
     }

}


#define MAXLEN 1000
int getline(char *, int);

int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p;
    char line[MAXLEN];

    nlines = 0;
    while((len = getline(line, MAXLEN)) > 0)
       if(nlines >= maxlines || (p = alloc(len)) == NULL)
          return -1;
       else {
            line[len-1] = '\0';
            strcpy(p, line);
            lineptr[nlines++] = p;
       }

    return nlines;
}

void writelines(char *lineptr[], int nlines)
{
     while(nlines-- > 0)
         printf("%s\n", *lineptr++);
}

#define MAXALLOC 5000
char allocbuf[MAXALLOC];
char *allocp = allocbuf;

char *alloc(int n)
{
     if(allocbuf + MAXALLOC - allocp >= n) {
        allocp += n;
        return allocp - n;
     }
     else
         return 0;
}

int getline(char s[], int lim)
{
  int c, i;

  for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
    s[i] = c;                                                         
  if (c == '\n') {
    s[i++] = c;   
  }
  s[i] = '\0';
  return i;
}

void swap(char *v[], int i, int j)
{
     char *temp;

     temp = v[i];
     v[i] = v[j];
     v[j] = temp;
}

void qsort(char *v[], int left, int right) {

    int i, last;

    if(left >= right) 
       return;

    swap(v, left, (left+right)/2);
    last = left;

    for(i = left + 1; i <= right; i++)
      if(strcmp(v[i], v[left]) < 0)
         swap(v, ++last, i);

    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

This is the original code.