Sign in to follow this  

Vector STL Implementation

This topic is 3722 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

Hey, I' m going to write the core classes of my graphics engine but, during the development of a vector-like class I' ve discovered that my class is much slower than the original one... o.o My class has a templated pointer and a push_back() function which allocates a block if there's not enough memory and writes the value... I' ve written a test-application and... The std::vector class writes 50000 elements in 1 second while my implementation does it in 15 seconds o.o What could be the problem ? Thanks, Bye !

Share this post


Link to post
Share on other sites
Most commonly used implementations of the STL are highly optimised and you should rarely expect to be able to write anything that's faster unless you know specifically why an STL container is going to be sub-optimal for a given situation.

In this case there are likely a number of reasons why std::vector is faster than your implementation of a vector-like container. I suspect a main killer is the way that your STL vector implementation resizes itself campared to you vector-like container.
Many STL implmentations will resize proportionally based on the current capacity by a factor of 2, so it doubles its capacity, giving you a linear time operation when performing repeated push_backs, if you were to only increase the capacity by a constant amount then it will be a hefty quadratic time operation.

Not to mention, in the STL, allocation and construction are separated tasks; giving fast and efficient allocation and JIT (Just-In-Time) construction of elements.

Share this post


Link to post
Share on other sites
Quote:
Original post by jwein
a push_back() function which allocates a block if there's not enough memory and writes the value... while my implementation does it in 15 seconds o.o
What could be the problem ?


Are you by any chance increasing the allocation size by just 1 each time (i.e. just enough room to hold the new element)? std::vector is smarter than that :)

Share this post


Link to post
Share on other sites
Hey, no i' ve solved the problem there was a bug in the programming. :)
I' m writing my class because i don' t like to use code of third part except for the graphics api :)
My class is faster than the original with lots of elements and it has an equal performance for little loops...
Sorry for my bad english but i'm italian :)

Share this post


Link to post
Share on other sites
Quote:

' m writing my class because i don' t like to use code of third part except for the graphics api :)

std::vector isn't a third-party library.

Quote:

My class is faster than the original with lots of elements and it has an equal performance for little loops...

Somehow I doubt this.

Share this post


Link to post
Share on other sites
It's not hard to beat STL in speed, especially the STL in 2005 which got slower than in 2003 due to the checked iterator crap being enabled even in release. He should probably make sure he's comparing the speed to the STL with that disabled.

Share this post


Link to post
Share on other sites
Quote:


Quote:

My class is faster than the original with lots of elements and it has an equal performance for little loops...

Somehow I doubt this.


I too find this very unlikely. Especially if it has gone from a 15 sec pause inducing bug to a Stroustrup and co. out performing class. But if this is truly the case I think that we NEED to see that code... so we can all use it.

BTW I was in the same boat as you about not wanting to use other's code for a long time. I have come around on the stl, not using it is like shooting yourself in the foot. Its cross platform, and truly part of C++.

Share this post


Link to post
Share on other sites
If your custom vector class does the exact same thing as std::vector, it's probably just better to use std::vector. The *possible* performance enhancement isn't worth the trouble.

Personally, I did write my own custom array class. But that was because I required an array which had a constant time for accesses and was reasonably fast at randomly inserting/deleting elements. Since std::vector guarantees contiguity, it needs to move half the data around if I insert something into the middle. So I designed a specifically non-contiguous version, which maintained an array of pointers which pointed to the data. If I wanted to insert an element into the middle, only the array of pointers would move and not the actual data.

In the case of small data types (around 4-8 bytes) it automatically switches to use std::vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sc4Freak
If your custom vector class does the exact same thing as std::vector, it's probably just better to use std::vector. The *possible* performance enhancement isn't worth the trouble.

Personally, I did write my own custom array class. But that was because I required an array which had a constant time for accesses and was reasonably fast at randomly inserting/deleting elements. Since std::vector guarantees contiguity, it needs to move half the data around if I insert something into the middle. So I designed a specifically non-contiguous version, which maintained an array of pointers which pointed to the data. If I wanted to insert an element into the middle, only the array of pointers would move and not the actual data.

In the case of small data types (around 4-8 bytes) it automatically switches to use std::vector.


Hmmm, aren't your pointers around 4 or 8 bytes?

Share this post


Link to post
Share on other sites
Quote:
Original post by vs322
I too find this very unlikely. Especially if it has gone from a 15 sec pause inducing bug to a Stroustrup and co. out performing class. But if this is truly the case I think that we NEED to see that code... so we can all use it.

