Re: Collections of derived objects
Jeff Flinn wrote:
While I haven't analyzed performance of std::list iterating through
std::deque is significantly slower than iterating through a std::vector
on MSVC8 and XCode3.1.2 gcc 4.0. Until we get hierarchical algorithms
iterator performance is another dimension to deciding which container
type to use.
According to my measurements, if you traverse a std::deque using
iterators (in the same way you would do for a std::list), the speed
difference compared to std::vector is not drastic. Traversing using
operator[] does show a comparable speed difference.
I made a small program which measures the speed of traversing a
container containing 1 million elements and got these results:
std::vector, operator[] traversal: 0.96 ms.
std::vector, iterator traversal: 0.96 ms.
std::deque, operator[] traversal: 5.915 ms.
std::deque, iterator traversal: 1.71 ms.
The program was the following:
//-------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <deque>
#include <ctime>
template<typename Container_t>
int measureTraversalSpeed(const char* containerName)
{
const int kElementsAmount = 1000000;
const int kIterations = 2000;
Container_t container(kElementsAmount, 0);
int sum = 0;
std::clock_t iClock = std::clock();
for(int iCounter = 0; iCounter < kIterations; ++iCounter)
{
for(size_t index = 0; index < container.size(); ++index)
sum += container[index];
}
std::clock_t fClock = std::clock();
std::cout
<< containerName << ", operator[] traversal: "
<< double(fClock - iClock) * 1000 / kIterations / CLOCKS_PER_SEC
<< " ms." << std::endl;
iClock = std::clock();
for(int iCounter = 0; iCounter < kIterations; ++iCounter)
{
for(typename Container_t::iterator iter = container.begin();
iter != container.end(); ++iter)
sum += *iter;
}
fClock = std::clock();
std::cout
<< containerName << ", iterator traversal: "
<< double(fClock - iClock) * 1000 / kIterations / CLOCKS_PER_SEC
<< " ms." << std::endl;
return sum;
}
int main()
{
// We return the sum so that gcc won't optimize the loops away...
return
measureTraversalSpeed<std::vector<int> >("std::vector") +
measureTraversalSpeed<std::deque<int> >("std::deque");
}
//-------------------------------------------------------------------------
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---