Skip to main content
GameDev.net gamedev.net
🔒 Locked

Question about optimizing STL vector use

Started by Ronin Magus Nov 25, 2002 at 12:51 PM 19 replies 600+ views
Original Post
Ronin Magus
Ronin Magus
Let''s say you have a vector, with maybe 2000 elements, each of a struct that has multiple members. A loop then goes through each 2000 elements and alters every member variable. An example (no meaning, just hypothetical: 
  
#include <vector>

using namespace std;

struct ABC
{
    int a, b, c;
};

int main()
{
    vector <ABC> myABC;

    myABC.resize(2000);

    for(int i = 0; i < myABC.size(); i++)
    {
        myABC[i].a ++;
        myABC[i].b ++;
        myABC[i].c ++;
    }

    return 0;
}
The STL documentation says that a [] dereference takes constant time. I''m not sure what that means, does it mean it takes just O(1) or what? So I was wondering if code like this would optimize that loop in main: 
  
int main()
{
    vector <ABC> myABC;
    ABC * ptrABC;
  
    myABC.resize(2000);

    for(int i = 0; i < myABC.size(); i++)
    {
        ptrABC = &myABC[i];

        ptrABC->a++;
        ptrABC->b++;
        ptrABC->c++;
    }
    
    return 0;
}
Would simply setting a pointer to the current element in a vector and then using that pointer be quicker than using the [] operator on the vector? This example may not matter that much but lets say you have a loop that accesses a member of a vector around 20 times. http://roninmagus.hopto.org acronymfinder.com - Find any acronym you need!
Dobbs
Dobbs
quote:
Original post by Ronin Magus
The STL documentation says that a [] dereference takes constant time. I'm not sure what that means, does it mean it takes just O(1) or what?


Yes, constant time means O(1).

And for the second part of your question, I would suggest using iterators instead of either method you listed.

Edit: Quick addition. Instead of iterators you could also use a STL algorithm like for_each.

[edited by - Dobbs on November 25, 2002 2:21:11 PM]
Fruny
Fruny
Not evaluating mABC.size() every iteration would already improve your code. The full source code for std::vector is available in <vector> - here''s the relevant code on my platform


  
typedef _Ptrit<value_type, difference_type, _Tptr,
	reference, _Tptr, reference> iterator;

iterator begin()
{  // return iterator for beginning of mutable sequence

   return (iterator(_Myfirst));
}


reference operator[](size_type _Off)
{  // subscript mutable sequence

   return (*(begin() + _Off));
}


Thus, calling myABC[k] creates an iterator from the address of the first element - for vector, an iterator is essentially a pointer, with additional typedefs - there is no hidden cost involved, and adds the offset to it ... which, if your compiler''s inlining and optimisations are any good, will be equivalent to an array lookup. Which is also what data access through ptrABC does.

The evaluation of the trade-off between speed and maintainability of the ''optimised'' code is left as an exercise to your profiler.

Premature optimisation is the root of all evils.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Kurioes
Kurioes 

  
#include <vector>
using namespace std;
struct ABC{
    int a, b, c;
};

int main()
{
    vector<ABC> myABC;
    vector<ABC>::iterator myABCiterator; // forgive me for the long name ;)

    myABC.resize(2000);
    for(myABCiterator = myABC.begin(); myABCiterator != myABC.end(); myABCiterator++)
    {
        (*myABCiterator)->a ++;
        (*myABCiterator)->b ++;
        (*myABCiterator)->c ++;
    }
    return 0;
}


Hope that''s correct...
Is there a faster way?... I always use this.
Dobbs
Dobbs
quote:
Original post by Kurioes
for(myABCiterator = myABC.begin(); myABCiterator != myABC.end(); myABCiterator++)

...

Is there a faster way?... I always use this.


There's no need to evaluate myABC.end() in each iteration of that loop.

Edit: oops

[edited by - Dobbs on November 25, 2002 4:09:24 PM]
Kurioes
Kurioes
quote:
Original post by Dobbs
[quote]Original post by Kurioes
for(myABCiterator = myABC.begin(); myABCiterator != myABC.end(); myABCiterator++)

...

Is there a faster way?... I always use this.


There''s no need to evaluate myABC.end() in each iteration of that loop.
quote]


you mean an iterator is NULL if there''s no next element?

