Trying to make this run faster

Hi Everyone:

First, I'd like to say that I'm new here and I hope to find the help I need.


I wrote a c program that reads a GIGANTIC file (~16GB) line by line using fscanf in a while loop as show below

Code:

---

while(fscanf(file, "%d %d %d", &inst_type, &in_delay, &sp_type ) != EOF)
{

// here I do simple processing with the variables read from the file
}

---

I'm supposed to output a result every million lines; the problem that this thing takes A LONG LONG TIME. It's been weeks so far and it's not done (running on a quad-core opteron).

Anyways, if I don't read the file and instead generate those variables randomly, the program runs very quickly (few minutes to finish).


I tried to output something(say result y) every 100 thousand lines and see how fast it's going and I noticed the following.

The first 10 y's came out quickly (they followed one another in an almost fixed interval of a one second or two), but then the y's started to come out slower and slower. It was like becoming exponentially SLOWER.


I don't know what the problem is. Is it the way I'm reading the file? Is there a buffer somewhere that's getting huge and making things dog slow? I really don't know.


Does anyone have any idea about this?


Thanks


P.S.
I also tried to profile (using gprof ) the program, but did not have luck getting it to work. There was all kids of errors that gprof generated and I'm no mood getting busy with those.

Not sure, but fscanf isn't a very efficient function. You might have better luck doing things "manually" (ie: fgets, then parsing the ints out, etc).

Fscanf() is the fastest file reader for text, in the tests I've seen, so that's not your problem. Fread() in binary mode is naturally faster, however - no translation for a text file is done.

I suspect you're trying to read and write out, in alternating loops, a very small amount of data, to the same hard drive.

That will just tear up the performance of the HD.

Your HD has a buffer, and you should be reading in data in a tight loop, and putting that data into a large array to process, later.

That will optimize the HD performance. One or two lines being read every second or two is an absolute travesty! You should have >500 lines read, in two seconds, if the data is adjacent on the HD.

Then when you've filled up the array, process all the data (do no more HD work, until your data is ready to be written to a file). Then write out all the data you've processed from the array, all at once.

Quote:

---

Fscanf() is the fastest file reader for text, in the tests I've seen, so that's not your problem.

---

Actually Sebastiani is correct. fscanf() is pretty slow compared to just using fgets() and parsing the data out manually.

Quote:

---

Your HD has a buffer, and you should be reading in data in a tight loop, and putting that data into a large array to process, later.

---

The file is 16GB, so I think reading all the values into an array is out of the question.

Thanks guys for this good start !

I don't think I'm very worried about "fgets" or "fscanf" because I've used both before and things were the same.

The big problem that I don't understand is why at first things are running very fast (which I would like to keep ), but then gradually the program gets slower and slower.

That is, the first 3-4 million lines are processed in less than 12 minutes, but the next 4 million lines would take a few hours, and the next few million lines will take even longer .....etc.

That's what I don't understand.



Thanks again for the effort, and I hope someone can give me a pointer as to what is slowing things down.

Quote:

---

Originally Posted by bithub

Actually Sebastiani is correct. fscanf() is pretty slow compared to just using fgets() and parsing the data out manually.

The file is 16GB, so I think reading all the values into an array is out of the question.

---

Show me a test on the same equipment, where fscanf is slower than fgets + parsing out the data from the fgets buffer.

You can't, period.

I never said load all 16 GB into an array - I said load as much as you can into a large array, all at once.

It slows down because the HD buffer (which is fast RAM), has been filled up, and now you're reading and writing in small chunks. Between each read and write, your buffer is probably flushing itself out.

Your throughput is slowing down so much, I wonder if your OS is starting to use the drive to emulate RAM. That will bring your processing to a near stop!

What does Task Manager or System Resources tell you about this, while it's running the program?

I'll be glad to check it out, and maybe even tweak it for you, if you like.

