Thread: Trying to make this run faster

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    5

    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.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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).
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.
    Last edited by Adak; 06-23-2009 at 11:56 PM.

  4. #4
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    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.

    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.

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    5
    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.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by bithub View Post
    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.

  7. #7
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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.

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    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.
    Last edited by KBriggs; 06-24-2009 at 08:06 AM.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Tha 1 Sick RAT
    Join Date
    Dec 2003
    Posts
    271
    Quote Originally Posted by wkohlani View Post
    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.
    A hundred Elephants can knock down the walls of a fortress... One diseased rat can kill everyone inside

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  12. #12
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    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.

  13. #13
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> 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.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Some help with make my programs faster
    By Sshakey6791 in forum C++ Programming
    Replies: 11
    Last Post: 12-11-2008, 01:41 PM
  2. What to make?
    By Caldus in forum C++ Programming
    Replies: 4
    Last Post: 04-06-2005, 01:12 PM
  3. A few questions on programs and when they can run...
    By Junior89 in forum Windows Programming
    Replies: 2
    Last Post: 04-05-2005, 07:47 PM
  4. Making standalone APP run in background
    By hart in forum Windows Programming
    Replies: 3
    Last Post: 02-27-2005, 11:20 AM
  5. plz help me run this program!!!
    By galmca in forum C Programming
    Replies: 8
    Last Post: 02-01-2005, 01:00 PM