Fast Processing of Text Files in C

Question

I've written some C code (not a C pro 'though), which is supposed to be as fast as possible. The algorithm is finished and I'm pleased with it's speed. But before it starts, I have to get some information from a text file, which is way to slow.

Right now the processing of the text file needs about 3 seconds for bigger files, while the same file is processed by Java code in less than 1 second, because Java has premade methods like readline() in it's framwork which alone contains more than 100 lines of pure code.

Is there any comparable Framework for C? I couldn't find anything on Google, because no matter how I rephrased my search requests I would get nothing, but tutorials on how to user fopen()...

If you wonder why I don't use Java then: The algorithm itself is way faster in C.

Here is the code I use in C. What needs to be done is to process a .cnf file in DINMACS format.

    while ((temp = fgetc(fp)) != EOF)
    {   
        if (temp == 'c')
        {
            //evtl. im Labor auf 13 ändern
            while ((temp =fgetc(fp)) != 10 && temp != EOF);
        }

        if (temp == 'p')
        {
            while ((temp =fgetc(fp)) < '0' ||  temp > '9');

            while (temp != 32)
            {
                variablen= (variablen * 10) + (temp - '0');
                temp=fgetc(fp);

            }

            while ((temp =fgetc(fp)) < '0' ||  temp > '9');

            while ((temp!= 32) && (temp != 10 ) )
            {
                klauseln= (klauseln * 10) + (temp - '0');
                temp=fgetc(fp);
            }

            while ((temp != 10) && (temp != EOF))
            {
                temp=fgetc(fp);
            }

            break;
        }
    }

    phi = (int *) malloc(klauseln * variablen * sizeof(int));

    int zaehler2 = 0;
    for (int j = 0; j < klauseln; ++j)
    {
        for (int i = 0; i < variablen; ++i)
        {
            phi[zaehler2++] = 0;
        }
    }

    int zeile = 0;

    while ((temp = fgetc(fp)) != EOF)
    {   
        if (temp == 'c')
        {
            while ((temp =fgetc(fp)) != 10 && temp != EOF);
        }
        else
        {
            while (temp != '0')
            {                        
                    int neg = 1;
                    int wert = 0;

                    while (temp != 32)
                    {
                        if (temp == '-') 
                        {
                            neg = -1;
                        }
                        else
                        {
                            wert = (wert * 10) + (temp - '0');
                        }

                        temp = fgetc(fp);
                    }
                    phi[wert - 1 + zeile] = neg;
                    temp = fgetc(fp);    
            }

            zeile = zeile + variablen;
            temp = fgetc(fp);    
        }
    }

Answer 1

To speed up code, you first check to see if there's a better algorithm.

There is nothing algorithmically wrong. You're processing each character, in sequence, without backtracking, so it's O(n), which is as good as you could expect.

So all you can do is try to find faster ways to do what you're already doing. To do that, you need to profile the code. You can't know where the time is being spent otherwise. If you don't know the most biggest bottleneck, you'll waste a lot of time trying to optimize the wrong spot.

It's possible that reading the file character by character is slow, and you might be better off reading the file in large chunks and then process the characters from memory. But it's also possible that fread is doing that for you behind the scenes, so it might not buy you anything.

Reducing the number of tests (comparisons) might help. For example, when you check for 10 (linefeed) or EOF, you have to do two tests for every character. If you read the file into memory first, you could append a sentinel 10 to the end of the buffer, and that loop would then have to check only for linefeeds.

Answer 2

I ran a test that reads chars from a file using fgetc(), another using getc() ("e8" method) and a buffered version that collects the chars from a local buffer.

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

#define BUFLEN  1024

FILE *fp;
char fname[] = "test.txt";
int bufsize, bufind;

int getachar() {
    static unsigned char buf[BUFLEN];
    if (bufind >= bufsize) {
        bufsize = fread(buf, sizeof(char), BUFLEN, fp);
        if (bufsize == 0)
            return -1;
        bufind = 0;
    }
    return buf[bufind++];
}

