Оптимизация -OG снижает быстродействие

[Mazdaywik]

Проблема

Скопирую текст из комментария #319 (comment):

Сделаны замеры для режимов -OiDPRS, -OiADPRS, -OiDGPRS и  -OiADGPRS. Выполнялось 17 проходов с пустым BENCH_FLAGS. Компиляция выполнялась в режимах

set RLMAKE_FLAGS=-X-OiDPRS -X--opt-tree-cycles=300
set RLMAKE_FLAGS=-X-OiADPRS -X--opt-tree-cycles=300
set RLMAKE_FLAGS=-X-OiDGPRS -X--opt-tree-cycles=300
set RLMAKE_FLAGS=-X-OiADGPRS -X--opt-tree-cycles=300

Результаты замеров (сырые)

• benchmark-iDPRS-22.11.2020-14-02-21,37_time.txt
• benchmark-iDPRS-22.11.2020-14-02-21,37_profile_count.txt
• benchmark-iDPRS-22.11.2020-14-02-21,37_profile_time.txt
• benchmark-iADPRS-22.11.2020-14-20-21,61_time.txt
• benchmark-iADPRS-22.11.2020-14-20-21,61_profile_count.txt
• benchmark-iADPRS-22.11.2020-14-20-21,61_profile_time.txt
• benchmark-iDGPRS-22.11.2020-14-46-00,02_time.txt
• benchmark-iDGPRS-22.11.2020-14-46-00,02_profile_count.txt
• benchmark-iDGPRS-22.11.2020-14-46-00,02_profile_time.txt
• benchmark-iADGPRS-22.11.2020-15-42-32,97_time.txt
• benchmark-iADGPRS-22.11.2020-15-42-32,97_profile_count.txt
• benchmark-iADGPRS-22.11.2020-15-42-32,97_profile_time.txt

Запись M [L…R] далее будет обозначать медиану и доверительный интервал в секундах. Далее будет рассматриваться только метрика (Total refal time).

• Режим -OiDPRS: 15,637 [15,543…15,873], число шагов 19 659 968. Будет принят за основу.
• Режим -OiADPRS: 14,266 [14,161…14,383], число шагов 16 613 321. По времени ускорение на 8,7 %, достоверное. Число шагов уменьшилось на 15,5 %.
• Режим -OiDGPRS: 16,316 [16,263…16,386], число шагов 19 657 383. Парадоксально по времени замедление на 4,3 %, достоверное. Число шагов уменьшилось на 0,01 %.
• Режим -OiADGPRS: 14,757 [14,717…15,025], число шагов 16 521 884. Ускорение по времени на 5,6 %, достоверное. Число шагов уменьшилось на 15,9 %.

Парадоксально, но добавление опции -OG достоверно замедляет программу! Действительно:

• -OiDPRS → -OiDGPRS, замедление на 4,3 %, достоверное (доверительные интервалы [15,543…15,873] и [16,263…16,386] соответственно), число шагов уменьшилось на 2585 или 0,01 %
• -OiADPRS → -OiADGPRS, замедление на 3,4 %, достоверное ([14,161…14,383] и [14,717…15,025]), число шагов уменьшилось на 91 437 или на 0,55 %.

Добавлю, что замер выполнялся на коммите 672af49.

Сделаны замеры на машине Intel® Core™ i5-2439M CPU @ 2.40 GHz, оперативная память DD3 8,0 Гбайт, ОС Windows 10 x64, компилятор Си++ — BCC 5.5.1. Кэши процессора L1 128 Кбайт, L2 512 Кбайт, L3 3,0 Мбайт.

Почему это странно

Потому что оптимизация -OG в рассматриваемой программе не должна давать ничего. Или, почти ничего. По крайней мере в режиме -OiDGPRS. Для этого в программе должны быть entry-функции, имеющие метки оптимизации, а такая только одна — EscapeChar в src/common/Escape.ref. И, по-видимому, она сократила число шагов на 2582 или 0,01 %.

