1 个不稳定版本
0.0.1 | 2021年6月27日 |
---|
#5 在 #atoi 中
每月 129 次下载
用于 vcd-ng
180KB
2.5K SLoC
更快的整数解析(Rust 版本)
这个仓库是 @KholdStare 在 https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html 上的实验的 Rust 版本
在 Rust Malaysia 也有关于此的博客文章。 https://github.com/rust-malaysia/rust-malaysia.github.io/blob/master/_posts/2020-07-12-faster-integer-parsing.md
根据 Reddit 上的讨论,发现有人在与 @KholdStare 之前就已经发现了完全相同的思想,那就是 Wojciech Muła。 http://0x80.pl/articles/simd-parsing-int-sequences.html
备注
规范
+/- 0000000000000 然后是数字。
目标
探索解析数字的最快方式,而不读取你自己的内存。(一旦我们对结果满意,我们可以在保持性能的同时尽可能多地尝试去安全化。)
我们试图遵守小数规则,并确保单个数字的解析速度特别快,总的来说,所有数字的解析速度都将比 std 快。
性能
如果您必须解析 u128 和 i128 数字,此软件包中的任何数字都在 25 纳秒以下(如果针对具有 avx 的特定 CPU,则可能在 15 纳秒到 20 纳秒以下)。它在所有数字上比 std rust(尤其是 i128)快得多。
对于 u8/i8,它与 std 相当。
对于 u16, u32, u64,它比 std 快约 1/3。
使用和功能
nightly
和 simd
功能以获得最高速度(并针对您的特定 CPU)。
如果想要运行所有测试,则需要 std
功能。默认情况下,它是 no_std
,并将从任何 [u8]
切片中进行解析。
这是如何工作的
这被称为 SWAR:寄存器内的 SIMD。
有帮助的优化
- 使用 likely 和 unlikely 内部函数。
- 在由于延迟要求而访问之前将
+
移动到更高位置。 - 返回前尽量不执行需要延迟的指令。例如
if cond { return a as u16 }
,你可以在if语句之前计算a as u16
,这样会更快。(我们在优化快乐路径) - 快速开始并尝试添加功能比慢慢开始然后使它更快要容易得多(后者你不知道为什么它慢,只是猜测,而如果你逐步构建,当你添加某些内容使速度变慢时,你会立即知道。)。
- 结果发现错误枚举会稍微减慢速度,所以为了最大速度,如果你不在乎解析错误类型,可以使用
.map_err(|_| ())
。
未优化的优化
似乎没有产生任何影响的事物
- 编译器在幕后将 *10 分解为 *8 + *2,所以我们不必这么做。(它似乎在100时使用imul,所以用移位替换它可能会略有收益)
- 将 len 从 usize 强制转换为 u8。
常见问题解答
-
我应该在生产中使用这个吗?因为这是一个新的crate,我会小心对待,尽管有测试和一些模糊测试,但仍可能存在一些bug。它已经有一个
reddit review
,我希望已经填补了关于对齐的健全性漏洞。 -
为什么不将其包含在标准库中?标准库的解析代码不是基于基数特定的。因为数字解析在核心库中,对于嵌入式系统来说,代码大小很重要。这个实现肯定比标准库的代码要多。
-
如果你想在wasm下运行测试,你需要安装
cargo install wasm-bindgen-cli
待办事项
- 使所有测试在no_std模式下工作。
- 为wasm编译
- 在wasm上进行基准测试?
- 在wasm下运行测试:
cargo test --features nightly --target=wasm32-unknown-unknown
- 使所有wasm测试通过。
- Wasm + Simd - 我能否使用核心simd,并且256位的东西直接在模拟中工作?
- 使用非可移植的simd命令(因此simd功能可以在arm/neon上工作)。
- 使它在大端模式下工作
大端
我们可以通过MIRI在大端模式下运行测试
rustup +nightly component add miri
MIRIFLAGS="-Zmiri-symbolic-alignment-check" cargo miri test --target mips64-unknown-linux-gnuabi64