Fast Input/Output in C

      Certain problems on competitive programming sites such as Codechef, SPOJ etc. specify warnings  such as : Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed). Usually all such problems can be solved by using the scanf and printf library functions. But there do exist methods which are much faster than these which yield a better execution time. An example is the getchar_unlocked() function. It can be argued that scanf provides a lot of security checks that should be there for any robust program facing real world inputs, but in the world of competitive programing, where the input is properly defined, we can safely ignore such checks for getting around tighter timing constraints and getting a much lesser execution time.

The getchar_unlocked() method :

int getchar_unlocked(void);

      The function reads the next character from stdin stream  and  returns  it  as  an unsigned char cast to an int, or EOF on end of file or error. The "_unlocked" differentiates it from the getchar() function in the sense that getchar_unlocked() does not use locking (it  do  not  set  locks itself, and does not test for the presence of locks set by others) and hence is thread-unsafe, but it works perfectly fine in single-threaded programs (like the ones submitted to SPOJ/Codechef). However it is much faster than both scanf() and getchar(), and thus can provide considerable improvement in execution time.

      Since the getchar_unlocked() function returns the next character from the stdin stream, we will have to write our own code to process different kinds of input. The following code is capable of accepting positive integers.

int scan_positive_int(int *a)
{
    int x=0;
    register int c=getchar_unlocked();
    for(; c>47 && c<58 ; c = getchar_unlocked())
    {
        x = (x<<1) + (x<<3) + c - 48;
    }
    *a=x;
}

Explanation :

1. The keyword register hints to compiler that a given variable can be put in a register. It’s compiler’s choice to put it in a register or not. Since register are faster to access than memory we can use them for taking input.

2. The expression "(x<<1)+(x<<3)" is equivalent to "x*10" . This is because of the following :
x*10 = x*(2+8)
        = (x*2)+(x*8)
        = (x<<1)+(x<<3)   (Because left shift of x by n is equivalent to x*2^n, so x<<3 is equivalent to x*8 and x<<1 is equivalent to x*2)
   
3. The statement x = (x<<1) + (x<<3) + c – 48; thus is equivalent to x = x * 10 + c -48 ; It will append the input character to the end of the integer x. (Eg. Suppose x is 2 and the input character is 1, then the statement becomes x = 2*10 + 1, thus giving x the value 21).

4.  The for loop after this takes a single character as input from the stdin stream and checks whether this character is an integer, and if it is then it appends the character to x, thus forming the number. The loop exits whenever a non-digit character is encountered.

Similar functions can be written for accepting integers and strings. A function that is capable of handling both positive and negative integers is given below :

int scan_int(int *a)
{
    int x=0,negative=0;
    register int c=getchar_unlocked();
    if(c=='-')
    {
        negative=1;
    c=getchar_unlocked();
    }    
    for(; c>47 && c<58 ; c = getchar_unlocked())
    {
        x = (x<<1) + (x<<3) + c - 48;
    }
    *a=(negative==1)?-(x):x;
}

The performance of above code can be tested with the INTEST problem on SPOJ. A code with scanf() statements for input yielded an execution time of 5.53 sec while the solution containing the above method using getchar_unlocked() for input took only 0.86 seconds.

The respective codes are :

1. Using scanf() : Exec time 5.53 sec

#include<stdio.h>
int main()
{
    int n,k,t,count=0;
    scanf("%d",&n);
    scanf("%d",&k);
    while(n>0)
    {
        n--;
        scanf("%d",&t);
        if(t%k==0)
            count++;
    }
    printf("%d",count);
    return 0;
}

2. Using getchar_unlocked() : Exec time 0.86 sec

#include<stdio.h>
int scan_positive_int(int *a)
{
        int x=0;
        register int c=getchar_unlocked();
        for(; c>47 && c<58 ; c = getchar_unlocked())
        {
                x = (x<<1) + (x<<3) + c - 48;
        }
        *a=x;
}
int main()
{
    int n,k,t,count=0;
    scan_positive_int(&n);
    scan_positive_int(&k);
    while(n>0)
    {
        n--;
        scan_positive_int(&t);
        if(t%k==0)
            count++;
    }
    printf("%d",count);
    return 0;
}

      I have tested the above codes on Ubuntu. On windows getchar_unlocked() will have to replaced with getchar() to make the above codes work. The getchar() function is slower than getchar_unlocked() because it provides the additional security of being threadsafe.So if you are using windows then you can test your code using getchar() and replace it with getchar_unlocked() before submitting it to Codechef/SPOJ.