Сейчас, благодаря $INCLUDE "LibraryEx";, в каждый файл включаются определения функций Map, MapAccum и Reduce, благодаря чему они могут специализироваться. В будущем планируется (#318) выкинуть возможность включения файлов, а значит, Map и др. будут оптимизироваться только в режиме глобальной оптимизации. Но это к делу сейчас не относится.

Т.е. флаг должен быть совершенно нейтральным, т.е. на быстродействие построенных программ не должен влиять измеримо никак. Но он достоверно (доверительные интервалы не пересекаются) снижает быстродействие на 4,3 %!

Возможная причина

Без режима -OG файлы транслируются независимо, файлы с интерпретируемым кодом конкатенируются в один. В режиме -OG синтаксические деревья объединяются, полученный файл транслируется в один .rasl (или один .cpp, но это нас сейчас не интересует).

Преобразования и над отдельными синтаксическими деревьями единиц трансляции, и над объединённым деревом, семантически одни и те же. (Во втором случае должна, однако, прогнаться EscapeChar, но это пустяки.)

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

И это единственная гипотеза, которая пока приходит мне на ум. Вся программа целиком в кэш не влезает (объём файла, построенного в режиме -OiADGPRS — 3743 Кбайта), а кэш любит локальность. Поэтому в первом случае (экземпляры не далеко от точки вызова) участок кода целиком влезает в кэш и интерпретируется быстро. Во втором случае (экземпляры далеко от точек вызова) при переходе на экземпляр и обратно интерпретируемый код оказывается не в кэше и запрос делается в оперативную память, что медленнее. А ведь в кэш, помимо кода, должно влезать и некоторое подмножество узлов поля зрения.

(Есть ещё и буфер TLB, который тоже любит локальность, и он тоже может влиять. Но у него влияние в целом похожее на кэш, поэтому их можно смешать при рассмотрении.)

Гипотезу можно проверить двумя способами:

• Протестировать на компьютере с другим объёмом кэша. У меня есть нетбук с процессором Intel Atom, скорее всего, у него кэш меньше (надо смотреть). На компьютере с меньшим объёмом кэша процентная разница в производительности должна быть меньше.
• Изменить алгоритм порождения экземпляров, чтобы те размещались не в конце дерева, а рядом с точкой вызова. В этом случае деревья при раздельной трансляции и объединённой будут больше похожи по структуре, а значит, процентная разница должна быть на уровне статистической погрешности.

Если гипотеза окажется верна, то второй пункт ↑ может также незначительно поднять быстродействие. Кроме того, измеримо поднять быстродействие сможет и удаление неиспользуемых функций (#228) — семантически совершенно нейтральная операция.

И ещё. Если гипотеза окажется верна, то выявится влияние очень низкого уровня на производительность высокоуровневого языка. Это немного удивительно.

[Mazdaywik]

Был сделан замер на нетбуке с процессором Intel® Atom™, ОЗУ 2 Гбайта, Windows 7 x32. Характеристики процессора:

D:\>wmic cpu get Name, L2CacheSize, L3CacheSize
L2CacheSize  L3CacheSize  Name
512          0            Intel(R) Atom(TM) CPU N270   @ 1.60GHz

Команда wmic не показывает размер кэша L1, кэш L3 на этой машине отсутствует.

Было выполнено два замера, каждый по 9 проходов. Первый:

set RLMAKE_FLAGS=-X-OiDPRS -X--opt-tree-cycles=300

Второй:

set RLMAKE_FLAGS=-X-OiDGPRS -X--opt-tree-cycles=300

Оба с set BENCH_FLAGS=-OP — то, что она была установлена, я узнал только на середине первого замера.

Сырые данные

• benchmark-iDPRS-24.11.2020-22-25-19,85_time.txt
• benchmark-iDPRS-24.11.2020-22-25-19,85_profile_count.txt
• benchmark-iDPRS-24.11.2020-22-25-19,85_profile_time.txt
• benchmark-iDGPRS-25.11.2020- 0-13-21,83_time.txt
• benchmark-iDGPRS-25.11.2020- 0-13-21,83_profile_count.txt
• benchmark-iDGPRS-25.11.2020- 0-13-21,83_profile_time.txt

Результаты:

• -OiDPRS: 79,608 [79,482…79,895].
• -OiDGPRS: 76,487 [75,737…76,719], ускорение на 3,9 %, достоверное.

Всё чудесатее и чудесатее

Вопреки ожиданиям на этой машине получилось не большее замедление, а наоборот ускорение! Причём достоверное. Как это можно объяснить — я не знаю!

Надо проверить другое следствие из исходной гипотезы: размещение экземпляров рядом с вызовами должно нивелировать разницу в производительности. И проверить опять на обоих машинах.

---

UPD: Бенчмарк выполнялся с вот таким [email protected]:

print-statistics = true
enable-profiler = true

Т.е. профилировщик был включён. Это тоже могло как-то повлиять на результат. Надо перемерять…