Стиль: Вы могли бы легко дать вашим меткам цикла значимые имена, например copy_search: и outer:
У вас есть Major пропущенные оптимизации, так что да, естьнекоторые вещи, которые помогут.
(Так как это домашняя работа, я просто собираюсь описать их, а не реализовывать их. Как бы заманчиво ни было бы написать мою собственную реализацию, тогда мне пришлось быотладка. Использование real было бы довольно ограниченным. Современная сортировка на x86 для коротких массивов (например, в качестве базового варианта для MergeSort или QuickSort) - это сеть сортировки SIMD SSE2 или AVX2.с использованием случайных чисел и упакованных инструкций min / max. Я думаю, что сортировка по ветвям обычно не лучший выбор в x86 asm, даже для крошечных массивов, таких как 3 или 4 элемента длиной: тогда вы, вероятно, просто захотите какой-нибудь скалярный код без ветвей.1013 * Самый простой способ получить лучший asm - переписать на C и скомпилировать его с включенной оптимизацией.В целом это хорошая идея, чтобы получить идеи о том, как оптимизировать: даже если вы являетесь экспертом в оптимизации asm, компилятор может подумать о том, чего вы не сделали.Использование вывода компилятора в качестве отправной точки для настройки, как правило, хорошо.
Задача halfpoint - это задача для вас решить, как это сделать дешево, без пересчета длины массива во внешнем цикле.Подсказка: сортировка вставки даже не смотрит на элементы за пределами уже отсортированной области внизу и на следующий элемент, который нужно вставить, независимо от конечного условия остановки, которое вы передаете как длину.Полное исключение этого условия из цикла, вероятно, является единственной алгоритмической оптимизацией;остальное - просто эффективная реализация Insertion Sort в asm.
(В общем случае для циклически инвариантных условий внутри циклов вы можете сделать 2 версии цикла и ветви, чтобы выбрать, какой из них запускать. Но здесьмы можем просто настроить входы цикла сортировки перед его запуском.)
Одна из наиболее очевидных оптимизаций - это Почему циклы всегда компилируются в стиле "do ... while" (прыжок с хвоста)? - используйте sub edi,4 / jnz copy_search_loop в нижней части внутреннего цикла.
Другой способ - загрузить элемент, который нужно сравнить и скопировать в регистр, чтобы вы моглине нужно загружать его дважды.
Это немного поможет, но на современном x86 не так уж много.Повторные загрузки, которые попадают в кэш L1d, дешевы.Intel и AMD могут выполнять 2 операции с памятью за такт, до 1 из которых является магазин.Вы используете режимы индексированной адресации для магазинов, поэтому Intel Haswell и более поздние версии не могут использовать выделенный AGU для простых хранилищ на порту 7 , в противном случае он может выполнять 2 загрузки + 1 сохранение в такт.
После исправления внутренней петли, чтобы избежать jmp (всего один провал jcc и sub / jcc внизу), ваша петля должна быть только 4 моп в Haswell ипозже (mov-load, макрос-слитый cmp / jcc, mov-store, макрос-слитый sub / jcc).В зависимости от того, как он декодирует, одна из ветвей может не слиться с макроблоком в Sandybridge.(SnB / IvB не может сделать 2 слияния в одной группе декодирования до 4 мопов, которые попадают в декодирование в одном и том же цикле).Таким образом, с регистром cmp/jcc вместо памяти, внутренний цикл может выполняться с 1 итерацией за такт (если он не ошибается).
Если после оптимизации осталось cmp reg, 0чтобы использовать флаги, установленные sub или dec, , оптимизируйте их до test reg,reg, что на 1 байт короче, но в остальном практически равноценно.(И все флаги устанавливаются одинаково, кроме AF, на который нельзя переходить).
Скорее всего, в массиве будет только 20 элементов.Может быть, до 30.
И он будет работать несколько тысяч раз, я думаю, с одним и тем же массивом, я думаю.
Хорошо, это означает, что предсказание ветвления может «выучить» шаблонветвление для небольших сортировок, повторное выполнение функции для одних и тех же данных.
Это означает, что настройка асма может иметь значение.При использовании рандомизированных данных большая часть выигрыша будет уменьшена из-за количества циклов, которые ЦП тратит на восстановление после неправильных прогнозов ветвлений.Конечно, более эффективный код может позволить ему быстрее обнаруживать неправильные прогнозы, и просто прожевать работу, пока следующий неверный прогноз не станет немного быстрее.Современные процессоры уже очень хорошо разбираются с помощью избыточных инструкций (при условии, что они не сильно увеличивают задержку критического пути), потому что большая часть машинного кода, который выполняется на современных процессорах, создается компиляторами JIT в JVM и аналогичных имне очень хорошо оптимизированы.
Для сортов размером 20 или 30 цикл поиска копии будет запускать несколько итераций довольно много раз (если входные данные уже близки к сортировке), поэтому предположительно его ветви обычноправильно предсказать, как продолжать цикл.И его оптимизация для выполнения меньших нагрузок и выполнения меньшего количества инструкций для случая с непрерывным поиском действительно должна помочь.
Помните, оптимизируйте свой код для общего случая.Для циклов это обычно означает быстрое выполнение дела «Keep looping».Это означает, что иногда стоит пролить (сохранить что-то в памяти) что-то вне цикла, чтобы освободить больше регистров для использования внутри цикла.
Еще один способ сохранить регистрыиспользовать приращение указателя вместо base + index. Или оставить некоторые данные только для чтения в памяти, особенно если вы читаете их только один раз за итерацию внешнего цикла.Например, условие внешнего цикла может быть cmp [end_pointer], esi / jb.
Для не крошечных массивов: векторизовать цикл поиска копии с помощью SSE2 или AVX2
(И, возможно,для небольших, если вы можете сделать накладные расходы достаточно низкими, нижний предел - это когда большинство элементов вставляются в 3 элемента конца отсортированной области, или, если накладные расходы выше, требуется больший средний размер копии, чтобы оно того стоило.)
Для более крупных сортировок Insertion Sort будет тратить много времени на копирование массива по 1 элементу за раз.т. е. внутренний цикл часто выполняет много итераций.Мы можем многого добиться, векторизовав его с помощью SSE2 для параллельного копирования и поиска 4 элементов.
// something like this, I haven't checked the logic carefully
movd xmm0, eax ; key
pshufd xmm0, xmm0, 0 ; broadcast the key to all 4 elements: [key, key, key, key]
;; TODO: handle edi not a multiple of 4 somewhere
copy_search:
movdqu xmm1, [esi+edi] ; load 16 bytes
movdqa xmm2, xmm0
pcmpgtd xmm2, xmm1 ; packed xmm2 = key > arr[i + 0..3]
pmovmskb eax, xmm2
test eax, eax
jnz .found_element_less_or_equal_key ; figure out which element from the bitmap, and do something. e.g. movd [mem], xmm0 to store the new element because we destroyed EAX.
movdqu [esi+edi+4], xmm1 ; store after checking, because we might not want to move all 4.
sub esi, 16
jg copy_search
;; else fall through: key goes in one of the first 1 to 3 elements
;; handle the non-multiple-of-4 case here because it's rarely reached
;; and doing it here instead of at the start avoid store-forwarding stalls for short counts
Если входной массив выровнен по 16 байтам, обрабатывается случай не кратный 4перед входом в цикл поиска копии заманчиво.Тогда все нагрузки могут быть выровнены.(Хотя хранилища все равно будут смещены, так что, может быть, даже обработать их так, чтобы вместо них были выровнены хранилища?) Но современные процессоры имеют эффективную обработку невыровненной нагрузки, и разбиение строк кэша не является слишком дорогим.Разделение страниц (через границу 4 Кб) очень дорого для Intel до Skylake.(Например, ~ 100 дополнительных циклов по сравнению с той же стоимостью, что и при разделении строк кэша).
Но если вы не можете сделать это очень дешево, избегайте этого полностью большую часть времени (кроме случаев, когда цикл поиска копии достигаетв самом начале массива), вероятно, является победой.
Условие завершения цикла не может быть таким простым, как i > 0, потому что нам нужно избегать уменьшения на 4 элемента, выходящих из началамассив. Но, смещая esi (основание массива), мы все равно можем справиться с этим, используя только sub/jcc в качестве условия цикла, не требуя sub и затем cmp/jcc против указателя.(Но если настраивать IvyBridge или Sandybridge, вероятно, стоило бы использовать приращение указателя, чтобы хранилище могло оставаться слитым. AMD не может слить sub/jcc, так что только в Haswell + эта индексированная адресация и sub/jge на самом деле, вероятно, самый оптимальный способ (без развертывания))
Это должно избежать остановок при пересылке из магазина, потому что мы записываем память после , которую мы загрузили из нее.Перекрытие от +4 (1/4 от вектора) относится к предыдущему чтению, а не к следующему чтению.Даже для небольших сортировок мы не должны получать киоски пересылки магазина: следующая внешняя итерация перезапустит внутренний цикл, выровненный по позиции, в которой мы его написали.
Но накладные расходы на обработку не кратных 4 и не превышающих начало массива повредят для небольших сортировок, потому что реальный векторный цикл выполняется всего несколько итераций.