What are the other options of faster IO in C

Question

I implemented merge sort and used it as a solution for this codechef problem. Here are the submissions. The code is placed below.

The problem that I think is causing slow execution is that my IO is slow in the main function. I know the number of elements that are inputted so there has to be some faster way to read input instead of the way that I am doing.

Are there faster IO methods instead of the ones that I am using in the main function? I have heard about using buffers, fgets and sscanf but I don't know if they are faster.

Any code examples would be helpful.

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

void merge_parts(int arr[], int length)
{
    int *ans;
    int i, j, k;
    int temp = length/2;

    ans = malloc(sizeof(int) * length);

    //This while and next if-else puts the merged array into temporary array ans
    for (j = temp, i = k = 0; (i < temp && j < length); k++){
        ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    if(i >= temp){
        while(j < length){
            ans[k++] = arr[j++];
        }
    }
    else{
        while(i < temp){
            ans[k++] = arr[i++];
        }
    }

    //This while loops puts array ans into original array arr
    for(i = 0; i < length; i++){
        arr[i] = ans[i];
    }

    free(ans);
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        merge_sort(&arr[0], (length/2));
        merge_sort(&arr[length/2], (length - length/2));
        merge_parts(arr, length);
    }
}

int main()
{
    int length;
    int *arr;
    scanf("%d", &length);
    arr = malloc(sizeof(int) * length);

    for(int i = 0; i < length; i++)
        scanf("%d", &arr[i]);

    merge_sort(arr, length);

    for(int i = 0; i < length; i++)
        printf("%d ", arr[i]);

    free(arr);
    return 0;
}

EDIT3:

[I deleted EDIT AND EDIT2 as they were no longer relevant]

merge_sort algorithm that I am using

void merge_parts(int arr[], int length)
{
    int ans[length];
    int i, j, k;
    int temp = length/2;
    //This while and next if-else puts the merged array into temporary array ans
    for (j = temp, i = k = 0; (i < temp && j < length); k++){
        ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
    }

    if(i >= temp){
        while(j < length){
            ans[k++] = arr[j++];
        }
    }
    else{
        while(i < temp){
            ans[k++] = arr[i++];
        }
    }

    //This while loops puts array ans into original array arr
    for(i = 0; i < length; i++){
        arr[i] = ans[i];
    }
}

void merge_sort(int arr[], int length)
{
    if(length > 1)
    {
        merge_sort(&arr[0], (length/2));
        merge_sort(&arr[length/2], (length - length/2));
        merge_parts(arr, length);
    }
}

merge1.c

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>

#define SORTING_ALGO_CALL merge_sort

char buffer[4096];
int bufcount;
int bufpos;

int get_next_char()
{
    if (!bufcount)
    {
        bufcount = fread(buffer, 1, 4096, stdin);
        bufpos = 0;
        if (!bufcount){
            return EOF;
        }
    }
    bufcount--;
    return buffer[bufpos++];
}

int readnum()
{
    int res = 0;
    char ch;
    do
    {
        ch = get_next_char();
    } while (!isdigit(ch) && ch != EOF);

    if (ch == EOF){
            return 0xbaadbeef;    // Don't expect this to happen.
    }

    do
    {
        res = (res * 10) + ch - '0';
        ch = get_next_char();
    } while(isdigit(ch));
    return res;
}


