在第7代Intel Core上优化视频RAM中递增ASCII十进制计数器

Question

我正在尝试为特定的卡比湖CPU（i5-7300HQ）优化以下子例程，理想情况下，使代码比其原始形式至少快10倍。该代码以16位实模式作为软盘式引导加载程序运行。它在屏幕上显示一个十位十进制计数器，从0到9999999计数，然后停止。

我看了Agner的《微体系结构和汇编优化指南》、《指令性能表》和《英特尔优化参考手册》。

到目前为止，我所能做的唯一明智的优化就是将循环指令替换为dec jnz指令，这里有解释。

另一种可能的优化可能是将lodsb替换为mov-dec，但我发现有关这方面的信息存在冲突，一些人说这有点帮助，另一些人说这实际上可能会影响现代CPU的性能。

我还尝试切换到32位模式，并将整个计数器保留在一个未使用的寄存器对中，以消除任何内存访问，但读入一位后，我意识到这十位将立即被缓存，一级缓存和寄存器之间的延迟差只有大约三分之一，因此绝对不值得以该格式使用计数器所增加的开销。

（编者按：add reg延迟为1个周期，add[mem]延迟约为6个周期，包括5个周期的存储转发延迟。如果[mem]像视频RAM一样不可访问，情况会更糟。）

org 7c00h

pos equ 2*(2*80-2)  ;address on screen

;init
cli
mov ax,3
int 10h
mov ax,0b800h
mov es,ax
jmp 0:start

start:
    push cs
    pop ds
    std

    mov ah, 4Eh
    xor cx, cx
    mov bl,'9'

countloop:
    mov cl,10           ;number of digits to add to
    mov si,counter+9    ;start of counter
    mov di,pos          ;screen position

    stc                 ;set carry for first adc
next_digit:
    lodsb               ;load digit
    adc al,0
    cmp bl, al
    jnc print
    add al,-10          ;propagate carry if resulting digit > 9
print:
    mov [si+1],al       ;save new digit
    stosw               ;print

    ;replaced loop with a faster equivalent
    ;loop next_digit
    dec cl
    jnz next_digit

    jnc countloop

    jmp $

counter:
    times 10 db '0'

    times 510-($-$$) db 0
    dw 0aa55h

我的问题是-我能做些什么来实现期望的速度增长？我还可以学习哪些其他材料来更好地理解基本概念？

注：这是一项学校作业。虽然直截了当的回答肯定会有帮助，但我更希望得到相关学习材料的解释或指点，因为我们没有得到任何。

编辑：将代码更改为最小的可复制示例

Answer 1

当您写入帧缓冲区时，最好将其视为在网络上发送数据包。“写入数据包”有一个包含地址、大小和数据（可能还包括校验和/奇偶校验）的标头。如果写入一个字节，数据包的数据部分将与数据包头的大小相形见绌，因此大部分带宽将被浪费。为了有效利用可用带宽，您需要更少的较大写入。写合并可以帮助您（将多个小写合并为一个大写），但在您自己优化写操作之后，它应该被视为一种潜在的小改进，而不是一个未能优化写操作的借口。

假设“通用32位80x86 CPU”（例如，80486没有SSE或AVX）；您的主要目标应该是将数据安排为五次32位写入；其中，每个32位写入包含两个“char-attribute”对。换言之，文字应该有点像：

    mov di,pos
    mov [di],eax
    mov [di+4],ebx
    mov [di+8],ecx
    mov [di+12],edx
    mov [di+16],esi

注意：在实模式或16位代码中使用32位指令没有什么错（只要CPU是80386或更高版本）。

然而这是一个柜台。这意味着99%的时间你只需要写一次（这也会使99%的写组合变得毫无价值）。更具体地说，如果最低的2位数翻滚（从“99”到“00”），则只需要第二次写入；如果最低的4位数翻滚（从“9999”到“0000”），则只需要第三次写入，以此类推。

因此...让我们初始化一个计数器：

    mov di,pos
    mov eax,0x4E304E30
    mov ebx,0x4E304E30
    mov ecx,0x4E304E30
    mov edx,0x4E304E30
    mov esi,0x4E304E30
    mov [di],esi
    mov [di+4],edx
    mov [di+8],ecx
    mov [di+12],ebx
    mov [di+16],eax