Upload the program and a data file, to Swoopshare, and give me the url in a private message. A 1 GB file (whatever the biggest that Swoopshare will allow), for testing will be fine.

This is not something I would use text-mode for.

Read say, 8mb or more a time with fread(), and parse each line yourself. You should see a tremendous increase then.

You say you output every millions lines:

read the relevent info from 1 million lines into an array
do your operations and output
continue reading a million lines at a time into this array and repeat

An array of 3 million ints is certainly manageable, and you can keep memory use low by just overwriting it each time.

you say that the first millions lines are very fast, and it gets slower after that. I don't know the cause, but doing this might allow you to keep the speed of the first million lines.

Quote:

---

Originally Posted by Adak

Show me a test on the same equipment, where fscanf is slower than fgets + parsing out the data from the fgets buffer.

---

This does not involve parsing of the buffer, but fscanf is noticably slower that fgets to read.

Code:

---

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

void test_fgets(FILE *fd) {
        char buffer[64];
        while (fgets(buffer,64,fd));
        rewind(fd);
}

void test_fscanf(FILE *fd) {
        char buffer[64];
        while (fscanf(fd,"%s",buffer)!=EOF);
        rewind(fd);
}

int main() {
        double lapse;
        time_t start, end;
        FILE *ptr=fopen("input/dictionary.txt","r");
        int i;

        start=time(NULL);
        for (i=0;i<1000;i++) { test_fgets(ptr); fprintf(stderr,"."); }
        end=time(NULL);
        lapse=difftime(end,start);
        printf("test_fgets: %d seconds\n",(int)lapse);
        start=time(NULL);
        for (i=0;i<1000;i++) { test_fscanf(ptr); fprintf(stderr,"."); }
        end=time(NULL);
        lapse=difftime(end,start);
        printf("test_fscanf: %d seconds\n",(int)lapse);
        fclose(ptr);
        return 0;
}

---

test_fgets: 6 seconds
test_fscanf: 11 seconds

"dictionary.txt" is 622kb. Just watching the output ("......") it is easy to tell fgets is about twice as fase. So depending on what the OP is doing with each line, this could make a HUGE amount of difference.

Quote:

---

Originally Posted by wkohlani

I'm supposed to output a result every million lines; the problem that this thing takes A LONG LONG TIME. It's been weeks so far and it's not done (running on a quad-core opteron).

Anyways, if I don't read the file and instead generate those variables randomly, the program runs very quickly (few minutes to finish).


I tried to output something(say result y) every 100 thousand lines and see how fast it's going and I noticed the following.

The first 10 y's came out quickly (they followed one another in an almost fixed interval of a one second or two), but then the y's started to come out slower and slower. It was like becoming exponentially SLOWER.

---

I think (and I really do think) the problem is that you're working with a large data set, or trying to at once; you do sound like you know what ytou're doing so I wouldn't question your programmingf logic here. but suffice to say your problem seems to be symptomatic of what Adak is trying to say in that you have a large number of data you're accruing at once (or trying to anyways), have you tried proicessing the 1st few thousand lines, flushing them to permanent storage then resuming you operation.
Remeber as you start working with such large data, the things that don't matter so much come into play, like your HD buffer, your Workling RAM, all other hardware and memory management related issues come into play, hence the reason Meteorological centers have vast arrays of powerful equipment the grids their data sets.

What else is going on inside that loop, besides printing something every so often?

Are you allocating any memory at all?
Because that will hose your machine unless you actually have a 64-bit OS and substantially more than 16GB of RAM to play with.


Try this:

Code:

---

int lines = 0;
char buff[BUFSIZ];
while ( fgets( buff, sizeof buff, file ) != NULL ) {
  if ( ++lines == 1000000 ) {
    putchar('.'); fflush(stdout);
    lines = 0;
  }
}

---

This should read the file quickly, and at a constant pace.
If it doesn't, then something else is going on.

Quote:

---

Show me a test on the same equipment, where fscanf is slower than fgets + parsing out the data from the fgets buffer.