int main()
{
    clock_t time1, time2;
    double time_taken;

//FIRST READ
    time1 = clock();

    int length = readnum();
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        length = readnum();
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading length = %f\n", time_taken);
    time1 = clock();

    int *arr;
    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nAllocating array = %f\n", time_taken);
    time1 = clock();

    for (int i = 0; i < length; i++){
        arr[i] = readnum();
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading array = %f\n", time_taken);
    time1 = clock();

    SORTING_ALGO_CALL(arr, length);

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nSorting array = %f\n", time_taken);
    time1 = clock();
/*
    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }
*/
//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nPrinting Sorted array = %f\n", time_taken);
    time1 = clock();

    free(arr);

//SECOND READ, PRINT
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nFreeing array = %f\n", time_taken);

    return 0;
}

merge2.c

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

#define SORTING_ALGO_CALL merge_sort

int main()
{
    clock_t time1, time2;
    double time_taken;

//FIRST READ
    time1 = clock();

    int length;
    scanf("%d", &length);
    while (length < 1)
    {
        printf("\nYou entered length = %d\n", length);
        printf("\nEnter a positive length: ");
        scanf("%d", &length);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading length = %f\n", time_taken);
    time1 = clock();

    int *arr;
    if ((arr = malloc(sizeof(int) * length)) == NULL)
    {
        perror("The following error occurred");
        exit(-1);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nAllocating array = %f\n", time_taken);
    time1 = clock();

    for (int i = 0; i < length; i++){
        scanf("%d", &arr[i]);
    }

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nReading array = %f\n", time_taken);
    time1 = clock();

    SORTING_ALGO_CALL(arr, length);

//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nSorting array = %f\n", time_taken);
    time1 = clock();
/*
    for (int i = 0; i < length; i++){
        printf("%d ", arr[i]);
    }
*/
//SECOND READ, PRINT AND NEXT FIRST READ
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nPrinting Sorted array = %f\n", time_taken);
    time1 = clock();

    free(arr);

//SECOND READ, PRINT
    time2 = clock();
    time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
    printf("\nFreeing array = %f\n", time_taken);

    return 0;
}

Both merge1.c and merge2.c contain the 2 functions of merge-sort.

The file that I am using for generating worst-case(decreasing order) input for the 2 files.

#include<stdio.h>

int main()
{
    int j = 100000;
    printf("%d\n", j);
    for(int i = j; i > 0; i--)
        printf("%d\n", i);

    return 0;
}

Timing result for merge1.c

Reading length = 23.055000

Allocating array = 0.000000

Reading array = 0.010000

Sorting array = 0.020000

Printing Sorted array = 0.000000

Freeing array = 0.000000

Timing result for merge2.c

Reading length = 22.763000

Allocating array = 0.000000

Reading array = 0.020000

Sorting array = 0.020000

Printing Sorted array = 0.000000

Freeing array = 0.000000

Answer 1

You can almost certainly beat scanf by writing your own little function to read numbers.

If all numbers are decimal and separated by something that isn't a digit, this would work:

 char buffer[4096]; 
 int bufcount;
 int bufpos;

 int get_next_char()
 {
     if (!bufcount)
     {
         bufcount = fread(buffer, 1, 4096, stdin);
         bufpos = 0;
         if (!bufcount){
            return EOF;
         }
     }
     bufcount--;
     return buffer[bufpos++]; 
 }


 int is_digit(int ch)
 {
     if (ch >= '0' && ch <= '9')
        return 1;
     return 0;
 }

 int readnum()
 {
     int res = 0;
     int ch;
     do
     {
         ch = get_next_char();
     } while(!is_digit(ch) && ch != EOF);
     if (ch == EOF)
     {
        return 0xbaadbeef;    // Don't expect this to happen. 
     }
     do
     {
         res = (res * 10) + (ch - '0');
         ch = get_next_char();
     } while(is_digit(ch));
     return res;
 }

The code in scanf is a lot more complicated than this, and is highly likely to call getc or fgetc, which is a bit less efficient than the above code would be. However, it's worth measuring exactly where you are spending time. Print the time for each function as part of your output.

Answer 2

I would supplement Mats' answer by, rather than using stdin, having a file name as input. Then open the file (in binary format if on Windows). Get the file length, malloc a big-enough buffer, read the entire file into it, and close the file. Then I would parse using a character pointer into the buffer. That way, getting the next character doesn't require a function call. That's hard to beat for speed.

The code for parsing an integer is:

num = 0;
while(isdigit(*pc)){
  num = num*10 + (*pc++ - '0');
}

Answer 3

• In optimization problem the rule of thumb is the best. Try to get numerics value of time spent in each step. Loading - sorting - etc... You can use a profiler for that (like gprof).

• To faster your IO you should consider doing less call to scanf. As you have the number of scanf require you could design a better algorithm for this specific part.

• Scanf do a lot of thing, parse the first arg, then read the byte and convert it to the format. If we want to go faster, we will use 'data problem' to skip some steps. First, we know that we are just using number define on N (math). Second, we know that every bytes are numbers or separators. We can use this.

So we use the read() system call that can read some byte from a file descriptor. The file descriptor for standard input change between operating system, but it is often 0.

The macro algorithm could be :

index = 0
buffer = new array[10000];
numberOfByteRead = 1
while there is byte that have been read at last call of read.
      numberOfByteRead = read said 10000 byte to buffer;
      parse the buffer
;;

parse(buffer,numberOfByteRead)
for all true byte in buffer :
   switch (buffer[0])
      case '0': { the mathematical operation on arr[index] that fit for '0'; break;  }
      case '1': { ... break;}
      case ' ': {index++; break;}
;;

Not a really fun part to code, but faster than scanf. Larger value that 10000, will reduce IO time, but increase memory. You have to balance.

Answer 4

static char buff[8*1000000];
int i, length, blen;
int *ap, *p;
int n = 0;
char ch, *cp = buff;

scanf("%d%*c", &length);
p = ap = malloc(sizeof(*ap) * length);

blen = fread(buff, 1, 8*1000000, stdin);
while(blen--){
    if(isdigit(ch=*cp++)){
        n = n * 10 + ch - '0';
    } else {
        *p++ = n;
        n = 0;
    }
}