void WVmethod (void) {
    int temp, count=0;
    bufsize = bufind = 0;
    if ((fp = fopen(fname, "rt")) == NULL)
        return;
    while ((temp = getachar()) != -1) count++;
    fclose(fp);
    printf ("WV method read %d chars. ", count);
}

void OPmethod (void) {
    int temp, count=0;
    if ((fp = fopen(fname, "rt")) == NULL)
        return;
    while ((temp = fgetc(fp)) != EOF) count++;
    fclose(fp);
    printf ("OP method read %d chars. ", count);
}

void e8method (void) {
    int temp, count=0;
    if ((fp = fopen(fname, "rt")) == NULL)
        return;
    while ((temp = getc(fp)) != EOF) count++;
    fclose(fp);
    printf ("e8 method read %d chars. ", count);
}

int main()
{
    clock_t start, elapsed;
    int loop;

    for (loop=0; loop<3; loop++) {
        start = clock();
        WVmethod();
        elapsed = clock() - start;
        printf ("Clock ticks = %d\n", (int)elapsed);

        start = clock();
        OPmethod();
        elapsed = clock() - start;
        printf ("Clock ticks = %d\n", (int)elapsed);

        start = clock();
        e8method();
        elapsed = clock() - start;
        printf ("Clock ticks = %d\n", (int)elapsed);

        printf ("\n");
    }
    return 0;
}

Program output:

WV method read 24494400 chars. Clock ticks = 265
OP method read 24494400 chars. Clock ticks = 1575
e8 method read 24494400 chars. Clock ticks = 1544

WV method read 24494400 chars. Clock ticks = 266
OP method read 24494400 chars. Clock ticks = 1591
e8 method read 24494400 chars. Clock ticks = 1544

WV method read 24494400 chars. Clock ticks = 265
OP method read 24494400 chars. Clock ticks = 1607
e8 method read 24494400 chars. Clock ticks = 1545

Answer 3

My guess is that you are looking for basic functions to read file and that reading characters one by one is not the direction you are looking for.

There are many functions to read and handle string in c. In stdio.h are some functions that could help you :

• char * fgets ( char * str, int num, FILE * stream ) : read characters until end of line or end of file, if num is large enough.
• int sscanf ( const char * s, const char * format, ...); : reads formatted input. For instance fscanf(line,"%d",&nb); will read an integer and place it into nb. It is not possible to call sscanf many times on the same string. But a bypass is to use strtok() of string.h to split a string using space " " as a separator.

Here a sample code doing the job :

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


#define MAX_LINE_SIZE 1000
#define MAX_SEQ_SIZE 100

int main()
{
    FILE * pFile;
    char line [MAX_LINE_SIZE];
    int nbvar,nbclauses;
    int* array=NULL;
    int i=0;int j;
    pFile = fopen ("example.txt" , "r");
    if (pFile == NULL){ perror ("Error opening file");}
    else {
        while (fgets(line, MAX_LINE_SIZE, pFile) != NULL){
            printf("%s",line);fflush(stdout);
            // parsing the line
            if(line[0]!='c' && line[0]!='\0'){
                if(line[0]=='p'){
                    sscanf(line,"%*s%*s%d%d",&nbvar,&nbclauses);
                    array=malloc(MAX_SEQ_SIZE*nbclauses*sizeof(int));
                }else{
                    char * temp;
                    char stop=0;
                    j=0;
                    //strtok split the line into token
                    temp=strtok(line," ");
                    while(stop==0){
                        sscanf(temp,"%d",&array[i*(MAX_SEQ_SIZE)+j]);
                        temp=strtok(NULL," ");
                        if(array[i*MAX_SEQ_SIZE+j]==0){stop=1;}
                        j++;
                        printf("j %d\n",j );fflush(stdout);
                    }
                    i++;
                }

            }
        }
        fclose (pFile);
    }
    if(array!=NULL){
        for(i=0;i<nbclauses;i++){
            j=0;
            while(array[i*MAX_SEQ_SIZE+j]!=0){
                printf("line %d seq item %d worths %d\n",i,j,array[i*MAX_SEQ_SIZE+j]);
                j++;
            }
        }
        free(array);
    }
    return 0;
}