optimization

This is a discussion on optimization within the C Programming forums, part of the General Programming Boards category; hey guys, I have the following code : for (int =0;i<a.size();i++) { if(key==a[i]) printf("found");break; } can anyone tell how can ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    12

    Unhappy optimization

    hey guys,

    I have the following code :

    for (int =0;i<a.size();i++)
    {
    if(key==a[i])
    printf("found");break;
    }


    can anyone tell how can achieve the same without checking i with the condition lessthan a.size()(which is the size of the array a).

    thanx
    krithi

  2. #2
    Registered User Draco's Avatar
    Join Date
    Apr 2002
    Posts
    463
    Put your question more into context. If that runs too slow, you could just check the size of the string outside the loop once and assign it to a variable. Then just check if I is below the variable. Other than a possible speed problem, I see nothing wrong with your code. Add a pice of outside code if it would help with answering your question.

  3. #3
    Registered User rmullen3's Avatar
    Join Date
    Nov 2001
    Posts
    330

    ~

    Code:
    for (int i = 0; i < a.size(); ++i)
    {
         if (key==a[i]) {
             printf("found"); break;
         }
    }
    Draco: That shouldn't make a difference, as the compiler would calculate a.size() only once.

    There's no real way to directly optimize your code. You're obviously searching through something, so the only route for optimization is to perhaps choose a better search algorithm, perhaps one that searches only the areas of the array that could contain key (thus, a would have to be sorted).
    "He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson

  4. #4
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078

    Re: ~

    Originally posted by rmullen3

    Draco: That shouldn't make a difference, as the compiler would calculate a.size() only once.
    Not necissarily. In many cases the compiler can't know that the size function will be returning the same value anytime.

  5. #5
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    As rmullen3 pointed out a.size() is only calculated once. It can be faster to write for loops like this:

    Example
    Code:
    int i = a.size();
    
    for(;i--;) {
      if(key == a[i]) {
        printf("found");
        break;
      }
    }
    Nonetheless, the most optimized (at least speed wise) would be to write your loop like this:

    Example
    Code:
    const char *cpy = a.c_str();
    
    for(;*cpy;cpy++) {
      if(key == *cpy) {
        printf("found");
        break;
      }
    }
    Like all loops that scan for something sometimes it is faster to go backwards through a loop then forwards. That is why you should put some thought into which way you loop through arrays.

    By the way, this is the C board. You really should post C++ questions there.

  6. #6
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by master5001
    As rmullen3 pointed out a.size() is only calculated once..
    Again, it is very likely that it will be called every time

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Well it may be called every time, but for a loop this small the compiler will typically optimize the loop so it is only called once. Though keep in mind I am only making assumptions from what I've observed my compilers to do in this situation. A for loop could be broken down into this:

    Code:
    int i = 0;
    
    label1:
    if(i < a.size()) {
      // do stuff
      goto label1;
    }
    However, compilers are geared towards optimizing loops so it would most likely move a.size() into one register and compare the regiser to i (which may also be a register). That is why in both my examples I didn't compare it to a.size().

  8. #8
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Originally posted by master5001
    Well it may be called every time, but for a loop this small the compiler will typically optimize the loop so it is only called once. Though keep in mind I am only making assumptions from what I've observed my compilers to do in this situation. A for loop could be broken down into this:

    Code:
    int i = 0;
    
    label1:
    if(i < a.size()) {
      // do stuff
      goto label1;
    }
    However, compilers are geared towards optimizing loops so it would most likely move a.size() into one register and compare the regiser to i (which may also be a register). That is why in both my examples I didn't compare it to a.size().
    In most cases that's not a possibility. The only time it could possibly do that is if the function is in the same module as the for loop.

    Why?

    Because the optimization you are describing is a compile-time optimization. In order to know enough to make that optimization, the for loop would have to have direct knowledge of the implementation of that function.

    If the implementation for the size member function is in another source file (which it usually would be), then the for loop wouldn't be able to see the implementation at compile time. It would have to make the assumption that the results would vary (hence it would have to call the funciton for every single iteration).

    In this case, the person writing the code can do his own optimization (because here he knows more than the compiler) and explicitly store the result of the size function and use that as a comparison in the for loop.

  9. #9
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Your point is valid. Though it does make sense I do believe in this example it could still be optimized in the way I described above, since std::string::size() is an inline function that is does not use any volatile variables it may (I'm not 100% sure on this one) be calculated only once. Then again I never personally take guesses at what my compiler does. I never write loops like that (even in my examples). I'll have to agree with Polymorphic though, a.size() may not always be calculated once, though looking at the loop I would bet that it is, there is a possibility it is not.

  10. #10
    Registered User rmullen3's Avatar
    Join Date
    Nov 2001
    Posts
    330

    ~

    Sorry, when I posted I was thinking of the evaluation of an expression, not the calling of function. So, it may be a good idea to get the size into a variable first.
    "He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 03:52 AM
  2. need reading material for c++ database optimization
    By elninio in forum C++ Programming
    Replies: 0
    Last Post: 07-25-2008, 12:32 AM
  3. optimization flags
    By markucd in forum C++ Programming
    Replies: 4
    Last Post: 06-30-2006, 10:08 AM
  4. Optimization settings
    By Roaring_Tiger in forum C Programming
    Replies: 4
    Last Post: 02-23-2005, 02:53 AM
  5. Optimization stuff
    By jverkoey in forum C++ Programming
    Replies: 2
    Last Post: 05-26-2004, 07:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21