Cha*_*aal 2 x86 assembly inline-assembly micro-optimization insertion-sort
因此，此插入排序是用x86编写的，但嵌入在C中。它还具有一个标志，在对数组的一半进行排序后，我们将其设置为保留。有什么办法可以提高性能？
void asmInsSort(int *list, int arrayLen, int halfpoint) {
_asm
{
mov ecx, arrayLen
mov esi, list
mov ebx, halfpoint
mov eax, 0
more:
cmp ecx, 0 // Compare current arrayLen w/ 0
je done // If it is equal, we are done
mov edi, eax //J = I
push eax //push eax (i) to free up register for key
mov eax, [esi + edi] //Key = Array[i] technically j
sub edi, 4 //J - 1
mov edx, arrayLen //K = Arraylength
sar edx, 1 //Signed Shift Right K by 1
cmp ecx, edx //IF Arraylength > K
jg cont1 //Jump cont1 hey
cmp halfpoint, 1 //IF halfpoint = 1
je done2 //Exit ELSE cont1
cont1 :
cmp edi, 0 //If j<= 0 exit loop
je cont2
cmp[esi + edi], eax //If Array[J] <= key exit loop
jle cont2
mov edx, [esi + edi] //k = Array[j]
mov[esi + edi + 4], edx //Array[j+1] = Array j
sub edi, 4 //J--
jmp cont1
cont2 :
mov[esi + edi + 4], eax //Array[j+1] = key
pop eax //Pop eax to get i from before for use above
add eax, 4 //Increment i
dec ecx //Decrement ArrayLength
jmp more
done2 : //halfpoint stack reset
pop eax;
done:
}
}
编辑：
所以我以为我正确地优化了：
void asmSort(int *list, int arrayLen, int halfpoint) {
_asm
{
mov ecx, arrayLen // n
mov esi, list
mov ebx, halfpoint // First halfpoint, then j
mov eax, 4 // i = 1
cmp ebx, 1 // if(!halfpoint)
jne main_loop // go to main loop
mov ebx, ecx // else copy arraylen to temp
and ebx, 1 // n%2
shr ecx, 1 // n/2
add ecx, ebx // add two together to get loop amount
main_loop:
cmp ecx, 0 // while n > 0
je end
mov edx, [esi + eax] // key = arr[i]
mov ebx, [eax - 4] // j = i - 1
inner_loop: // while ( j >= 0 && arr[j] > key )
cmp ebx, 0 // (if j < 0, leave)
jl end_inner
cmp [esi + ebx], edx // (if arr[j] <= key, leave )
jle end_inner
mov edi, [esi + ebx] // edi = arr[j]
mov [esi + ebx + 4], edi // arr[j + 1] = edi;
sub ebx, 4 // j = j - 1;
jmp inner_loop
end_inner:
mov [esi + ebx + 4], edx // arr[j + 1] = key;
dec ecx // n--
add eax, 4 // i++
jmp main_loop
end:
}
return;
}
但这根本不起作用。不知道我做错了什么。
样式：您可以轻松地为循环标签赋予有意义的名称，例如copy_search:和outer:
您错过了一些主要的优化，所以是的，有些事情会有所帮助。
（由于这是家庭作业，因此我将仅描述它们，而不是实际实现它们。就像编写自己的实现那样很吸引人，然后我必须对其进行调试。尽管如此，实际用途还是很有限的。在x86上进行短数组排序的最新技术（例如，作为MergeSort或QuickSort的基本案例）是使用shuffle和打包的最小/最大指令的SIMD SSE2或AVX2排序网络，我认为分支排序通常不是最佳选择即使对于像3或4个元素长的微小数组，也可以在x86 asm中进行选择：那么您可能只需要一些标量无分支代码。）
获得更好的asm的最简单方法是用C重写，并在启用优化的情况下进行编译。通常，这是一个很好的想法，以获取如何进行优化的想法：即使您是asm优化的专家，编译器也可能会想到您没有想到的东西。通常使用编译器输出作为调整的起点。
这halfpoint对您来说是一个难题，它解决了如何廉价地做到这一点而又无需重新计算外部循环内的数组长度。提示：插入排序甚至不会查看底部已经排序区域之外的元素以及要插入的下一个元素，而与您作为长度传递的最终停止条件无关。完全取消该条件可能是唯一的算法优化。其余的只是在asm中更有效地实现插入排序。
（在一般情况下，对于循环内部的循环不变条件，您可以制作两个版本的循环和分支以选择要运行的版本。但是在这里，我们可以在排序循环输入开始之前对其进行调整。）
最明显的优化之一是为什么循环总是被编译成“ do ... while”风格（尾跳）？- 在内部循环的底部使用sub edi,4/ jnz copy_search_loop。
另一个是加载要比较的元素并将其复制到寄存器中，因此您不必加载两次。
这会有所帮助，但在现代x86上不是很大。L1d缓存中重复出现的负载很便宜。Intel和AMD都可以每个时钟执行2次内存操作，最多可以存储1次。您正在为存储使用索引寻址模式，因此Intel Haswell和更高版本不能在端口7上使用专用的简单存储AGU，否则每个时钟可以进行2次加载+ 1次存储。
修复内部循环以避免出现“ a” jmp（只有一个掉线jcc并在底部出现“ sub/ jcc”）之后，在Haswell及更高版本（移动加载，宏融合的cmp / jcc，mov-store，宏）上，您的循环应为4 uops -fused sub / jcc）。根据其解码方式，分支之一可能不会在Sandybridge上进行宏熔断。（SnB / IvB不能在多达4个微码的一个解码组中进行2次融合，而这些微码在同一周期内达到解码）。因此，使用寄存器cmp/jcc而不是内存，内部循环可以每个时钟1次迭代运行（当它不会发生错误预测时）。
如果您cmp reg, 0在优化后使用sub或设置的标记时还剩下一个dec，则将它们优化到test reg,reg短1个字节的位置，否则性能几乎相等。（并以相同的方式设置除AF以外的所有标志，您无法分支到该标志）。
它很可能只会在数组中包含20个元素。可能高达30。
我相信，使用相同的阵列，它将运行数千次。
好的，这意味着分支预测可能会“学习”少量排序的分支模式，从而针对相同的数据重复运行该函数。
这意味着调整asm实际上可能很重要。对于随机数据，大多数收益将与CPU从分支预测错误中恢复所花费的周期数量相形见war。当然，效率更高的代码可以让它更快地检测到错误预测，并仔细研究直到下一个错误预测稍快一些。现代CPU已经非常擅长通过冗余指令（只要它们不会增加关键路径延迟），因为许多在现代CPU上执行的机器代码是由JVM和类似程序中的JITed编译器创建的，并且优化的不是很好。
对于大小为20或30的某种类型，复制搜索循环将多次运行多次迭代（除非输入已经接近排序），因此推测其分支通常可以正确预测继续循环。对其进行优化以减少负载并运行更少的指令，对于仍在搜索中的案例实际上应该有所帮助。
请记住，针对常见情况优化代码。对于循环，通常意味着要使“保持循环”情况更快。这意味着有时值得在循环外溢出（将某些内容存储到内存中）以释放更多寄存器供循环内使用。
保存寄存器的另一种方法是使用指针增量而不是基数+索引。 或者将一些只读数据保留在内存中，特别是如果您在每个外循环迭代中仅读取一次的话。例如，外循环条件可以是cmp [end_pointer], esi/ jb。
（对于较小的文件，如果可以使开销足够小，则下限是在将大多数元素插入已排序区域末尾的3个元素内时进行的限制。或者，如果开销较高，则需要较大的平均副本大小值得。）
对于较大的排序，插入排序将花费大量时间一次将数组复制到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的情况是很诱人的。然后可以对齐所有负载。（不过，存储仍然会错位，所以也许甚至可以以使存储对齐的方式来处理它？）但是，现代CPU具有高效的未对齐负载处理能力，并且高速缓存行拆分并不是超级昂贵。在Skylake之前，分页（跨越4k边界）在Intel上非常昂贵。（类似于〜100个额外的周期，而成本与高速缓存行拆分相同）。
但是，除非您可以非常便宜地做到这一点，否则在大多数情况下完全避免这样做（除非复制搜索循环到达数组的最前面时）可能是一个胜利。
循环终止条件不能像一样简单i > 0，因为我们需要避免在数组开始处减少4个元素。 但是通过偏移esi（数组基数），我们仍然可以使用a sub/jcc作为循环条件来处理它，不需要a sub然后cmp/jcc针对指针。（但是，如果要针对IvyBridge或Sandybridge进行调优，可能值得使用指针递增，以便存储可以保持微融合。但是AMD不能融合sub/jcc，因此只有Haswell +可以使用此索引寻址，sub/jge并且实际上可能是最多的最佳方式（不展开）
这应该避免存储转发停顿，因为从它加载后我们正在写内存。从重叠+4（矢量的1/4）是成先前的读取，不进入下一个读操作。即使是小种类的商品，我们也不应出现存储转发停滞的情况：下一次外部迭代将重新启动与我们编写位置对齐的内部循环。
但是处理非4的非整数且不超过数组开头的开销对于小排序会很不利，因为实际的矢量循环仅运行几次迭代。