在分解大型数据结构进行处理时，应该以什么大小为目标？具体筛段尺寸

What size should be aimed for when breaking up large data structures for processing? Specifically segment size of sieve

提问人：northerner 提问时间：12/10/2019 更新时间：12/10/2019 访问量：55

问：

一些大型数据结构的引用局部性较低。这对缓存不利。我正在实施埃拉托色尼的筛子。它包含一长串数字。可以分段处理列表以提高缓存命中率。区段大小应该是多少？我听说 L1 指令集缓存应该效果最好。根据我的测试，较大的尺寸效果更好，尽管我基本上只是尝试不同的尺寸。为什么大于 L1 缓存的大小实际上会导致整体更快的执行时间？缓存大小应该是单个内核还是所有内核？除了 CPU 缓存之外，还有其他可能的值，例如页面大小？

我知道分析将确定最佳大小，但我首先需要知道要测试哪些值。

在 Windows 任务管理器中，它说计算机有 256KB L1 缓存。但在 CPU-Z 中，它说 L1 数据是“4x32 KB”。在我的程序中，数字列表由 Since an 是 ' 字节表示，我猜 KB 实际上是 kibibytes，所以段大小为 32x1024。因为一个千字节中有 2^10 个字节。这一切都正确吗？std::vector<unsigned char>unsigned-char

C++ 数据结构 与语言无关 的分析 cpu-cache

评论

0赞 ALX23z 12/10/2019
256KB 可能是 256KBits。4×32KB - 4×是由于 4 个 CPU 内核。“埃拉托色尼的筛子”，如果你被这些细微差别所困扰 - 为什么不实施一种更快的方法来寻找素数呢？有亚线性方法。
0赞 northerner 12/10/2019
你能详细说明你所说的任何/所有内容@ALX23z吗？为什么 KB 的意思是 kbits 而不是 kbytes？您知道运行速度比线性更快的筛子的实现吗？
1赞 ALX23z 12/10/2019
为什么KB=KBits？经典的营销技巧。这就是他们推销互联网速度的方式。但这只是猜测 - 您最好在制造商的网站上进行验证。
0赞 ALX23z 12/10/2019
“Sieve of Erathostheses”是一种用于寻找素数的特定算法。用于查找素数的子线性算法的称呼不同。我曾经在 Wiki 上看到一个 - 但你最好看看关于这个主题的文章。虽然，它们永远不会比 .O(n/log n)n

答： 暂无答案

上一个：用于形成嵌套邻居邻接列表的算法

下一个：不同语言的浮点精度