Ответ 1
Такое большое различие является произведением двух условий.
первое условие связано с исходным кодом. Слияние на месте настолько эффективно, что было бы трудно разработать что-либо значительно быстрее, даже если кодирование выполняется вручную на уровне ассемблера. Применение дженериков является простым, поэтому компилятор ** создал ту же самую сборку с ней или без нее. Поскольку реализация алгоритма эффективна, только несколько машинных команд, добавленных в цикл, способны производить значительное пропорциональное изменение, указанное в вопросе.
** Специфика компиляции во всем этом ответе использовала g++ 6.2.1 20160916, пакет Fedora 24 dnf по умолчанию, а также ядро LINUX 4.8.8-200.fc24.x86_64. Runtime был кеш Intel i7-2600 8M. Также для Atmel SAM3X8E ARM Cortex-M3 с arm-none-eabi-g++ 4.8.3-2014q1.
второе условие связано с компиляцией второго трюка, описанного в пункте 3 предложения 2 вопроса. Первый трюк, сокращение типов в шаблоне, не вызвал существенных изменений в языке ассемблера. Второй трюк вызвал разницу уровня сборки на выходе на выходе из компилятора для двух вызовов.
Этот прекомпилятор взлома может облегчить тестирование.
#ifdef ORIG
#define half_inplace_merge half_inplace_merge_orig
#else // ORIG
#define half_inplace_merge half_inplace_merge_slow
#endif // ORIG
...
half_inplace_merge(niInA.begin(), niInA.end(),
niInB.begin(), niInB.end(),
niOut.begin(), compare);
Выполнение и сравнение с помощью этих команд в оболочке bash использует взлом прекомпилятора.
g++ -DORIG -S -fverbose-asm -o /tmp/qq.orig.s /tmp/qq.cpp
g++ -DSLOW -S -fverbose-asm -o /tmp/qq.slow.s /tmp/qq.cpp
araxis.sh /tmp/qq.orig.s /tmp/qq.slow.s # to run Araxis Merge in Wine
Эти инструкции являются результатом инициализации хранилища InputIterator [], но это вне цикла.
leaq -48(%rbp), %rax #, _4
movq -64(%rbp), %rdx # first1, tmp104
movq %rdx, (%rax) # tmp104, *_5
leaq 8(%rax), %rdx #, _9
movq -96(%rbp), %rax # first2, tmp105
movq %rax, (%rdx) # tmp105, *_9
Первичное замедление происходит при разыменовании двух элементов, содержащихся в хранилище [], при необходимости с помощью сравнения и свопинга, и это находится в цикле. Эти инструкции не существуют в версии без второго трюка.
movb %al, -17(%rbp) # _27, cmp
movzbl -17(%rbp), %eax # cmp, _29
cltq
...
movzbl -17(%rbp), %edx # cmp, _31
leaq -48(%rbp), %rax #, tmp121
movslq %edx, %rdx # _31, tmp122
salq $3, %rdx #, tmp123
addq %rdx, %rax # tmp123, _32
Хотя в телах условного для версии без трюка есть дублирование кода, это влияет только на компактность кода, добавляя два вызова, пять ходов и одну команду сравнения. Количество циклов ЦП, необходимых для выполнения слияния на месте, одинаково между ветвями, полученными в результате сравнения, и обе им не имеют инструкций, перечисленных выше.
Для каждой из нескольких попыток синтаксиса, попытка удаления избыточности в ветвях для повышения компактности неизбежно приводит к дополнительным инструкциям, требуемым вдоль пути выполнения.
Детали последовательности команд для различных перестановок, обсуждаемых до сих пор, будут варьироваться от компилятора к компилятору, выбора опций оптимизации и даже условий вызова функций.
Теоретически возможно, чтобы компилятор использовал правило рефакторинга AST (абстрактное дерево символов) (или эквивалент) для обнаружения и сокращения требований к программной памяти и циклу процессора для любой версии функции. Такие правила имеют антецеденты (шаблоны поиска), которые соответствуют шаблону, который должен быть оптимизирован в коде.
Оптимизация скорости для кода со вторым трюком потребует антецедента правила, который соответствует абдикции атипичной оценки [] как внутри, так и снаружи цикла. Обнаружение избыточности ветки без второго трюка является более разумной целью.
Интегрируя два оператора в каждой ветки, можно увидеть, как два одинаковых шаблона в AST могут быть достаточно простыми, чтобы антецедент рефакторинга соответствовал и выполнял требуемое уменьшение размера кода. Было бы очень мало скорости в этом случае, если таковые имеются.
if (compare(*first2, *first1)) {
std::iter_swap(result, first2 ++);
} else {
std::iter_swap(result, first1 ++);
}