最小操作码大小 x86-64 strlen 实现

2024-04-14

我正在研究最小操作码大小x86-64 strlen我的代码高尔夫/二进制可执行文件的实现不应超过一定的大小(为简单起见,请考虑 demoscene)。
总体思路来自于here http://www.int80h.org/strlen/,尺寸优化思路来自here https://stackoverflow.com/a/33668295/5329717 and here https://codegolf.stackexchange.com/a/132985.

输入字符串地址位于rdi,最大长度不应大于Int32

xor   eax,eax ; 2 bytes
or    ecx,-1  ; 3 bytes
repne scasb   ; 2 bytes
not   ecx     ; 2 bytes
dec   ecx     ; 2 bytes

最终结果在ecx in 11 bytes total.

问题是关于设置ecx to -1

选项1已经说明

or ecx,-1 ; 3 bytes

Option 2

lea ecx,[rax-1] ; 3 bytes 

Option 3

stc         ; 1 byte
sbb ecx,ecx ; 2 bytes

选项4,可能是最慢的一个

push -1 ; 2 bytes
pop rcx ; 1 byte

我明白那个:
选项 1 依赖于之前的选项ecx value
选项 2 依赖于之前的选项rax value
选项 3 我不确定它是否依赖于之前的选项ecx value?
选项 4 是最慢的吗?

这里有明显的赢家吗?
标准是保持操作码大小尽可能小并明智地选择性能最佳的一个。
我完全知道有使用现代 CPU 指令的实现,但这种传统方法似乎是最小的一种。


对于一个 hacky 足够好的版本,we know rdi有有效地址。很有可能的是edi不是一个小整数,因此 2 字节mov ecx, edi。但这并不安全,因为 RDI 可能指向刚刚超过 4GiB 边界的位置,因此很难证明它是安全的。除非您使用像 x32 这样的 ILP32 ABI,否则所有指针都低于 4GiB 标记。