BTW I was in the same boat as you about not wanting to use other's code for a long time. I have come around on the stl, not using it is like shooting yourself in the foot. Its cross platform, and truly part of C++.
Yeah, because that's obviously impossible..

STL has to make a lot of trade-offs, and not all of them aimed solely to improve speed. The OP may just have used a larger growth factor for instance, or his STL implementation may have chosen not to inline something to reduce code size, etc.

Either way a classic dynamic vector is so simple that there just aren't many performance hacks the STL implementors could've used. As long as you're working with POD types and everything is inlined I'd expect much the same performance from any reasonable implementation.

Share this post


Link to post
Share on other sites
Quote:

Either way a classic dynamic vector is so simple that there just aren't many performance hacks the STL implementors could've used. As long as you're working with POD types and everything is inlined I'd expect much the same performance from any reasonable implementation.

Uh, you're kind of agreeing with us here. std::vector is, in fact, rather simple, so it's very unlikely to expect somebody like the OP (based on his posts here and in the past) has managed to stumble upon something that is so much better (even in general, as he implies, although perhaps he's only benchmarking with custom objects the custom vector was designed for).

I'm more inclined to believe that he's simply using bogus tests, like profiling in debug mode or "timing" code that the optimizer removes because it's a bunch of no-ops.

Share this post


Link to post
Share on other sites
Quote:
Original post by jpetrie
Quote:

Either way a classic dynamic vector is so simple that there just aren't many performance hacks the STL implementors could've used. As long as you're working with POD types and everything is inlined I'd expect much the same performance from any reasonable implementation.

Uh, you're kind of agreeing with us here. std::vector is, in fact, rather simple, so it's very unlikely to expect somebody like the OP (based on his posts here and in the past) has managed to stumble upon something that is so much better (even in general, as he implies, although perhaps he's only benchmarking with custom objects the custom vector was designed for).

I'm more inclined to believe that he's simply using bogus tests, like profiling in debug mode or "timing" code that the optimizer removes because it's a bunch of no-ops.
What I meant to say was that there's very little room for performance improvements except for the growth factor.
I figure you're probably right. But then there's a decent chance he's profiling it against Visual Studio with it's 50% growth, while he's using traditional size doubling himself. After all I'd expect the resizing to account for a fair chunk of the time in a micro-benchmark like this.

Then again it might just be a lucky realloc() call or something..

Share this post


Link to post
Share on other sites
Quote:
Original post by jwein
Hey, no i' ve solved the problem there was a bug in the programming. :)
I' m writing my class because i don' t like to use code of third part except for the graphics api :)
My class is faster than the original with lots of elements and it has an equal performance for little loops...
Sorry for my bad english but i'm italian :)


The STL is The Standard Template Library.
It's not a third party library, its actually part of C++.
Writing your own vector container because you don't want to use the one provided is a bit like using a goto to subvert using a for loop - It has everyone confused as to why you'd want to do that and it doesn't look anywhere near as neat/clean/consistent even if it does (seem to) work just the same.

It's certainly feasible that your implementation may work just as fast, but is it as safe? Also what type were you using for elements when you were profiling both containers?

Share this post


Link to post
Share on other sites
It's not unlikely at all. STL, at least in MSVC 2005, has alot of extra crap in it that has severe effects on performance. Obviously much of it is useful debugging functionality to catch iterator bugs and stuff. Many people aren't aware of how to disable it. The fact that in MSVC2005 these things are enabled in release builds unless you define some additional preprocessor macros causes a severe performance hit, even over the MSVC2003 STL. I would bet he is comparing to the default release version, which is in fact not very good performance wise. He should disable the release build safety checks and compare to the significantly more speedy STL if he is using 2005 or another implementation that does similar things.

STL is excellent no doubt, and if speed is a priority you need to make sure the extra iterator checking and such is disabled.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by Sc4Freak
If your custom vector class does the exact same thing as std::vector, it's probably just better to use std::vector. The *possible* performance enhancement isn't worth the trouble.

Personally, I did write my own custom array class. But that was because I required an array which had a constant time for accesses and was reasonably fast at randomly inserting/deleting elements. Since std::vector guarantees contiguity, it needs to move half the data around if I insert something into the middle. So I designed a specifically non-contiguous version, which maintained an array of pointers which pointed to the data. If I wanted to insert an element into the middle, only the array of pointers would move and not the actual data.

In the case of small data types (around 4-8 bytes) it automatically switches to use std::vector.


Hmmm, aren't your pointers around 4 or 8 bytes?

Yes. That's why if I specify an Array<int> (for example), the class will automatically switch its internal implementation to std::vector.

Share this post


Link to post
Share on other sites
Hi, I know that std::vector is not a thirdy party library but i didn't know how to explain that in English. I' ve written my own class because i want to "see" all the code that i compile in my engine ( However I know that the original one was written by more experienced coders ).
Last test ( i don't remember the number of loops ) was: 1.23 seconds for the original one, 0.7 seconds for our implementation... ( about 70 % difference )
To do this i' ve coded something like allocate( _numElements * 2 + _x ) where _x is incremented in every resize...

Share this post


Link to post
Share on other sites
Trust me, if you _ever_ want to finish what you are programming,
use the stl (the time you are wasting in inventing your own implementation
you should rather spend on important things (like making your game fun
to play)

There are only a few situations where you might not want to use it (and
in these cases you will have good arguments against it).
And in the end, if the profiler shows that std::vector is really the
bottleneck in your application (and you still have time before release),
then you can always optimize things.

If I have to decide between potential candidates for a job, I'll
definitely prefer the one who knows stl over the one who "will do
it himself" - even if only because you will always be in a situation
where you'll have to use some existing code / sdk's and you should
be able to work into that and use it (as opposed to doing everything
from scratch).

Share this post


Link to post
Share on other sites
Quote:
Original post by jwein
Last test ( i don't remember the number of loops ) was: 1.23 seconds for the original one, 0.7 seconds for our implementation... ( about 70 % difference )
To do this i' ve coded something like allocate( _numElements * 2 + _x ) where _x is incremented in every resize...


If you are using MSVC, google for "_HAS_ITERATOR_DEBUGGING" and "_SECURE_SCL". Adjust how you compile the code and then benchmark again.

It is much better to spend 5 minutes learning how to optimise your builds than it to spend 5 weeks reimplementing, debugging and "benchmarking" what others have done already.

Share this post


Link to post
Share on other sites
Quote:
Original post by jwein
Hi, I know that std::vector is not a thirdy party library but i didn't know how to explain that in English. I' ve written my own class because i want to "see" all the code that i compile in my engine ( However I know that the original one was written by more experienced coders ).

You can see the standard library code too. Since it's templated, the source is included with the compiler.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
You can see the standard library code too. Since it's templated, the source is included with the compiler.

Of course, reading from the Necronomicon translated into pig-latin while standing on your head during an acid trip is less sanity testing than trying to decode the source to many standard library implementations.

Share this post


Link to post
Share on other sites
Quote:
Original post by jwein
Hi, I know that std::vector is not a thirdy party library but i didn't know how to explain that in English. I' ve written my own class because i want to "see" all the code that i compile in my engine ( However I know that the original one was written by more experienced coders ).

Unfortunately, in the real world that's not always an option. However there's nothing stopping you from snooping around inside the STL files.

Quote:
Last test ( i don't remember the number of loops ) was: 1.23 seconds for the original one, 0.7 seconds for our implementation... ( about 70 % difference )
To do this i' ve coded something like allocate( _numElements * 2 + _x ) where _x is incremented in every resize...

That doesn't hold much salt.

We don't know what data type you were storing in the containers, was it a primitive type? An object/class type?

What properties did the type possess? Did it have a non-trvial copy constructor for example?

If you're using only primitive types have you compared to a valarray at all?

What happens if you use a bool as the data type? (In terms of performance and memory)

How many loops did you actually do? Have you tried suitably larger/smaller counts?

How full was each container compared to its capacity once you'd finished? Perhaps your container was just on the verge of another expensive reallocation whereas the vector had just done one.

How many reallocations did each container do in total?

How were you iterating each container?

Does your container reserve any memory prior to the loop? Do you reserve any in the vector?

Did you remember to use a release build? Did you disable all pre-processor macros for run-time debugging in the STL container?

Assuming that your container is legitimately faster than a vector then what tradeoffs have you made to achieve that performance?
One can usually increase speed performance by sacrificing say memory consumption, safety or good programming idioms (like RAII).
You also have to consider whether you're making proper use of the STL in the first place, most people who roll their own containers without good reason don't make performant use of the STL anyway hence they think they've created something better when they havn't really.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
It's not unlikely at all. STL, at least in MSVC 2005, has alot of extra crap in it that has severe effects on performance.
That's a bit harsh. The SC++L of VS2005 has lots of good useful iterator debugging added to it, I would say. It picked up a number of bugs in products I've maintained.
Correctness over speed.

Reading the standard library implementation isn't that hard really.

Beware of falling prey to the NIH (Not invented here) syndrome.

Share this post


Link to post
Share on other sites

This topic is 3722 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this