The fastest way to iterate over a collection of objects

Question

First, let’s give you a few prerequisites: I have some kind of research code that performs Monte Carlo simulations, what’s important is what it takes to iterate through a set of objects, calculate a series of vectors from their surface, and then for each vector I iterate through collect objects again to see if the vector falls into another object (similar to ray tracing). The pseudocode will look something like this.

for each object { for a number of vectors { do some computations for each object { check if vector intersects } } } 

Since the number of objects can be quite large and the number of rays even larger, I thought it would be wise to optimize how I repeat the collection of objects. I created some test code that tests arrays, lists, and vectors, and for my first test cases, I found that vector iterators were about twice as fast as arrays, however, when I implemented the vector in my code, it was slightly slower than the array I used before.

So, I went back to the test code and increased the complexity of the object function that each loop called (a dummy function equivalent to "check if the vector intersects"), and I found that when the complexity of the function increases the execution time, the gap between arrays and vectors decreases to those until eventually the array becomes faster.

Does anyone know why this is happening? It seems strange that the runtime inside the loop should affect the runtime of the outer loop.

Answer 1

What you are measuring is the difference in overhead for accessing an element from an array and a vector. (as well as their creation / modification, etc.) depending on the operation you are performing).

EDIT: It will vary depending on the / os / library platform used.

Answer 2

This probably depends on the implementation of vector iterators. Some implementations are better than others. (Visual C ++ - at least older versions - I'm looking at you.)

Answer 3

I think the time difference that I observed was actually related to an error in the pointer processing code. Having made several modifications to make the code more readable, iterations took time (give or take 1%) regardless of the container. This makes sense, since all containers have the same access mechanism.

However, I noticed that the vector works a little slower in the OpenMP architecture, this is probably due to the overhead in each thread supporting its own copy of the iterator.