因此,您可能需要使用 push rdi / pop rcx 复制完整的 RDI,各 1 个字节。但这会增加短字符串启动的额外延迟。如果您没有长度大于其起始地址的字符串,那么它应该是安全的。 (但那是似是而非的如果您有任何大型数组,则用于 .data、.bss 或 .rodata 中的静态存储;例如,Linux 非 PIE 可执行文件的加载时间约为0x401000= 1

如果您只想让 rdi 指向终止,这非常有用0字节,而不是实际需要计数。或者,如果您在另一个寄存器中有起始指针,那么您可以这样做sub edi, edx或其他东西并以这种方式获取长度而不是处理rcx结果。 (如果您知道结果适合 32 位,则不需要sub rdi, rdx因为你知道无论如何它的高位都是零。并且高输入位不影响加/减的低输出位;进位从左到右传播。)

对于已知小于 255 字节的字符串,您可以使用mov cl, -1(2 个字节)。这使得rcx至少 0xFF,或者更高,具体取决于其中剩余的垃圾量。 (当读取 RCX 时,Nehalem 和更早的版本会出现部分注册停顿,否则仅依赖于旧的 RCX)。无论如何,那么mov al, -2 / sub al, cl获取 8 位整数的长度。这可能有用也可能没用。

根据呼叫者的不同,rcx可能已经保存了一个指针值,在这种情况下,如果可以使用指针减法,则可以保持它不变。


在您提出的选项中

lea ecx,[rax-1]非常好,因为你只是异或归零eax,它是一个廉价的 1 uop 指令,具有 1 个周期延迟,可以在所有主流 CPU 上的多个执行端口上运行。

当您已经有另一个具有已知常量值的寄存器时,尤其是异或归零的 3 字节寄存器lea如果可行的话,几乎总是创建常量的最有效的 3 字节方法。 (看有效地将CPU寄存器中的所有位设置为1 https://stackoverflow.com/questions/45105164/set-all-bits-in-cpu-register-to-1-efficiently).


我完全知道有使用现代 CPU 指令的实现,但这种传统方法似乎是最小的一种。

Yes, repne scasb非常紧凑。在典型的 Intel CPU 上,其启动开销可能约为 15 个周期,并且根据阿格纳·雾 http://agner.org/optimize/,它发出 >=6n uops,吞吐量 >= 2n 个周期,其中n是计数(即每个字节比较 2 个周期进行长比较,其中隐藏了启动开销),因此它的成本相形见绌lea.

错误依赖的东西ecx可能会延迟其启动,所以你肯定想要lea.

repne scasb对于你正在做的任何事情来说可能足够快,但它比pcmpeqb / pmovmsbk / cmp。对于短的固定长度字符串,integer cmp / jne is very当长度为 4 或 8 字节时很好(包括终止 0),假设您可以安全地过度读取字符串,即您不必担心""在页面的末尾。不过,此方法的开销随字符串长度而变化。例如,对于字符串长度 = 7,您可以执行 4、2 和 1 个操作数大小,或者可以执行两个重叠 1 个字节的双字比较。喜欢cmp dword [rdi], first_4_bytes / jne; cmp dword [rdi+3], last_4_bytes / jne.


有关 LEA 的更多详细信息

在 Sandybridge 系列 CPU 上,lea可以在与它和执行单元相同的周期中分派到执行单元xor-0 被发送到无序的 CPU 核心。xor-归零是在问题/重命名阶段处理的,因此uop以“已执行”状态进入ROB。指令不可能必须等待 RAX。 (除非异或和异或之间发生中断lea,但即便如此,我认为在恢复 RAX 之后和之前会有一个序列化指令lea可以执行,所以不能一直等待。)

Simple lea可以在 SnB 上的 port0 或 port1 上运行,或在 Skylake 上的 port1 / port5 上运行(每个时钟吞吐量 2 个,但有时在不同 SnB 系列 CPU 上有不同的端口)。这是 1 个周期的延迟,因此很难做得更好。

您不太可能看到使用带来任何加速mov ecx, -1(5 字节)可以在任何 ALU 端口上运行。

在 AMD 锐龙上,lea r32, [m]在 64 位模式下被视为“慢”LEA,只能在 2 个端口上运行,并且具有 2c 延迟而不是 1。更糟糕的是,Ryzen 并没有消除异或归零。


您所做的微基准测试仅测量没有错误依赖性的版本的吞吐量,而不测量延迟。这通常是一个有用的衡量标准,并且您确实得到了正确的答案:lea是最好的选择。

纯粹的吞吐量是否准确地反映了有关您的实际用例的任何信息是另一回事。如果字符串比较位于关键路径上,作为长或循环携带的数据依赖链的一部分,并且未被中断,那么您实际上可能依赖于延迟,而不是吞吐量。jcc为您提供分支预测+推测执行。 (但是无分支代码通常更大,所以这不太可能)。

stc / sbb ecx,ecx很有趣,但只有 AMD CPU 可以处理sbb作为依赖破坏(仅取决于 CF,而不取决于整数寄存器)。在 Intel Haswell 及更早版本上,sbb是一条 2 uop 指令(因为它有 3 个输入:2 个 GP 整数 + 标志)。它有 2c 的延迟,这就是它性能如此糟糕的原因。 (延迟是循环携带的 dep 链。)


缩短序列的其他部分

根据您正在做的事情,您也许可以使用strlen+2也好,但要抵消另一个常数或其他东西。dec ecx在 32 位代码中只有 1 个字节,但 x86-64 没有简写形式inc/dec指示。所以 not /dec 在 64 位代码中并不那么酷。

After repne scas, 你有ecx = -len - 2(如果你开始于ecx = -1), and not给你-x-1 (i.e. +len + 2 - 1).

 ; eax = 0
 ; ecx = -1
repne scasb      ; ecx = -len - 2
sub   eax, ecx   ; eax = +len + 2
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

最小操作码大小 x86-64 strlen 实现 的相关文章

  • 在长模式下更改 GDT 并更新 CS

    我正在编写一个简单的自制 64 位操作系统 通过 UEFI 启动它 这意味着当我的代码开始执行时 它已经处于长模式 并且启用了分页 现在 退出 UEFI 引导服务后 我想用我自己的控制结构替换 UEFI 构建的所有控制结构 成功更改 CR3
  • 英特尔® 事务同步扩展新指令 (TSX-NI) 与英特尔 TSX 有何不同?

    我在Intel的页面上找到了 https ark intel com products 97123 Intel Core i5 7500 Processor 6M Cache up to 3 80 GHz https ark intel c
  • 如何获取 VESA BIOS 信息

    我正在跟踪Phil Opp 教程 https os phil opp com 关于用 Rust 编写一个操作系统 在稍微尝试了一下之后 我想在屏幕上显示真实的图形 我发现我应该从使用带有 VESA 的线性帧缓冲区开始 我在 osdev or
  • 汇编编程语言:程序仅当输入为 ESC 时退出,并在退出前要求确认(y/n),否则循环

    我只是汇编语言编程的初学者 我们的第一个任务是让程序仅在输入为 ESC 时退出 退出之前请求确认 y n 否则循环 我知道 ESC 在 ASCII 代码中具有等效值 但我对插入位置或是否需要添加更多内容感到困惑 请帮我 这是程序 model
  • 为什么当设置为 TLS 选择器时,ES 和 DS 在 64 位内核上最终会归零?

    下面的 32 位程序调用set thread area 2 http linux die net man 2 set thread area在 GDT 中创建一个条目 该条目旨在用于 TLS 通常将结果选择器放入FS or GS并成功使用
  • DASM 汇编器中的 ASCII 到 C64 屏幕代码

    我正在通过 C64 模拟器学习 6502 micro 的汇编 目前正在尝试将字符串输出到屏幕 这是我的代码 processor 6502 org 1000 ldx 00 using x register as column counter
  • 在 REP MOVSW 之前 PUSH CS / POP DS 的目的是什么?

    为什么在下面的代码中我们压入代码段 PUSH CS 然后将其弹出到数据段 POP DS 我将这些行明确指定为 line1 和 line2 请告诉我 MOVSW 在这里是如何工作的 IF HIGHMEMORY PUSH DS MOV BX D
  • 破坏/分解函数的函数

    我以前有过 here https stackoverflow com questions 4920610 c class function in assembly 已经表明 C 函数不容易用汇编表示 现在我有兴趣以一种或另一种方式阅读它们
  • 一条指令可以同时处于两种寻址模式吗?

    我在书中读到了以下内容从头开始编程 处理器有多种不同的访问数据的方式 称为 寻址模式 最简单的模式是立即模式 其中 要访问的数据嵌入在指令本身中 例如 如果我们想将寄存器初始化为 0 而不是给出 计算机要从中读取 0 的地址 我们将指定立即
  • 遍历内存编辑每个字节

    我正在编写汇编代码 提示用户输入一串小写字符 然后输出包含所有大写字符的相同字符串 我的想法是迭代从特定地址开始的字节 并从每个字节中减去 20H 将小写变为大写 直到到达具有特定值的字节 我对 Assembly 相当缺乏经验 所以我不确定
  • AVX512 掩码寄存器(k1...k7)的 GNU C 内联 asm 输入约束?

    AVX512 为其算术命令引入了 opmask 功能 一个简单的例子 上帝螺栓 org https godbolt org z P7xWD8 include
  • 什么时候汇编比C更快? [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 Locked 这个问题及其答案是locked help locked posts因为这个问题是题外话 但却具有历史意义 目前不接受新的
  • Clang 使用 -nostdlib 生成崩溃代码

    我正在尝试为可执行文件设置自己的运行时环境 但无法使用 clang v3 4 1ubuntu1 目标 x86 64 pc linux gnu 来生成没有段错误的可执行文件 我已将问题简化为以下内容 如果我有一个文件 crt1 c 除了满足
  • g++.exe 和 x86_64-w64-mingw32-g++.exe 有什么区别?

    同样的问题也适用于 gcc ar 等 在 Code Blocks 中将工具链可执行文件从 Something exe 更改为 x86 64 w64 mingw32 something exe 时 代码仍然可以完美编译 此外 32 位和 64
  • 汇编基础知识:输出寄存器值

    我刚刚开始学习汇编语言 我已经陷入了 在屏幕上显示存储在寄存器中的十进制值 的部分 我使用 emu8086 任何帮助将不胜感激 model small Specifies the memory model used for program
  • 尝试使用 x86 程序集 GNU GAS 在数组索引处赋值时出现错误

    我在用x86GNU 与 GCC 的程序集 并尝试实现相当于以下内容的程序集c c int x 10 x 0 5 但是 当我尝试运行 使用命令 a out 我的汇编代码如下 第一次编译后gcc filename s 错误Segmentatio
  • 近调用/跳转表并不总是在引导加载程序中工作

    一般问题 我一直在开发一个简单的引导加载程序 并在某些环境中偶然发现了一个问题 在这些环境中 此类指令不起作用 mov si call tbl SI Call table pointer call call tbl Call print c
  • 两个基本的 ANTLR 问题

    我正在尝试使用 ANTLR 来获取简单的语法并生成汇编输出 我在 ANTLR 中选择的语言是 Python 许多教程看起来非常复杂或详细阐述与我无关的事情 我真的只需要一些非常简单的功能 所以我有两个问题 将值从一个规则 返回 到另一规则
  • 为什么 GCC 不将 a*a*a*a*a*a 优化为 (a*a*a)*(a*a*a)?

    我正在对科学应用程序进行一些数值优化 我注意到的一件事是 GCC 会优化调用pow a 2 通过将其编译成a a 但是调用pow a 6 没有优化 实际会调用库函数pow 这大大降低了性能 相比之下 英特尔 C 编译器 http en wi
  • 页面错误陷阱的成本

    我有一个应用程序 它定期 每 1 或 2 秒后 通过分叉自身来获取检查点 因此 检查点是原始进程的一个分支 它一直保持空闲状态 直到原始进程发生某些错误时被要求启动 现在我的问题是fork的写时复制机制的成本有多大 每当原始进程写入内存页面

随机推荐