然后，您要增加它并更新屏幕：

.update:
    add eax,0x00010000
    cmp eax,0x4E390000
    ja .digit1rollover
    jmp .done1

.digit1rollover:
    add eax,0x00000001-0x000A0000
    cmp al,0x39
    ja .digit2rollover
    jmp .done1

.digit2rollover:
    mov eax,0x4E304E30
    add ebx,0x00010000
    cmp ebx,0x4E390000
    ja .digit3rollover
    jmp .done2

.digit3rollover:
    add ebx,0x00000001-0x000A0000
    cmp bl,0x39
    ja .digit4rollover
    jmp .done2

.digit4rollover:
    mov ebx,0x4E304E30
    add ecx,0x00010000
    cmp ecx,0x4E390000
    ja .digit5rollover
    jmp .done3

.digit5rollover:
    add ecx,0x00000001-0x000A0000
    cmp cl,0x39
    ja .digit6rollover
    jmp .done3

.digit6rollover:
    mov ecx,0x4E304E30
    add edx,0x00010000
    cmp edx,0x4E390000
    ja .digit7rollover
    jmp .done4

.digit7rollover:
    add edx,0x00000001-0x000A0000
    cmp dl,0x39
    ja .digit8rollover
    jmp .done4

.digit8rollover:
    mov edx,0x4E304E30
    add esi,0x00010000
    cmp esi,0x4E390000
    ja .digit9rollover
    jmp .done5

.digit9rollover:
    add esi,0x00000001-0x000A0000
    cmp si,0x4E39
    ja .digit10rollover
    jmp .done5

.digit10rollover:
    mov esi,0x4E304E30
;   jmp .done5

.done5:
    mov [di],esi
.done4:
    mov [di+4],edx
.done3:
    mov [di+8],ecx
.done2:
    mov [di+12],ebx
.done1:
    mov [di+16],eax

您还需要围绕此循环。幸运的是，bp仍然没有使用，所以这没有问题（只是不要忘记在初始化中设置bp）：

.done:
    dec bp
    jne .update

Answer 2

我们的要求是数字的每一个变化都必须在屏幕上可见

您的屏幕刷新率可能为60Hz，可能高达144Hz。如果更改视频RAM的速度超过此速度，则会使帧缓冲区上的硬件扫描输出循环无法读取某些计数，不会发送到物理屏幕，也不会变成高速相机可以记录的可见光光子图案。

脚注1：如果VGA文本模式是在只知道如何绘制像素的硬件上模拟的，则为虚拟等效模式。问：现代PC视频硬件支持硬件中的VGA文本模式，还是BIOS模拟它（使用系统管理模式）？作为后续行动。

如果我们不接受每16.66增加1个的限制。。ms（60 Hz），我们需要决定我们愿意在哪些方面设置瓶颈，而不是可以回避哪些方面。

当然，我们需要做计算ASCII数字的实际工作，而不仅仅是增加一个二进制计数器并在计时器或垂直消隐中断中偶尔将其格式化为字符串（每次屏幕刷新一次）。这不能满足分配的精神。

或者，如果我们只在寄存器中计算ASCII数字，而只在计时器或vblank中断中存储mov，会怎么样？这将从增量中异步采样快速递增的计数器，以便您可以直观地看到所有低位的变化。（这是一个非常明确的最低要求）。

从实际循环中省略存储仍然不会影响任务的精神。我认为我们的循环应该，如果在没有花哨硬件设置的情况下自行运行，真正将所有计数都传输到视频RAM。这似乎没有争议。这就是原始代码所做的。

CPU可以配置为与MTRR进行写组合。一些台式机有一个BIOS选项，可以将AGP GART设置为UC（不可缓存）与WC（称之为“USWC=不可缓存的推测性写入组合”）。这篇BIOS调优文章有一节介绍它。现代固件似乎离开了VGA内存UC，让操作系统/图形驱动程序设置MTRR/PAT。

不幸的是，使VGA内存WC工作得太好了，并且存储永远不会从CPU内核的写入组合缓冲区中取出。（LFB，因为这是英特尔CPU。）我们可以在每个存储后使用mford或clflushopt之类的内存屏障手动刷新缓存行的地址。但是我们又回到了起点，因为在OP的Kaby Lake iGPU/固件上，刷新WC存储的成本似乎与仅执行UC存储的成本大致相同。

