#parse #integer #conversion #atoi #parser

atoi_radix10

快速解析为10进制整数(尤其是u64/u128)

1 个不稳定版本

0.0.1 2021年6月27日

#5#atoi

Download history 32/week @ 2024-03-10 57/week @ 2024-03-17 84/week @ 2024-03-24 104/week @ 2024-03-31 42/week @ 2024-04-07 22/week @ 2024-04-14 28/week @ 2024-04-21 60/week @ 2024-04-28 63/week @ 2024-05-05 20/week @ 2024-05-12 64/week @ 2024-05-19 30/week @ 2024-05-26 50/week @ 2024-06-02 23/week @ 2024-06-09 38/week @ 2024-06-16 14/week @ 2024-06-23

每月 129 次下载
用于 vcd-ng

MIT/Apache

180KB
2.5K SLoC

CI

更快的整数解析(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。

使用和功能

nightlysimd 功能以获得最高速度(并针对您的特定 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

无运行时依赖