- 去年写了关于内联 Lemire 近乎无除法无偏有界随机数算法的快速路径的内容,想法是通过在很少执行的慢路径中消除大量随机数生成器副本减少代码膨胀,但简单分割阻止了编译器优化
pcg32_rand(1 << n)
等情况,博客大部分在尝试缓解此问题。 周一在拖延另一个博客文章时意识到可以做得更好,有更通用的优化能免费得到
1 << n
的特殊情况。- 近乎无除法:Lemire 算法有 4 个技巧,近乎无除法逻辑导致快路径和慢路径有两个随机数生成器副本,一般编译器不会去重程序员写的代码,所以当限制为常量时编译器不能简化算法。
- 恒无除法:当限制为常量时,拒绝阈值可在编译时计算,除法免费时无需用技巧(4)避免,此时生成小于限制的随机数函数只有一个
pcg32_random()
调用,节省空间且编译器能自动消除循环,比去年写的代码更好。 - 算法选择:可根据限制是编译时常量还是运行时变量自动选择恒无除法或近乎无除法算法,可使用 C 技巧或 GNU C 的
__builtin_constant_p()
,还在思考其他语言如何做类似的事,如 Rust 虽不喜欢自动特化但有替代方法,可写不能误用的方法,这是个有趣的语言设计问题,或许应学习 Zig 看看其comptime
如何工作。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。