当然，我们只需要在整个计数器同步时进行刷新，如果进位波动较大，则在更新所有数字后进行刷新。如果我们分别存储每个数字，如果我的数学正确，与UC内存相比，这可以使我们的速度提高11.111%。或者，如果我们一次进行两位数的dword存储，则会减少1.0101%，因为我们只需要每100个计数增加一个存储，而不是每10个计数增加一个存储。

这意味着计数器的递增速度非常快（仔细实施后，每个核心时钟周期几乎有1个计数）。我们只需在一个中断处理程序中使用一个内存屏障或串行化指令来对计数器进行采样，该中断处理程序在视频硬件开始屏幕左上角的新过程之前运行，扫描出一个新帧。事实上，iret正在序列化，因此仅从空的中断处理程序返回即可完成这项工作。如果您使用MTRR制作视频RAM WC，但没有编程定时或垂直消隐中断定期触发，则按住键盘上的键甚至可能使计数器更新在屏幕上可见（在其他情况下不可见）。

从循环的外部级别使用clflush或mfence不会很好地工作；这将与增量同步，从而使低位始终为零。这会使我们有时只在循环中显式刷新，而不是将刷新作为正常系统操作的一部分，因为中断而发生的事情。（或者，如果这个引导加载程序不是唯一运行的东西，至少会是这样。例如，如果在DOS下运行，那么每隔几毫秒就会有一个计时器中断。）

如果我们坚持每次计数都刷新到视频RAM（要么保留UC，要么在循环中手动使用WC显式刷新），唯一重要的优化就是减少视频RAM的存储数量。i、 e.不更新不变的数字。原始代码每次都存储每个数字，因此修复后的速度应接近10倍。

即使只是存储到不可缓存的DRAM或进行PCIe事务，也比您可以在循环内优化的任何事情都要慢得多，即使是自修改的代码机器也是如此。如果存储到VGA文本帧缓冲区会触发系统管理模式中断（SMI），通过更新真实像素帧缓冲区来模拟文本模式，那么存储到帧的成本是天文数字，与循环中的任何其他操作相比。这可能就是out Skylake/Kaby Lake集成GPU的固件工作原理：现代PC视频硬件是否支持硬件中的VGA文本模式，还是BIOS模拟它（使用系统管理模式）？

因此，允许硬件在我们的存储上对VRAM进行写合并，对于使这个优化问题变得有趣，而不仅仅是一个算法调整是至关重要的。

为此，请为VGA帧缓冲区编程MTRR。https://wiki.osdev.org/MTRR记录可与wrmsr指令一起使用的实际MSR。我认为每个MSR都有一个包含8个区域的位字段。您需要的是IA32\U MTRR\U FIX16K\U A0000，在MSR[259]中-8个区域，每个区域16 KB（总共128 KB），其中包括保存VGA文本模式内存的线性地址块B8000。Intel的SDM第3卷中的图11-8记录了布局。

有很多地方需要改进，但有两点至关重要：

>

微体系结构：自修改代码管道核，即机器清除，与主循环位于相同的64B缓存线中（性能约为50倍，无其他更改）如果不改变这一点，很难从任何其他微观优化中看到任何收益。

算法：不要每次盲目地将进位一直向上传播到每个数字：90%的增量根本不进位，99%只进位1位，等等。处理低位数字的嵌套循环可以非常有效地运行，只需增加自己的数字计数器，并让外环将其重置为“0”，无需使用adc显式传播这些进位。将这些ASCII数字保存在寄存器中也可以避免将它们加载/存储到计数[]，只需将其纯粹存储到视频RAM，如mov[di-4]，eax[代码]。

对于低位数的内部循环非常有效，高6位或7位的性能几乎变得无关紧要。该部分每10k或1k增量运行一次，因此其成本被摊销。（积极优化的内部循环的速度比原始循环的微优化版本快19倍，无需更改算法即可节省一些uops并避免一些瓶颈。）

原始版本的其他微优化（在修复SMC机器清除后）提供了约1.5倍的加速系数：使进位分支通常不执行，节省一些UOP，避免来自lodsb的部分寄存器错误依赖，并写入16位部分寄存器。

使用我从头重写的优化的4级内部循环，我的版本在Skylake/Kaby Lake上比原版本的无SMC失速版本快约29倍，或比真正的原版本快约1500倍。这里当然有一个中间地带，你可以进行adc传播，但当CF==0时，你可以提前进行传播；我没有试图实现这一点。

在32位模式下测试，但为16位模式组装的相同代码应以相同的方式执行，包括原始版本中的SMC暂停。（假设WC存储在刷新之前不会触发SMI，并且WC缓冲区将存储保持在内核内部的本地状态，这样就可以像WB内存一样实现1个存储/时钟。）

SKL和KBL在性能上是时钟对时钟相同的，是相同的微体系结构，所以我的测试结果应该可以为您重现。我确实在16位模式下组装了代码以查看对齐：看起来您的循环将在与循环结尾相同的64字节缓存线中有一些字节的计数[]，因此对于大多数数字，每次迭代都会有一个SMC管道核。

我修改了您的原始代码，以便在Linux下以32位模式运行相同的循环，从而可以使用硬件性能计数器分析性能。优化任何东西的第一步是获得基线测量。由于您提到了出于微体系结构原因的一些微优化，我们希望性能计数器不仅仅是总时间。我们无法在裸机上的引导加载程序中轻松实现这一点。可能是在来宾VM中，但随后您将存储到虚拟VGA设备，而不是真正的硬件，因此这可能与在Linux下用户空间的正常WB内存上使用普通或NT存储没有什么不同。

显示每秒所做工作量的计数器是比较不改变算法或分支数的调整的速度的一种简便方法。查看1秒内分支的计数以查看循环的相对速度，或将其除以周期。

我使用movnti尝试模拟存储到WC视频RAM（不可访问的推测写入组合，而不是正常的WB=写回缓存）。我认为WC内存区域的普通存储的行为类似于movnt存储。没有完成缓存行的movnt存储可以继续更新相同的写入组合LFB，而无需实际刷新到内存。所以它类似于可以在L1d缓存中命中的普通存储到WB内存。

帧缓冲区存储的SMI捕获（如果有的话）由CPU内核之外的硬件完成，可能是系统代理，因此在内核刷新之前不会触发。或者如果没有SMI陷阱，那么它可能只是转到我们iGPU系统上的DRAM。或者通过PCIe总线访问单独卡上的视频RAM。

DRAM和缓存几乎不涉及，而且系统足够空闲，物理核的另一个逻辑核上没有任何东西占用周期，因此代码本身有一个完整的CPU，在整个时间内将垃圾邮件存储到写组合缓冲区。

• 原始版本，移植为在32位用户空间中运行：Godbolt-未完全计时，但每秒打印统计数据的性能统计-I1000显示，它的运行速度比计数器之前的align 64慢约52倍。管道核武器可能包括冲洗WC缓冲区，这也意味着要去DRAM
• 原始版本，避免了SMC管道核弹：约85.7秒，10^10计数的约3580亿个核心时钟周期。2.66 IPC
• 微优化版本：Godbolt-约55.3秒，约2310亿个时钟周期，10^10个计数。4.56 IPC（但使用更简单的指令，而不是lodsb）
• 新的内循环，空的占位符外循环：Godbolt-约2.93秒，约122.5亿个核心时钟周期。2.73仪表板组合仪表

优化版本实现了每4个时钟接近3个存储。（从00...99开始计算低2位数字需要100个存储，它是这样做的。我没有用clflushope为这些最终版本计时。）

如果修复了一些暂停，并使用CF==0停止了循环，这将导致存储/重新加载（store-forwaring）延迟出现瓶颈，从而降低了数组的元素计数。您肯定希望这些数据位于寄存器中，以便它们只能存储，而不是加载/adc/存储。

TODO：评论并讨论我为该版本应用的微优化：

>

为什么GCC不使用部分寄存器？/Haswell/Skylake上的部分寄存器具体表现如何？编写AL似乎对RAX有错误的依赖，而且AH不一致-也lodsb很烂。lodsd/q是可以的。使用movzx进行窄加载，而不是合并到低字节中。幸运的是，Sandybridge-家庭上的adc循环中的inc/dec很好，不会像P6-家庭那样导致部分标志停顿。特别是在Skylake中，它根本不进行标志合并，而是在需要时单独读取FLAGS的CF和/或SPAZO部分。（结果：cmovbe和cmova是2 uop读取2个整数输入和CF ZF；其他cmov只有1 uop。）

您可以在16位模式下使用32位寄存器，无需切换模式。汇编程序只使用操作数大小前缀。写入32位寄存器不依赖于旧值，但16或8依赖于旧值。我用它来打破否则将被循环携带的依赖链，允许CPU在循环迭代/http://www.lighterra.com/papers/modernmicroprocessors/.

Haswell/Skylake的分支吞吐量为1/时钟，但可以在同一周期内运行未拍摄和拍摄。在快速路径上布局分支以支持未拍摄（通常总是一个好主意）。

哪个英特尔微架构引入了ADC reg，0单uop特例？-adc al，0不幸的是，在Skylake上是2 uops，与adc eax，0或adc bl，0不同。疯狂，对吧？这基本上是硬件设计师的CPU性能错误或CPU错过优化，其中较小编码的特例操作码解码更差。

32字节对齐例程不适合uops缓存——英特尔最近的JCC勘误表使得idq.mite_uopsperf事件值得检查。Skylake过去对代码对齐非常健壮，但现在对高吞吐量代码来说很可怕。

性能并没有完全下降，但一个重要因素可能是因为前端瓶颈，必须对32字节边界上以jcc结尾的32字节机器代码块使用传统解码。我没有花太多精力对此代码进行优化，但根据性能计数器，快速版本恰好避免了此问题。

这只是内部循环；外环只是重复10^10/10k次，没有实际的外环工作。我们每10k增量只保留一次内部4个循环，因此假装部分需要零时间并不会特别改变结果。

每个寄存器2个嵌套级别的循环的相同模式可以重复更多次，或者只需像您所做的那样执行一系列adc。

;; nasm -felf32 decimal-counter.asm
;; ld -N -melf_i386 -o decimal-counter decimal-counter.o
;; writeable text segment like a bootloader
;; runs in 32-bit mode with prefixes for 16-bit operand-size
;;
;; taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,resource_stalls.any:u,rs_events.empty_cycles:u,machine_clears.count:u -I1000 ./decimal-counter

%use smartalign
alignmode p6, 64

;org 7c00h

;pos equ vram + 2*(2*80-2)  ;address on screen
pos equ vram + 2*(2*80-4)  ;address on screen

    ; In GDB, use
    ; p ((char*)&vram) + 2*(2*80-4)-36

;init
;cli
;mov ax,3
;int 10h
;mov ax,0b800h
;mov es,ax
;jmp 0:start


 ; pick your poison, or let stores stay in the CPU, not reaching VRAM
%macro FLUSH 1
 ;  clflushopt %1           ; all the way to DRAM
 ;  mfence                  ; for mov to WB: just drain store buffer.  For WC or movnt, IDK how guaranteed it is to hit DRAM
;   lock xor byte [esp], 0   ; faster version of mfence (at least on Skylake)
%endmacro
;%define movnti mov         ; for experiments

global _start
align 512
_start:
;    push cs
;    pop ds
;    mov ebp, counter+9    ; save address in a register
;    mov edi,pos
    mov edi, pos - 10*4
    mov eax, '0_0_'
    mov ecx, 10
    rep stosw                   ; memset the digits in VRAM

    mov  ebp, 10000000000 / 10000     ; outer loop iterations
    mov edi, pos-4

;    mov ah, 4Eh         ; VGA attribute byte
;    mov eax, '____'

align 32
.outer:

    mov  edx, '0_0_'           ; thousands (low), hundreds (high) digits
