Why is STL so slow?

122

Author

June 27, 2002 12:44 AM

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.

Kippesoep

892

June 27, 2002 12:58 AM

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.

Kippesoep

Fruny

1,658

June 27, 2002 01:03 AM

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

"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

Vorlath

122

Author

June 27, 2002 01:27 AM

Fruny: You''re missing the point entirely.

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

Fruny

1,658

June 27, 2002 01:29 AM

quote:Original post by Vorlath
Fruny: You''re missing the point entirely.

"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

SilentStrike

122

June 27, 2002 01:46 AM

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]

Vorlath

122

Author

June 27, 2002 01:49 AM

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.

SilentStrike

122

June 27, 2002 01:58 AM

So you want to read from an item in the list rather than write to it?

Fruny

1,658

June 27, 2002 02:03 AM

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 assignmentfor_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 ]

"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

Vorlath

122

Author

June 27, 2002 02:03 AM

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?

Why is STL so slow?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Why is STL so slow?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines