Понимание детализации при сравнении двух разных реализаций алгоритма BFS
Приведенные ниже результаты измеряются с использованием perf на вычислительном сервере с 32 ядрами. Я знаю, что моя реализация неоптимизирована, но нарочито, поскольку я хочу провести сравнение. Я понимаю, что графовые алгоритмы имеют тенденцию иметь низкую локальность, к которой пытаются обратиться исследователи.
Я не уверен в результатах, хотя. Прошедшее время вводит в заблуждение. Моя реализация проходит через граф с примерно 4-миллиметровыми узлами примерно за 10 секунд, а остальное время - до обработки. Оптимизированная версия использует одни и те же входные данные и проходит около 10 раз, каждая из которых занимает менее секунды, поэтому на самом деле это просто время предварительной обработки. Я не пытаюсь достичь того же. Просто поймите, почему это может быть основано на перф.
Я вижу, что ошибки моей страницы значительно выше. Я не уверен, почему это так, поскольку аннотации (насколько я могу судить) не указывают на какой-либо конкретный фрагмент моего кода из моего...
__gnu_cxx::new_allocator<std::_List_node<int> >::construct<int, int const&>
Это происходит, когда я обрабатываю сам график, так как я создаю связанные списки для списков смежности. Я подумал, что это может вызвать проблемы, и все равно хотел провести расследование. Я должен быть в состоянии улучшить ошибки страниц (и, надеюсь, производительность), переключаясь на неровные массивы?
Оптимизированный алгоритм имеет гораздо более высокую пропускную способность кэш-памяти последнего уровня, что, как я думал, объясняет основную проблему с алгоритмами BFS / graph с низкой локальностью, но это, похоже, не влияет на производительность, и моя неоптимизированная значительно ниже.
Кроме того, существуют циклы переднего / заднего плана, которые кажутся противоположными с точки зрения проблем производительности при сравнении этих двух - у меня хуже во внешнем интерфейсе, а оптимизированный хуже у внутреннего.
Я упускаю или не понимаю что-то очевидное? Я подумал, что с точки зрения низкой локальности будет что-то очевидное, что может иметь значение при взгляде на perf, но меня смущает оптимизированная версия.
Это моя реализация неоптимизированной параллельной BFS (запускается один раз)...
Это использует оптимизированный параллельный BFS из набора тестов (работает 10 раз)...
Оба требуют около 40 секунд для предварительной обработки данных один раз, прежде чем выполнять параллельный поиск.
1 ответ
К несчастью perf stat часто не дают достаточно информации, чтобы действительно определить узкое место в вашем приложении. Можно иметь два приложения с сильно различающимися узкими местами, но с очень похожими perf stat профили. Например, два приложения могут иметь одинаковое количество или долю пропусков в кеше L2, и, тем не менее, в одном из них может преобладать этот эффект, а на другой способ может почти не оказываться влияние, в зависимости от объема и характера перекрывающихся работ.
Поэтому, если вы попытаетесь провести глубокий анализ с этих высокоуровневых счетчиков, вы часто просто наносите удары в темноте. Тем не менее мы можем сделать несколько замечаний. Вы упоминаете:
Оптимизированный алгоритм имеет гораздо более высокую пропускную способность кэш-памяти последнего уровня, что, как я думал, объясняет основную проблему с алгоритмами BFS / graph с низкой локальностью, но это, похоже, не влияет на производительность, и моя неоптимизированная значительно ниже.
Во-первых, потери LLC составляют ~620 миллионов для оптимизированного алгоритма и ~380 для вашего алгоритма, но в этом тесте оптимизированный алгоритм выполняется 10 раз, а ваш - только один раз. Таким образом, оптимизированный алгоритм имеет, возможно, 62 миллиона промахов, а ваш алгоритм в шесть раз превышает количество промахов LLC. Да, ваш алгоритм имеет более низкий коэффициент пропусков LLC, но абсолютное количество пропусков LLC - вот что имеет значение для производительности. Более низкий уровень пропусков означает, что вы совершаете все больше общих обращений, чем в 6 раз: в основном вы делаете гораздо больше обращений к памяти, чем в оптимизированной версии, что приводит к более высокому числу обращений, но к большему количеству промахов.
Все это указывает на доступ к большему объему памяти в вашем неоптимизированном алгоритме, или, возможно, на доступ к нему в гораздо более кеш-памяти. Это также объясняет гораздо большее количество ошибок страниц. В целом, оба алгоритма имеют низкий IPC, а ваш - особенно низкий (0,49 IPC), и, учитывая, что нет проблем с предсказанием ветвлений, и что вы уже определили их как графовые алгоритмы с проблемами доступа к локальности / памяти, задержки в ожидании память очень вероятна.
К счастью, есть лучший способ - просто перепроектировать то, что может быть узким местом на основе perf stat выход. Корпорация Intel разработала целую методологию, которая пытается выполнить этот тип нисходящего анализа таким образом, чтобы определить истинные узкие места. Это не идеально, но гораздо лучше, чем смотреть на равнину. perf stat счетчики. VTune не бесплатен, но вы можете получить аналогичный анализ, основанный на том же методологическом эффекте, используя топлев Энди Клин. Я настоятельно рекомендую вам начать там.