.thousands:
 .hundreds:
    movnti  [edi-4], edx
    ; don't want to flush yet; only after low digits are updated
    add  edx, 1<<16

    mov  eax, '0_0_'            ; tens (low=AX), ones (high) digits
    .tens:
        .ones:                  ; do{
          movnti  [edi], eax         ; store low 2 digits
        FLUSH [edi]
          lea  ecx, [eax + (1<<16)]       ; off the critical path of the EAX dep chain
          movnti  [edi], ecx
        FLUSH [edi]
          add  eax, 2<<16               ; unroll by 2
          cmp  eax, '9_'<<16
          jle  .ones            ; }while(ones<='9')
                   ; mov byte [edi+2], '9'    ; peel the last 2 iterations?

        add  eax, ('1_0_') - ('0_0_' + (10<<16))     ; increment the more-significant digit (AL), resetting less-significant digit back to '0'
        cmp  al, '9'
        jle  .tens

    cmp  edx, '9_9_'
    jle  .hundreds

    add  edx, ('1_0_') - ('0_0_' + (10<<16))     ; increment the more-significant digit (DL), resetting less-significant digit back to '0'
    cmp  dl, '9'
    jle  .thousands

;; TODO: increment the high 6 digits, propagating carry.  Possibly clflushopt here only?
;    pause
    dec ebp
    jnz .outer
    ;    jmp $
    mov eax, 1
    int 0x80


;section .data   ; avoids machine clears
    ; in original 16-bit code: counter starts at 00000037 30<rept>, ends at 00000040 (inclusive), in same cache line as the loop
align 64
counter:
    times 10 db '0'
;section .text

    times 510-($-$$) db 0
    dw 0aa55h

section .bss
vram:   resw 80*25

我已经测试过这适用于低位数，在GDB中单步执行并使用显示（（char*）

使用dword存储意味着，当1放置时，包装我们不需要单独的存储来更新十位。它只需更新同一寄存器的低位字节，并让内部循环的第一次迭代进行存储。

在从0099滚动到0100的过程中，内存内容暂时为0199。但是，除非使用SSE一次存储16个字节，否则无法真正避免一个或另一个问题。另一种选择是以某种方式在0100之前安排0000，但这可能会浪费数百个循环中十/一dword的存储空间。

Answer 3

这是我的看法。已应用以下优化：

• 最低有效位已完全展开以获得最佳性能

此外，我已将代码更改为COM二进制文件以便于测试。将其变回引导加载程序是读者的一项练习。一旦它成为引导加载程序，您可以做的一件事是修复代码，使CS和SS具有0000的段库。这避免了对某些微架构上的加载和存储的惩罚。

        org     100h

pos     equ     2*(2*80-12)             ; address on screen

        mov     ax, 3                   ; set up video mode
        int     10h
        mov     ax, 0b800h
        mov     ds, ax
        mov     es, ax

        mov     di, pos
        mov     ax, 4e30h               ; '0' + attribute byte 4e
        mov     cx, 10
        cld
        rep     stosw                   ; set up initial display

        xor     ax, ax
        sub     sp, 10
        push    ax
        push    ax
        push    ax
        push    ax
        push    ax
        mov     bp, sp                  ; set up counter

        dec     di
        dec     di                      ; di points to the last digit on screen
        mov     bx, digits              ; translation table

        jmp     countloop

%macro  docarry 1                       ; digits other than the last one
        mov     al, [bp+%1]             ; second to last digit
        inc     ax                      ; add carry to al
        aaa                             ; generate BCD carry
        mov     [bp+%1], al             ; desposit to counter
        cs xlat                         ; generate ASCII digit
        mov     [di-2*9+2*%1], al       ; display digit
        jnc     countloop               ; exit when carry dies
%endm

docarry2:                               ; place this here so jumps are in range
        docarry 2
        docarry 1
        docarry 0
        int     20h

        align   16                      ; for performance
countloop:
        mov     [di], byte '0'          ; treat last digit separately
        mov     [di], byte '1'
        mov     [di], byte '2'
        mov     [di], byte '3'
        mov     [di], byte '4'
        mov     [di], byte '5'
        mov     [di], byte '6'
        mov     [di], byte '7'
        mov     [di], byte '8'
        mov     [di], byte '9'

        docarry 8
        docarry 7
        docarry 6
        docarry 5
        docarry 4
        docarry 3
        jmp     docarry2

digits:
        db      '0123456789'

与基于8 MHz 80286的机器上的原始代码相比，这将速度提高了约30倍，并设法使计数器每秒增加约329000次（每位数约3.04µs）。在现代系统上测试会有点困难，但我会努力找到解决方案。