how can I get the fastest iteration possible for some calculus intensive code?

Question

Context

I'm using a QLinkedList to store some class I wrote.
The fact is I must iterate a lot over this list.
By a lot I mean the program I write makes infinite calculus (well, you can still stop it manually) and I need to get through that QLinkedList for each iteration.

Problem

The problem is not if I'm iterating to much over this list.

It's that I'm profiling my code and I see that 1/4 of the time is spent on QLinkedList::end() and QLinkedList::begin() functions.

Sample code

My code is the following :

typedef QLinkedList<Particle*> ParticlesList;  // Particle is a custom class

ParticlesList* parts = // assign a QLinkedList

for (ParticlesList::const_iterator itp = parts->begin(); itp != parts->end(); ++itp)
{
    //make some calculus
}

Like I said, this code is called so often that it spends a lot of time on parts->begin() and parts->end().

Question

So, the question is how can I reduce the time spent on the iteration of this list ?

Possible solutions

Here are some solutions I've thought of, please help me choose the best or propose me another one :)

• Use of classic C array : // sorry for this mistake

Particle** parts = // assing it something
for (int n = 0; n < LENGTH; n++)
{
    //access by index
    //make some calculus
}

This should be quick right ?

• Maybe use Java style iterator ?
• Maybe use another container ?
• Asm ? Just kidding... or maybe ?

Thank you for your future answers !

PS : I have read stackoverflow posts about when to profile so don't worry about that ;)

Edit :

The list is modified

I'm sorry I think I forgot the most important, I'll write the whole function without stripping :

typedef std::vector<Cell*> Neighbours;
typedef QLinkedList<Particle*> ParticlesList;

Neighbours neighbours = m_cell->getNeighbourhood();
Neighbours::const_iterator it;

for (it = neighbours.begin(); it != neighbours.end(); ++it) 
{
    ParticlesList* parts = (*it)->getParticles();
    for (ParticlesList::const_iterator itp = parts->begin(); itp != parts->end(); ++itp)
    {
        double d = distanceTo(*itp); // computes sqrt(x^2 + y^2)
        if(d>=0 && d<=m_maxForceRange)
        {
            particleIsClose(d, *itp); // just changes 
        }
    }
}

And just to make sure I'm complete, this whole code is called in a loop ^^.

So yes the list is modified and it is in a inner loop. So there's no way to precompute the beginning and end of it.

And moreover, the list needs to be constructed at each big iteration (I mean in the topmost loop) by inserting one by one.

Debug mode

Yes indeed I profiled in Debug mode. And I think the remark was judicious because the code went 2x faster in Release. And the problem with lists disappeared.

Thanks to all for your answers and sorry for this ^^

Answer 1

If you are profiling in debug mode, a lot of compilers disable inlineing. The begin() and end() times being high may not be "real". The method call times would be much higher than the equivalent inline operations.

Something else I noticed in the full code, you're doing a sqrt in the inner loop. They can be fairly expensive depending on the hardware architecture. I would consider replacing the following code:

 double d = distanceTo(*itp); // computes sqrt(x^2 + y^2) 
 if(d >= 0 && d <= m_maxForceRange) 

with:

 double d = distanceToSquared(*itp); // computes x^2 + y^2
 if(d >= 0 && d <= m_maxForceRangeSquared)

I've done this in code where I was doing collison detection and it sometimes makes a noticible improvement. The tests are equivalent and saves a lot of calls to sqrt. As always with optimization, measure to verify if it improves the speed.