缓存无关算法：让硬件替你优化
💡
原文中文，约17000字，阅读约需41分钟。
📝
内容提要
现代计算机的性能瓶颈已转向内存访问，缓存无关算法在所有层级缓存上实现最优性能，无需了解缓存参数。通过递归分解问题，缓存无关算法自动适应缓存大小，适用于矩阵运算和优先队列等场景，尽管常数因子较大，但其理论价值在于揭示了不依赖硬件参数的通用最优策略。
🎯
关键要点
- 现代计算机性能瓶颈转向内存访问，算法的I/O复杂度变得更加重要。
- 缓存感知算法需要程序员了解缓存参数，而缓存无关算法则不需要，能够在所有层级缓存上实现最优性能。
- 外部存储模型将存储简化为内部存储和外部存储两层，关键参数为内部存储容量M和每次I/O传输的块大小B。
- 缓存无关模型假设算法不知道B和M，但在分析I/O复杂度时仍使用这两个参数，能够自动适应不同的缓存大小。
- 递归分解问题的方式使得缓存无关算法在所有尺度上都能达到最优性能。
- van Emde Boas布局在不知道B的情况下实现了最优的搜索I/O复杂度。
- Funnel Sort是一种缓存无关的排序算法，能够在不知M和B的情况下达到I/O排序的最优界。
- 缓存无关矩阵乘法通过递归分块实现，能够在不依赖缓存参数的情况下达到I/O最优界。
- 缓存无关优先队列通过分层缓冲区结构实现，达到与外部存储模型下最优界相同的I/O复杂度。
- 理论与实践之间存在差距，缓存无关算法的常数因子通常较大，且在实际应用中可能面临TLB缺失和预取失效的问题。
❓
延伸问答
什么是缓存无关算法？
缓存无关算法是一类不需要知道缓存参数（如缓存大小和块大小）而能在所有层级缓存上实现最优性能的算法。
缓存无关算法如何适应不同的缓存大小？
缓存无关算法通过递归分解问题的方式，在某个递归层次上，子问题大小恰好等于缓存大小，从而自动适应不同的缓存大小。
缓存无关算法在实际应用中有哪些局限性？
缓存无关算法的常数因子通常较大，且在实际应用中可能面临TLB缺失和预取失效的问题。
Funnel Sort是什么，它的优势是什么？
Funnel Sort是一种缓存无关的排序算法，能够在不知缓存参数的情况下达到I/O排序的最优界，其优势在于无需了解硬件参数。
缓存无关矩阵乘法是如何实现的？
缓存无关矩阵乘法通过递归分块实现，能够在不依赖缓存参数的情况下达到I/O最优界。
为什么缓存无关算法在理论上优于缓存感知算法？
缓存无关算法在理论上优于缓存感知算法，因为它们不依赖于具体的硬件参数，能够在所有层级上自动适应并达到最优性能。
➡️