You can't, period.

---

Wow, I can't? period??

Ok. I used this program to fill a file with 10 million lines:

Code:

---

#include <stdio.h>

int main(void)
{
    FILE* f = fopen ("./data", "w");
    unsigned int i;
    for(i = 0; i < 10000000; ++i)
        fprintf(f, "%d %d %d\n", i, i, i);
    fclose(f);
}

---

I then used the following code to read the data out. Note that there is a slow() function (using fscanf), and a fast method (custom code):

Code:

---

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

void slow(void)
{
    FILE* f = fopen("./data", "r");
    int first, second, third;
    int counter = 0;
    while(fscanf(f, "%d %d %d", &first, &second, &third) != EOF)
    { 
        counter++;
    } 
    printf("Got %d entries\n", counter);
}

int get_value(const char** pp)
{
    const char* p = *pp;
    int value = 0;
    while(isdigit(*p))
    { 
        value *= 10;
        value += *p++ - '0';
    } 
    *pp = p + 1; /* Add 1 to skip space */
    return value;
}

void fast(void)
{
    FILE* f = fopen("./data", "r");
    int first, second, third;
    int counter = 0;
    char buffer[128];
    int value;
    while(fgets(buffer, sizeof(buffer), f))
    { 
        const char* p = buffer;
        first = get_value(&p);
        second = get_value(&p);
        third = get_value(&p);

        counter++;
    } 
    printf("Got %d entries\n", counter);
}

int main(void)
{
    slow();
    return 0;
}

---

The slow method took 9.52 seconds, the fast method took 1.73 seconds. This is using GCC 4.01 with optimizations turned on.

>> The slow method took 9.52 seconds, the fast method took 1.73 seconds. This is using GCC 4.01 with optimizations turned on.

I wasn't quite sure how much of an improvement it would make, but I'm really not suprised that it turned out to be several times faster. fscanf is a huge, monolithic, swiss-army knife of a function that's great for general purpose work but often suboptimal when compared to a special purpose solution. In most cases I would prefer the former, but when it becomes a bottleneck you sometimes have to resort to "hand-rolled" approaches. Having said that, I would agree with Salem that the actual issue is probably somewhere else. But it may be a good idea, anyway, to adopt something like Bithub suggested, in order to squeeze out as much performance as possible.

Well done, Bithub! :)

I don't consider your fast function anything standard for input from a file, however.

Here's the times on my (rather slow), SATA drive:

Fast ( fgets() with custom() ): 3.95 seconds (two runs averaged)

Slow ( standard fscanf() ): 6.81 seconds (two runs averaged)

When you use the standard sscanf() in place of your custom function, you get:

Fast ( fgets() with sscanf() ): 7.36 seconds (two runs averaged)

I've seen this tested several times and fscanf() always beats other standard text mode input from a file with assignments.

wkohlani:

You know what would be fun for the forum members, and *great* for you, is to put a test data file, and your current program up where it can be d/l'ed, and then the members here could have a little fun contest and see how who can make it run the fastest and by how much. :)

I'm sure your program's speed would be significantly faster, and we can also see what might be the problem that is causing your program/system, to continually degrade in throughput.

Best of all, it's free. :D

Naturally, don't include any sensitive info in the files.

Quote:

---

I don't consider your fast function anything standard for input from a file, however.

---

There is no "standard" way to read input from a file outside of using standard C functions to achieve your goals. My method is just as standard as using fscanf(), it just isn't as flexible (since it was tailor made for the problem at hand). Using a solution customized for a known data set will always be faster than using one of the scanf() family of functions.

Quote:

---

Originally Posted by Adak

I've seen this tested several times and fscanf() always beats other standard text mode input from a file with assignments.

---

Adak, no offence, but I don't see anyway to interpret this sentence which makes sense. After a discussion on the color of the sky, inc. settling some criteria about respective wavelengths of light, etc, and even using the equipment yourself to demonstrate that the sky is in fact blue, you turn around and say:

"I've seen this tested several times and the sky is always red."

So far in this thread, several people (including yourself) have tested fscanf a number of different ways and fscanf has performed relatively poorly in every single test...

Salem is definitely on the best track. I/o can slow things down hours - crummy algorithms slow things down for weeks.

I vote for:
Linear search times on a growing array or linked list. At the start you are searching a small number of data elements, doing compare operations, etc. As you add more elements the search times keep going up. O(n) - searching an unordered list.

No way does I/O account for weeks of runtime. If that were the case the system would be unusable by other processes.

I read/write 10+GB files on HPUX 9000 series everyday. I can read a whole file with fgets() in less than 120 seconds.
11.2 GB file example:

Code:

---

/bbp01/CSF_regbills_out/cycle_18> time  hash32 [hiddenfilename].REGB.PDF
23187971334

real    1m57.44s
user    0m34.53s
sys    0m4.34s

---

That code read and processed every single character in the file. The difference:

Code:

---

real - (user + sys)

---

is due primarily to I/O wait times - ie. losing quantum for direct I/O waits.

I could see a crummy PIII PC taking a full hour to read the file. If the OS supported largefiles. Not weeks.

I would have also thought that the algorithm is to blame (instead of the I/O), except for this quote:

Quote:

---

Anyways, if I don't read the file and instead generate those variables randomly, the program runs very quickly (few minutes to finish).

---

I just assumed that his claim of it taking "weeks" was a massive exaggeration. At any rate, seeing the code in question would definitely provide us with some answers.

Quote:

---

Originally Posted by MK27

Adak, no offence, but I don't see anyway to interpret this sentence which makes sense. After a discussion on the color of the sky, inc. settling some criteria about respective wavelengths of light, etc, and even using the equipment yourself to demonstrate that the sky is in fact blue, you turn around and say:

"I've seen this tested several times and the sky is always red."

So far in this thread, several people (including yourself) have tested fscanf a number of different ways and fscanf has performed relatively poorly in every single test...

---

Yes fscanf() is a total failure - except it beats using fgets and any standard assignment function (like sscanf() for example), that I've seen actually tested.

Sure, BitHub's custom assignment function is great - but that's *customized*, so of course, it's faster.

You did see that fscanf() *beat* fgets() + sscanf() in the timed test, by more than 10% didn't you?

Quote:

---

Originally Posted by Adak

Yes fscanf() is a total failure - [COLOR="Blue"]except it beats using fgets and any standard assignment function (like sscanf() for example),

---

Sure, but you are changing your tune now:

Quote:

---

I've seen this tested several times and fscanf() always beats other standard text mode input from a file with assignments.

---

IMO iterating thru a character array with a pointer is a form of "standard text mode input"; the fact that fgets + sscanf will be more or less (+/- 10%) just as slow as fscanf itself might be intuitively obvious (but at least you did test it).

Quote:

---

Yes fscanf() is a total failure

---

Woah, straw-man argument to the extreme! Who said fscanf() is a total failure?

Quote:

---

it beats using fgets and any standard assignment function

---

What is a "standard assignment function"? This is just a made-up term that you are using to formulate some sort of point. What you mean to say is that fscanf() is faster than using both fgets() and sscanf() together. So what? sscanf() has the same general algorithm as fscanf(), and therefore it has the same inefficiencies. You are not making a point at all, you are merely stating the obvious.

At any rate, you are running away from your original argument. I'll post it here in case you don't remember what it was:

Quote:

---

Show me a test on the same equipment, where fscanf is slower than fgets + parsing out the data from the fgets buffer.

You can't, period.

---

Your original argument never mentioned sscanf(). It was just fscanf() vs fgets(). It is very easy to prove that using fgets() + parsing the buffer with some reasonable code will always be faster than fscanf(). That was the argument. Stop trying to turn it into fscanf() vs sscanf() because no one other than you has been arguing that point.