as in:
for (interator=container.begin(); *iterator; iterator++) ?
Hollower
Hollower
I think what he means is there is no need to call myABC.end() in each iteration. Unless the size of the vector is going to change during the loop, you can simply store the return value in a local variable and use that. Evaluate has a specific meaning in C++ so he shouldn''t have used that word.
SabreMan
SabreMan
quote:
Original post by Hollower
Evaluate has a specific meaning in C++ so he shouldn''t have used that word.

Evaluate was exactly the right word to use. The meaning in C++ is to "determine the value of an expression".
Evil Bill
Evil Bill
What i''d do:

  
int main()
{
vector<ABC> myABC;
ABC* pEnd = &myABC[2000];

   myABC.resize(2000);
   for(pData=&myABC[0]; pData!=pEnd; pData++)
   {
      pData->a++;
      pData->b++;
      pData->c++;
   }
}

That should be slightly faster, since its not a lookup anymore, its just a dereference.

Member of the Unban Mindwipe Society (UMWS)
SabreMan
SabreMan
quote:
Original post by Evil Bill
ABC* pEnd = &myABC[2000];

WTF is that? You get the value of end from calling the end() member function, not by inventing your own value for it.
Evil Bill
Evil Bill
D''oh! Sorry, me being blonde again
Well, it equates to the same thing anyway.

Member of the Unban Mindwipe Society (UMWS)
silvermace
silvermace
1. it dosnt eval .end() everytime, unless you compiler sucks shit and cant optimize.

2. iterators are the fastest way, thats why they''re there

3. using a std::slist or std::list would be faster

4. (*iter) for a vector iterator, this indirection is unneeded (i think)

Evil Bill
Evil Bill
1. Only if theres *no* optimization
2. Not always. They''re there to provide a standard interface to the container. This is why std::list & std::vector''s itterators behave the same way. Well-written code should be able to change from list to vector and back, by only changing the declaration of the variable
3. Nope. std::list would be faster if you were doing a lot of pop()s and push()s. Here, vector will be faster
4. The indirection is always needed (see 2.)

Member of the Unban Mindwipe Society (UMWS)
Qw3r7yU10p!
Qw3r7yU10p!
use ++iterator rather than iterator++
Evil Bill
Evil Bill
Agaian, any deacent compiler should optimize that. I still use ++iter usually anyway.

Member of the Unban Mindwipe Society (UMWS)
Qw3r7yU10p!
Qw3r7yU10p!
really the nice way to do it is to use a function object

  
class ABCManipulator {
    void operator(ABC& toBeChanged) {
        toBeChanged.a++;
        toBeChanged.b++;
        toBeChanged.c++;
    }
};  


  
    vector <ABC> myABC;

    myABC.resize(2000);
    for_each(myABC.begin(), myABC.end(), ABCManipulator());


also it''s relly probably in your interest to make the member variables private and have a public function with a meaningful name such as BumpUpAllStats() or something. That would put all the complicated manipulation in the class and the ABCManipulator class would have an easier job. If it was reduced to one function there are other ways of doing the calling without having to create the function object class. Come and ask more if you want, I have to do some work now.
SabreMan
SabreMan
quote:
Original post by Evil Bill
D''oh! Sorry, me being blonde again
Well, it equates to the same thing anyway.

There''s no such guarantee.
Qw3r7yU10p!
Qw3r7yU10p!
quote:
Original post by Evil Bill
Agaian, any deacent compiler should optimize that. I still use ++iter usually anyway.


only if the iterator is a built-in type and the return value isn''t being used.

if the iterator is something ''other'' then it possibly won''t be optimised because there may be unforseen side effects. (plenty of qualifiers there)

it''s an easy habit to get into and you''re not having to rely on the compiler. you''re telling it what you mean rather than hoping it understands what you mean and in this case it''s very easy to do.

ps. i should have made the ABCManipulator either a struct or with a public: operator()
civguy
civguy
quote:
Original post by petewood
only if the iterator is a built-in type and the return value isn''t being used.
Sigh, you didn''t read my lengthy post about the same thing did you (in a previous thread where you claimed the same thing)? Why can''t the return value be used? Post-increment simply delays the addition until after the evaluation.

b = (t++) * 3;

<=>

b = t * 3;
++t;

No temporary as you can see. I can''t prove that every compiler does it like this, but I''d like to see even a single compiler that doesn''t do it like this.
SabreMan
SabreMan
quote:
Original post by civguy
Post-increment simply delays the addition until after the evaluation.

That''s not the point. Postfix increment cannot be commuted to prefix increment if the compiler cannot verify there are no side-effects of the operator. Removal of such side-effects would change the semantics of the operation. That''s why the compiler cannot necessarily perform this optimisation for UDTs.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.