Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Vorlath

Why is STL so slow?

This topic is 5867 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was doing some timing tests between a list and my own implementation (for lists only). Why is it that my version is so much faster? It''s not ever worth using STL at all. And I had to take out the comparison on iterator.end() because this slows down STL by a factor of 100. All it does is just compares with NULL and it''s a function call that VC doesn''t make inline. Why do people use STL? It''s certainly not for the speed.
  
  list<int>::iterator i;
  list<int> l(100000);

  list<int>::iterator end = l.end();
  int cnt = 0;
  for (i=l.begin();i!=end;i++,cnt++)
  {
    *i = cnt;
  }
  
If I replace list with my own linked list implementation, it''s so much faster. It''s even worse with deque and vector.

Share this post


Link to post
Share on other sites
Advertisement
One thing to do is use "++i" instead of "i++".
The VC implementation of the STL is rather outdated. If you want a superior, better performing STL implementation, try STLport.

Share this post


Link to post
Share on other sites
Maybe because you're not using it properly :


    
#include <iterator>

#include <algorithm>

#include <list>

using namespace std;

template<class T>
class iota
{
T value;
public:
iota( T v ) : value( v ) {};
inline T operator() { return value++; };
};

list<int> l;
generate_n( back_inserter<int>(l), 100000, iota(0) );


or, using boost's counting iterators :


  
#include <list>

#include <boost/counting_iterator.hpp>

using namespace std;
using namespace boost;

list<int> l( make_counting_iterator(0), make_counting_iterator(100000) );


And you have to make sure that you're using the right container to the right task.

Then I'll ask you : your list implementation may be faster, but is it as convenient ? Is it faster in all possible use cases ? Does it provide the same functionality (e.g. list::sort) ? Is it type-safe ? Is it generic ? And so on, and so forth.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]


[edited by - Fruny on June 27, 2002 2:06:33 AM]

Share this post


Link to post
Share on other sites
Fruny: You''re missing the point entirely.

Kippesoep: Thanks. CBuilder 6 uses it. I''ll have to try it out with that.

Share this post


Link to post
Share on other sites

I tested this with MSVC 6. The STL version runs slowering in debug mode by factor of 2.5, but approximately the same in release mode (ran faster by 10, equal, and then slower by 10). As for why to use the STL, even if it's slower. The test case for my own linked list took like 15 minutes to debug, I was incrementing cur twice in the deallocation loop (Given, I am a very poor C programmer.. don't have to manually do much pointer stuff anymore) .


  
#include <list>
#include <ctime>
#include <iostream>

template <class T>
struct ll_node {
ll_node* next;
T data;
};

const int testSize = 1000000;

void testStdList() {
std::list<int> l(testSize);
std::list<int>::iterator end = l.end();
int cnt = 0;

clock_t start = clock();

for (std::list<int>::iterator i=l.begin();i!=end;i++,cnt++)
{
*i = cnt;
}

std::cout << clock() - start << std::endl;

}

void testMyList() {
ll_node<int>* head = new ll_node<int>;
ll_node<int>* cur = head;
int cnt=0;

while (cnt < testSize) {
cur->next = new ll_node<int>;
cur=cur->next;
cnt++;
}
cur->next=NULL;
cnt=0;

clock_t start = clock();

for (cur = head; cur != NULL; cur=cur->next, cnt++) {
cur->data = cnt;
}

std::cout << clock() - start << std::endl;

for (cur = head; cur != NULL; ) {
ll_node<int>* tmp = cur;
cur = cur->next;
delete tmp;
}
}

int main() {
testStdList();
testMyList();

return 0;
}




[edited by - silentstrike on June 27, 2002 2:49:25 AM]

Share this post


Link to post
Share on other sites
I was doing a test on how fast a list is at iterating through all the elements. *i = cnt was just a dummy piece of code so that it would do something and access the item. All you did was re-implement my loop taking into consideration *i = cnt. The assignment (or rather the cnt value) is irrelevant, but the access to the item IS. Your implementation shows no direct access to the item which is what I want to test. Pretend you don''t know what type of item I''m storing and give me access to each item, then you can change my loop. But I probably shouda made clear what I was testing. Sorry.

BTW, I appreciate you taking the time to reply. Thanks.

Share this post


Link to post
Share on other sites
quote:
Original post by Vorlath
Pretend you don''t know what type of item I''m storing and give me access to each item, then you can change my loop.


Ok, no big deal. When you look at the code for the for_each loop, here''s how it is implemented (a bit cleaned up from SGI''s implementation)


  

// Assign is some functor doing your assignment

for_each( l.begin(), l.end(), Assign() );

// for_each. Apply a function to every element of a range.

template <class InIt, class Func>
Func for_each( InIt first, InIt last, Func f)
{
// compile-time concept check

__STL_REQUIRES( InIt, _InputIterator);

for ( ; first != last; ++first)
f(*first);
return f;
}


Note that l.end() will be evaluated only once, just like any other function parameter (i.e. ''last''). And that they use pre-increment.

The actual overhead due to the iterators is implementation-dependent, as Kippesoep pointed-out (and the Dinkum implementation that ships with MSVC is crappy... which is why they Dinkumware sells another version as a ''drop-in'' replacement).

It is in the interest of library providers to provide you with the most efficient library they can produce.

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]

Share this post


Link to post
Share on other sites
SilentStrike: Sorry, that last message was directed at Fruny.

Your post was exactly what I was looking for. You understood perfectly. Thanks for those results. My results were a bit better, but that might be due to the implementation I''m using. If so, then this is good news. And I know STL is way better than writing your own development time wise. But I''m looking for speed.

I guess I just don''t need all the functionality of STL.
Anyone know of any stipped down version of STL that''s built just for speed?

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!