This thread has now completely been derailed. I'm sorry.

Quote:

---

Originally Posted by bithub

This thread has now completely been derailed. I'm sorry.

---

Nah. It is worth demonstrating that fgets + sscanf is not the optimized solution either and Adak brought that out. If I were reading this later, I might wonder otherwise...but bithub is taking the cake for heroics :p Nice job.

Quote:

---

Originally Posted by Adak

wkohlani:

You know what would be fun for the forum members, and *great* for you.......

---

Is if the half the people who posted on here weren't arguing about the efficiency of similar functions and actually concentrated on the matter at hand which is trying to diagnose your problem. :P
In any case pls post us a test file containing no sensitive information and maybe the releveant part of your program logic so We can run it on our respective machines and get to the bottom of your problem. Unless of course you've solved it yourself whilst some of us were debating :)

Thank you all for you valuable replies. I took some of the comments into consideration and used fgets, and also read 1 million lines at a time and put that into an array and processed that, and also tried other solutions but the same problem still exists.

I then, got gprof to work and noticed that there was a function that took 90% of the time (on a smaller sample of the input file) and was probably what was making things slow.

I commented out that function and others and kept only reading the file as mentioned in my first post. Doing that, the program was running fast at a constant speed!! So, i'm convinced now that the problem is not with reading the file, it's most likely this funciton which gets called every time I read a line.

This function is as follows:

Code:

---

double is_dependent(unsigned long long which_inst, enum stall_reason *where)
{
        struct dependency *temp, *prev;
        double ret_val = 0;

        // Scan the chain for the dependent line
        for(prev=NULL, temp=dc_head; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);

        // Found. Unlink node and return when_satisfied
        if(temp)
        {
                if(prev)
                {
                        prev->next = temp->next;
                }
                else
                {
                        dc_head = temp->next;
                }

                ret_val = temp->when_satisfied;
                *where = temp->reason;
                free(temp);
        }

        return ret_val;
}

---

By the way: dc_head is a global variable of type struct dependency


Can anyone point out what exactly in this code might be slowing things down. Memory leak? I have not looked at it closely yet, but I will very soon.


Thank you all. This has been very helpful.

Do you create and destroy 'dependency' instances often? You could always stop destroying them, and push them onto a 'free list', rather than calling malloc and free all the time. Just a thought.


Quzah.

Quote:

---

Originally Posted by quzah

Do you create and destroy 'dependency' instances often? You could always stop destroying them, and push them onto a 'free list', rather than calling malloc and free all the time. Just a thought.


Quzah.

---

hmm...

Yes, since the function is called whenever I read a line (that is 100s of millions of times), so it is getting called alot. And in each call the following line is executed:

Code:

---

struct dependency *temp, *prev;

---

So, you're suggesting that I should put that line in global scope so that I only create those dummy variables once?


But, I still need to use free() every time before exiting the function. Let me try that and see.



Thanks

Quote:

---

Originally Posted by wkohlani

And in each call the following line is executed:

Code:

---

struct dependency *temp, *prev;

---

So, you're suggesting that I should put that line in global scope so that I only create those dummy variables once?

---

No, that's not at all what I'm saying.

Code:

---

double is_dependent(unsigned long long which_inst, enum stall_reason *where)
{
        struct dependency *temp, *prev;
        double ret_val = 0;

        // Scan the chain for the dependent line
        for(prev=NULL, temp=dc_head; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);

        // Found. Unlink node and return when_satisfied
        if(temp)
        {
                if(prev)
                {
                        prev->next = temp->next;
                }
                else
                {
                        dc_head = temp->next;
                }

                ret_val = temp->when_satisfied;
                *where = temp->reason;
                temp->next = freelist;
                freelist = temp;
        }

        return ret_val;
}

---

More along the lines of that. Rather than actually call free a million times, just stuff it on another list. Then if you need to allocate one...

Code:

---

