Я работал над проектом и пытался найти источник большого замедления во времени выполнения и сузил его до одного метода, который мне удалось оптимизировать из логики. Проблема заключается в том, что мое решение заключается в использовании ссылки, которая заставляет другую часть кода работать довольно медленно ... Вопрос, на который я хотел бы ответить, заключается в том, почему внутренний цикл требует гораздо больше времени для оценки, когда карта является ссылкой, а не локальная переменная?
Вот старый способ до оптимизации:
// old method: create an empty map, populate it
// and then assign it back to the path object later
map<int,float> screenline_usage;
for (int i=0; i<numCandidates; ++i)
{
// timing starts here.
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[it->first] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~12 seconds
}
// This function call is evaluated 400k times for an overall execution time of ~126 seconds
path->set_zone_screenline_usage(access_mode, zone_id, screenline_usage);
// TOTAL EXECUTION TIME: 138 seconds.
Новый способ после оптимизации:
// new method: get a reference to internal path mapping and populate it
map<int, float>& screenline_usage =
path->get_zone_screenline_usage(access_mode, zone_id);
screenline_usage.clear();
for (int i=0; i<numCandidates; ++i)
{
// timing starts here
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[it->first] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~76 seconds
}
// New method... no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: 76 seconds (62 second time saving) ... but should be able to do it in just 12 seconds if the use of reference didn't add so much time :(
Вот соответствующие подпрограммы, вызываемые из этого кода:
// This is the really slow routine, due to the copy assignment used.
void set_zone_screenline_usage(int access_mode, int zone_id,
map<int,float>& screenline_usage)
{
m_container[access_mode][zone_id] = screenline_usage;
}
map<int,float>& get_zone_screenline_usage(int access_mode, int zone_id)
{
return m_container[access_mode][zone_id];
}
ПРИМЕЧАНИЯ. Информация о времени предназначена для одного прогона, в котором приведенный выше код оценивается примерно 400 000 раз. Синхронизация выполняется с использованием некоторых классов, которые я создал для доступа к счетчику меток времени RDTSC (да, я знаю, что TSC означает счетчик меток времени), среднее значение numCandidates равно 10, а среднее число элементов, помещенных в карту screenline_usage, равно 25.
ОБНОВЛЕНИЕ: Во-первых, спасибо всем, кто принял участие здесь. Я думаю, что, в конце концов, это вообще не имело никакого отношения к ссылкам на c ++ и было связано с согласованностью кэша. Я заменил приведенный выше оптимизированный код на вектор & и хеш-функцию, реализованную в виде карты переменных-членов
// newest method: get a reference to internal path mapping (as vector) and populate it
// map<int,int> m_linkNum_to_SlNum declared in header and populated in constructor.
vector<float>& screenline_usage = path->get_zone_screenline_usage(access_mode, zone_id);
for (int i=0; i<numCandidates; ++i)
{
// timing starts here
map<int, float>& my_screenline_usage =
path->get_combined_screenline_usage(legnr, stop_id);
map<int, float>::iterator it = my_screenline_usage.begin();
for (; it != my_screenline_usage.end(); ++it)
screenline_usage[m_linkNum_to_SlNum[it->first]] += usage * it->second;
// timing ends here, this block evaluated 4 million times for overall execution time of ~9 seconds
}
// Newest method... again no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: just 9 seconds (129 second time saving) ... this is even better than using a locally constructed map which took 12 seconds in the inner loop :)
Здесь мне кажется, что, учитывая, что вектор не является локальным, но является непрерывным блоком памяти и что хеш-функция (m_linkNum_to_SlNum) является локальной переменной-членом, этот подход приводит к коду / данным, которые способны помещается в кэш без необходимости выходить в основную память для данных, что приводит к значительному ускорению. Другие выводы, сделанные с учетом этих выводов, высоко ценятся.