C++ производительность вложенного цикла

Question

У меня есть в основном два вектора один для большого количества элементов и второй для небольшого числа зондов, используемых для выборки данных элементов. Я наткнулся на вопрос, в каком порядке реализовать эти два цикла. Естественно, я думал, имея внешний контур над большей вектор будет выгодно

Осуществление 1:

for(auto& elem: elements) { 
    for(auto& probe: probes) { 
     probe.insertParticleData(elem); 
    } 
} 

Однако, кажется, что вторая реализация занимает лишь половину времени

Реализация 2 :

for(auto& probe: probes) { 
    for(auto& elem: elements) { 
     probe.insertParticleData(elem); 
    } 
} 

Что может быть причиной этого?

Edit:

Задержки были получены с помощью следующего кода

clock_t t_begin_ps = std::clock(); 
... // timed code 
clock_t t_end_ps = std::clock(); 
double elapsed_secs_ps = double(t_end_ps - t_begin_ps)/CLOCKS_PER_SEC; 

при вставке данных элементов я в основном две вещи, проверяя, если расстояние до зонда находится ниже предела и вычисление в среднем

probe::insertParticleData (const elem& pP) { 
    if (!isInside(pP.position())) {return false;} 
    ... // compute alpha and beta 
    avg_vel = alpha*avg_vel + beta*pP.getVel(); 
    return true; 
} 

Чтобы получить представление об использовании памяти, у меня есть ок. 10k элементов, которые представляют собой объекты с 30 двойными элементами данных. Для теста я использовал 10 зондов, содержащих 15 удвоений.

Answer 1

Мое предположение: Если insertParticleData является виртуальным, компилятор будет обрабатывать адрес функции как константу во внутреннем цикле и перемещать выборку vtable вне внутреннего цикла. I.e. эффективно генерировать код, который выглядит как:

for (auto& probe: probes) { 
     funcPtr p = probe.insertParticleData; 
     for (auto& elem: elements) { 
     (*p)(elem); 
     } 
    } 

, тогда как в первом варианте, р будет вычислен для каждой внутренней итерации.

Answer 2

Сегодняшние процессоры сильно оптимизированы для линейного доступа к памяти. Поэтому несколько длинных циклов будут бить много коротких петель. Вы хотите, чтобы внутренний цикл повторялся по длинному вектору.