struct dependency *newdependency( void )
{
    struct dependency *d = freelist;
    if( d )
    {
        freelist = freelist->next;
    }
    else
    {
        d = malloc( sizeof *d );
    }
    return d;
}

---

It may not help you out, but I'm not sure that calling free over and over is really helping you speed things up. 'freelist' would be a global pointer to a structure.


Quzah.

> // Scan the chain for the dependent line
> for(prev=NULL, temp=dc_head; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);
Is there any possibility that this data could be sorted in any way?

Because a linear search of 1M items arranged in a line will take 1M operations.
The same 1M items in a perfectly balanced binary tree (if you can establish a sort order) is 20

Quote:

---

Originally Posted by wkohlani

Code:

---

        // Scan the chain for the dependent line
        for(prev=NULL, temp=dc_head; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);

---

---

Don't let the fact that you've crammed all that into one line confuse you into thinking that it's not still a loop over (on average) half of the items in a linked list each time.
When you're talking about easily over a million items to iterate over each time, after a little while, don't you think that's going to take a long time?!
It's where your code becomes O(n*n) and that's what makes it slow.

The rule here is: Don't repeatedly use a linear search - ever!

Quote:

---

Originally Posted by iMalc

Don't let the fact that you've crammed all that into one line confuse you into thinking that it's not still a loop over (on average) half of the items in a linked list each time.
When you're talking about easily over a million items to iterate over each time, after a little while, don't you think that's going to take a long time?!
It's where your code becomes O(n*n) and that's what makes it slow.

The rule here is: Don't repeatedly use a linear search - ever!

---

I think you're right. But, in this case, what's the alternative approach?

Is there another way of searching the linked list faster? I can't think of another approach especially with the way the structure is built now. Maybe I need to change it, but that will require major changes in the code.

If you don't want to change the linked list's structure, change how you hold the list. Instead of using one pointer to hold the list, use an array of pointers. Basically, make a hash table. Super simple version:

Code:

---

/* super lazy mode, use the last digit as what list you end up in */
#define HASHSIZE 10
struct node *dc_head[ HASHSIZE ]; /* instead of just one pointer, an array... */
...
double is_dependent(unsigned long long which_inst, enum stall_reason *where)
{
        struct dependency *temp, *prev;
        double ret_val = 0;
        size_t which_bucket = which_inst % HASHSIZE;

        // Scan the chain for the dependent line
        for(prev=NULL, temp=dc_head[ which_bucket ]; temp && temp->which_inst != which_inst; prev=temp, temp=temp->next);

        // Found. Unlink node and return when_satisfied
        if(temp)
        {
                if(prev)
                {
                        prev->next = temp->next;
                }
                else
                {
                        dc_head[ which_bucket ] = temp->next;
                }

                ret_val = temp->when_satisfied;
                *where = temp->reason;
                free(temp);
        }

        return ret_val;
}

---

Pretty much all you've done is split your list into HASHSIZE smaller lists. Now everything that ends in a 1 goes in array[ 1 ], everything that ends in a 9 goes in array[ 9 ], etc.

This is just an extremely simplified example. That's not the best number to use for hashing, but it's easy to understand, which is why I use it for examples. Now, you've cut your search time by 10.

Either way, if you use this, a tree, or something better, you're going to end up putting some work in. I think this would probably require the least amount of work, because really all you have to do is find everywhere you use dc_head and make it use an array instead. It's not the fastest method, but it's really simple.


Quzah.

Quote:

---

Originally Posted by wkohlani

I think you're right. But, in this case, what's the alternative approach?

Is there another way of searching the linked list faster? I can't think of another approach especially with the way the structure is built now. Maybe I need to change it, but that will require major changes in the code.

---

I would probably do those "major changes" if it were me. I'm sure they can't be that bad.
However an alternative approach is to insert the address of every node (as the data to store) into a binary tree of some kind (perhaps a splay tree), or into a hash table.
quzah's suggestion could be thought of as a kind of primitive hash-table.