(Speed) оптимизация, влияющая на неожиданный раздел кода

Question

Я делаю оптимизацию скорости на своем собственном коде. ПСЕВДОКОД что-то вроде этого:

1. myStructure = constructStructure (param1) 
2. processStructure(myStructure) 
3. myStructure = constructStructure (param2) 
4. processStructure(myStructure) 

я была сосредоточена на оптимизации функции constructStructure(param) начиная двух вызовов функции занимают около 75% времени. Я не касался функцииprocessStructure(structure).

я получил хорошую скорость вверх (все это в настоящее время принимает около 75% оригинального времени), но когда я измерил соответствующие времена операций 1.-4. я получил неожиданные результаты:

 before  after 
1. 75.10ms  56.88ms 
2. 23.12ms  19.32ms 
3. 70.72ms  53.22ms 
4. 20.81ms  14.45ms 

Я получил (небольшое, но) значительное ускорение в частях 2. и 4., которые не были изменены! Это измеряется на 1000 пробегах и затем усредняется. (Я не вычислял стандартное отклонение, но я запускал и показывал отдельные времена 20-их раз для каждого варианта, и это, похоже, соответствует средним значениям).

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

Отсутствие (существенное) утечки памяти Насколько я могу судить - я наблюдал за своей системной памятью во время тестовых прогонов и не было постоянного увеличения используемой памяти. (Я знаю, что это не очень хороший способ проверить это, и впасть в потенциальную утечку памяти - это моя следующая остановка. Кроме того, я действительно хочу освободить/удалить всю зарезервированную память, как только это мне не понадобится) ,

Не то, чтобы я не был доволен скоростью, , но я даже не могу понять, что произошло! Поскольку это код, который я буду использовать некоторое время после того, как я закончу работу над ним, наличие в коде кода тайн не является привлекательным вариантом.

Кто-нибудь есть какие-либо идеи относительно того, что случилось и как я могу проверить, если то, что вы предлагаете действительно так? PS. Я работаю в C++.

---

Как фактический код слишком велик, чтобы поместить здесь (100 линий для изготовления структуры + 300 строк для его обработки), я могу описать его немного, а также описывающее изменение:

constructStructure

это функция построения дерева структуру (не бинарное дерево) (на основе полутоновых пикселей изображения), Whe re каждому узлу присваивается атрибут int.

Параметр функция constructStructure является Comparator, указывающий порядок интенсивностей пикселей (первый раз это less<int>(), второй раз greater<int>()).

только изменение в оптимизированной процедуры с использованием std::priority_queue вместо std::multimap реализовать кучи структуры (как описано в this question of mine - за исключением того, что не используется с std::pair<int,int>, но вместо этого на std::pair<int,myData>)

Я подтвердил, что произведенный myStructure является эквивалентом Дерево (путем изучения полученного дерева для разных изображений) в некотором смысле:

• полученное дерево имеет число узлов
• данных, содержащиеся в узлах же является же
• но порядок детей в пределах узла отличается при использовании std::multimap, чем при использовании std::priority_queue (дети снова являются узлами, содержащими одни и те же данные)
• заключение: деревья эквивалентны, чтобы данные, которые он хранит и его структура вплоть до порядка дочерних узлов в пределах какого-либо одного родительского узла

processStructure

Это функция, которая исследует построенное дерево, в стиле DFS (снизу вверх). Сложность зависит только от числа узлов в дереве и проверяет только атрибут, назначенный каждому узлу (а не данные, содержащиеся в узле, которые доступны для дальнейшей обработки, не используются здесь).

---

Наконец, после дальнейшего тестирования и различия между порядком узлов я указал, вопрос будет:возможно, что порядок узлов в дереве производит это существенное изменение в производительности, даже если (при обходе дерева с помощью подхода DFS) данные в узлах не проверяются, а только один целочисленный атрибут для каждого узла?

Answer 1

Что можно:

1. Inlining: Может быть, processStructure() и constructStructure() находится в заголовочном файле, или в файле, где вы называете эти functons. Если это так, компилятор может сам встроить код для сохранения в proc-call. Таким образом, это просто эффект макрооптимизации вызовов комбинационных функций.

2. Эффект кеша: возможно, вы используете меньше кода или меньше памяти, а после оптимизации что-то может поместиться в кеш L1/L2.

Предлагаю вам сгенерировать файл сборки для обоих вариантов программы (опция -s для gcc) и сравнить код ассемблера.

Answer 2

Это немного догадка, так как у нас нет кода для просмотра, и для проверки, даже с кодом, потребуется некоторое тщательное изучение, и даже тогда он может работать совершенно по-другому на другом система. Но кэширование и локальность ссылок и переводы виртуальной памяти могут иметь вид существенного влияния производительности, наблюдаемого здесь.

Осмотрите порядок, в котором ваша фаза обработки посещает узлы (то есть в порядке, предзаказ, пост-порядок, случайный, любой). Затем рассмотрите, где каждый из этих узлов мог быть выделен по отношению к другим узлам, которые будут обрабатываться последовательно. Если после посещения одного узла, следующий из них находится очень близко к памяти (особенно в пределах одной и той же линии, но, возможно, также на одной и той же странице виртуальной памяти из-за ограниченных ресурсов TLB), скорее всего, будет быстрее получить доступ, чем который, с точки зрения кеша, находится в довольно случайном месте. Кэши делают что-то вроде предварительной выборки, а это значит, что если доступ к памяти осуществляется в основном линейно, кеш может скрыть большую задержку доступа к основной памяти. В худшем случае, если каждый узел находится в совершенно другой строке кэша, в местоположении без заметного отношения к предыдущему узлу. Есть гораздо больше, что можно сказать о иерархии кеша и производительности виртуальной памяти - на эту тему написаны целые книги.

Я бы предположил, что два разных метода, которые вы используете для построения своего дерева, приводят к значительно различным порядкам распределения узлов в дереве, в результате чего процесс пересечения дерева позже имеет совершенно другой шаблон доступа к памяти, который может вызвать заметные изменения производительности. Я не знаю точно, как вы это сделаете, но если бы вы могли упорядочить все ваши узлы в непрерывном порядке в памяти, в том порядке, в котором вы будете обращаться к ним во время обработки, это будет почти наилучшим образом, и вы может видеть еще большее ускорение, чем вы уже. Обычно вам приходится довольствоваться «достаточно хорошими», особенно если разные входы приводят к значительному различному набору данных.

valgrind имеет модуль cachegrind, который может помочь смоделировать приближение того, как определенная иерархия кэш будет работать с программой - это полезно, чтобы найти некоторые из этих типов различий, хотя это не следует воспринимать как серьезную гарантию производительности, потому что это обязательно более простая модель кэша, чем реальная, и не может учитывать многозадачность, переключатели контекста ядра и т. д.