将 UInt64 十六进制字符串转换为 UInt32 值的最快方法,保留尽可能多的前导数字,即截断

The fastest way to convert a UInt64 hex string to a UInt32 value preserving as many leading digits as possible, i.e. truncation

提问人:Vas 提问时间:6/1/2023 最后编辑:Peter CordesVas 更新时间:6/1/2023 访问量:150

问:

我正在寻找将表示 ulong 的十六进制字符串解析为 uint 的最快方法,保留 uint 可以处理的尽可能多的前导数字并丢弃其余数字。例如

string hex = “0xab54a9a1df8a0edb”;12345678991234567899 应该输出:uint result = 1234567899;

我可以通过简单地将十六进制解析为 ulong 来做到这一点,使用 ToString 获取数字,然后尽可能多地放入 uint 而不会溢出,但我需要更快的东西。谢谢。首选 C# 代码,但任何代码都可以。

C# 解析 decimal simd 截断

评论

1赞 Pepijn Kramer 6/1/2023
如果您的问题是关于 C# 的,请仅标记 C#。您在这里是否有经过验证的性能问题?例如,你是否分析了你的代码,并确保这种转换实际上阻碍了你?
1赞 Peter Cordes 6/1/2023
16 是 2 的幂,所以幸运的是,如果超过 8 位,您可以取最后 8 位十六进制数字。有没有一种算法可以快速将海量十六进制字符串转换为字节流? asm/C/C++ 有一个使用 SIMD 内部函数的 C++ 版本。github.com/zbjornson/fast-hex 也存在,但可以在水平包装蚕食的方式上进行一些改进。如果您已经有一个相当快的字符串,只需将其截断为 32 位,例如 C 或 ;缩小 C 模约的整数转换范围以拟合 dst 类型ulongulongx & 0xFFFFFFFFuLL(uint32_t)x
1赞 Peter Cordes 6/1/2023
x86 可以使用 BMI2 将 8 字节的低半字节提取为 4 字节,一个 asm 指令,经过一些 SIMD 工作,将每个字节映射到低 4 位为 0-15 整数的字节。(/或一些 SIMD 在 XMM0 中最多处理 16 个字节之后的东西。在 Zen 3 之前,它在 AMD 上很慢,但在其他方面,每个时钟吞吐量为 1 个,例如在 Intel 上有 3 个周期的延迟。uops.infopextmovq rax, xmm0pext rax, rax, rdx
1赞 Peter Cordes 6/1/2023
或者等等,你想截断十进制数字,而不是十六进制数字吗?因为通常截断为 uint32_t 是 = ,与低十六进制数字匹配,而不是低十进制数字匹配。0xab54a9a1df8a0edb0xdf8a0edb3750366939
1赞 Peter Cordes 6/1/2023
所以像(1e10)或其他东西可能是一个起点。如果它大于 2^32-1,取模 1000000000 (1e9) 代替取低 9 位十进制数字?u64 % 10000000000

答:

2赞 Peter Cordes 6/1/2023 #1

对于十进制截断,十六进制数字的所有高位都会影响低 9 或 10 位十进制数字,因此您需要转换整个内容。有没有一种算法可以快速将大量十六进制字符串转换为字节流? asm/C/C++ 具有具有 SSE 内部函数的 C++。我在那里发表了一些可能的改进,并 https://github.com/zbjornson/fast-hex.如果您使用 SIMD 在较大的缓冲区中查找数字文字,这可能特别好,因此您可能已经在 SIMD 寄存器中拥有十六进制字符串。(不确定 SIMDJSON 是否这样做。

十六进制字符串到 64 位整数是 SIMD 当然可以加速的,例如,做一些事情将每个数字映射到 0-15 个整数,组合成对的字节以打包半字节(例如使用 x86),然后将这些 8 位块洗牌到寄存器的底部。(例如 或 )。x86 至少具有有效的 SIMD 到 GP 整数,尽管在某些 ARM CPU 上 ARM 等效项很慢。pmaddubswpackuswbpshufbmovq rax, xmm0

(如果您的字符串是固定长度的,并且可能不需要检查不是十六进制数字的无效字符,那么从 SIMD 获得 ASCII 十六进制 -> uint 的加速要容易得多。


(C#) 的十进制截断以适应 (C#u64ulongu32uint)

10 次幂的取模截断为一定数量的十进制数字。

(uint)(x % 10000000000) works for some numbers, but 10000000000 (1e10 = one followed by 10 zeros) is larger than 2^32-1. Consider an input like (). We'd get producing (keeping the low 32 bits of that 34-bit number.)0x2540be3ff9999999999(uint)99999999991410065407 = 0x540be3ff

So perhaps try modulo 1e10, but if it's too big for u32 then modulo 1e9.

  ulong tendigit = x % 10000000000;  // 1e10
  uint truncated = tendigit <= (ulong)0xffffffff ? tendigit : (x % 1000000000);  // % 1e9 keeps 9 decimal digits

If this isn't correct C# syntax or the literals need some decoration to make them (like C for good measure), please let me know.ulong10000000000uLL

It's probably at least as efficient to just modulo the original number two different ways than to try to get the leading decimal digit of and subtract it or whatever. The asm is going to need two 64-bit multiplicative inverse constants, and starting from the original number again keeps critical-path latency shorter for out-of-order exec if branch prediction predicts that it needs to calculate the nine-digit truncation.x % 1e10


Binary truncation

@Matthew Whited deleted his answer (due to a bug in the decimal truncation part), but his binary truncation part based on substrings of the original hex input could perhaps be more efficient in some cases than doing the full conversion and then casting to a narrower type or masking with AND.

If you want the last 8 bytes of the hex string

uint.Parse(hex[^8..],NumberStyles.HexNumber)

If you want the first 8 bytes

uint.Parse(hex[2..10], NumberStyles.HexNumber);