Thread: Trying to make this run faster

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

  2. #17
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    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...
    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

  3. #18
    .
    Join Date
    Nov 2003
    Posts
    307
    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.

  4. #19
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    I would have also thought that the algorithm is to blame (instead of the I/O), except for this 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.

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

  6. #21
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Adak View Post
    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:

    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).
    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

  7. #22
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    Yes fscanf() is a total failure
    Woah, straw-man argument to the extreme! Who said fscanf() is a total failure?

    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:
    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.

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    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 Nice job.
    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

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

  10. #25
    Registered User
    Join Date
    Jun 2009
    Posts
    5
    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.
    Last edited by wkohlani; 06-26-2009 at 11:48 PM.

  11. #26
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  12. #27
    Registered User
    Join Date
    Jun 2009
    Posts
    5
    Quote Originally Posted by quzah View Post
    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

  13. #28
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by wkohlani View Post
    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.
    Hope is the first step on the road to disappointment.

  14. #29
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > // 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
    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.

  15. #30
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by wkohlani View Post
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

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