6个版本
使用旧的Rust 2015
| 0.1.6 | 2017年4月10日 |
|---|---|
| 0.1.5 | 2017年4月10日 |
| 0.1.3 | 2016年4月22日 |
| 0.1.2 | 2016年2月3日 |
| 0.1.1 | 2016年1月22日 |
#1732 in 算法
296每月下载量
在 5 个crate中使用 (直接使用2个)
34KB
593 行
timely-sort
Rust中radix排序的缓存感知实现。
Timely sort 是用 Rust 编写的最低有效位radix排序。它旨在提高缓存感知，特别是在最小化从L1缓存向上移动的数据量方面。传统的观点是，这些交换限制了现代多处理器排序的可扩展性。
目前有两种radix排序版本：一种是普通的 LSBRadixSorter，另一种是执行软件写入合并的版本，LSBSWCRadixSorter。每个都维护一个内部缓冲区，用于存储到目前为止推送的元素，最初按最低有效字节分区，并在调用 finish 时完成排序。例如，请查看 benches/benches.rs。目前，文档还不够出色。
对于性能，请考虑排序随机 u32 数据的递增数量。我们在这里从 2 << 20 到 2 << 25 个元素，使用Rust的默认 sort()。当你运行 cargo bench
test msort_u32_20 ... bench: 19,182,135 ns/iter (+/- 1,022,566) = 218 MB/s
test msort_u32_21 ... bench: 38,633,682 ns/iter (+/- 1,299,863) = 217 MB/s
test msort_u32_22 ... bench: 78,986,400 ns/iter (+/- 1,691,552) = 212 MB/s
test msort_u32_23 ... bench: 161,851,450 ns/iter (+/- 3,195,896) = 207 MB/s
test msort_u32_24 ... bench: 329,526,599 ns/iter (+/- 5,655,355) = 203 MB/s
test msort_u32_25 ... bench: 672,753,001 ns/iter (+/- 11,634,847) = 199 MB/s
吞吐量下降，这是有道理的，因为 msort 是一个n log n算法。
radix排序没有这个问题，实际上还加快了（不要问；可能是一些我没有正确使用的缓冲区重用）
test rsort_u32_20 ... bench: 19,704,006 ns/iter (+/- 1,643,605) = 212 MB/s
test rsort_u32_21 ... bench: 34,972,698 ns/iter (+/- 1,925,898) = 239 MB/s
test rsort_u32_22 ... bench: 63,746,111 ns/iter (+/- 3,033,849) = 263 MB/s
test rsort_u32_23 ... bench: 120,175,182 ns/iter (+/- 7,227,761) = 279 MB/s
test rsort_u32_24 ... bench: 232,857,170 ns/iter (+/- 12,383,304) = 288 MB/s
test rsort_u32_25 ... bench: 458,974,307 ns/iter (+/- 17,849,213) = 292 MB/s
当我们进行软件写入合并时，每个缓冲区的头部都保留在自己的缓存行上，分布在几页上以避免淘汰，我们得到了更好的数字
test rsortswc_u32_20 ... bench: 11,996,260 ns/iter (+/- 1,615,053) = 349 MB/s
test rsortswc_u32_21 ... bench: 24,176,384 ns/iter (+/- 1,989,330) = 346 MB/s
test rsortswc_u32_22 ... bench: 48,412,808 ns/iter (+/- 3,983,659) = 346 MB/s
test rsortswc_u32_23 ... bench: 98,133,997 ns/iter (+/- 7,162,924) = 341 MB/s
test rsortswc_u32_24 ... bench: 197,561,440 ns/iter (+/- 13,321,125) = 339 MB/s
test rsortswc_u32_25 ... bench: 395,547,731 ns/iter (+/- 19,570,709) = 339 MB/s
代码看起来对我有效，但在用于特殊目的之前，请务必提前警告。该逻辑用于检测适合64字节缓存行的元素数量，以及适合4k页面的元素数量，但这个逻辑在未经测试的情况下可能非常糟糕。