c++ - 具有可变大小页面的缓冲池。当传入页面大于要驱逐的页面时，需要一种高性能的方法来合并页面

Question

在数据库缓冲池(内存池)的实现中，我有一个由内存中的页面组成的缓冲区。

页面有不同的大小(都是 512kb 的整数倍)。

假设我的驱逐策略是 LRU(最近最少使用)但是我试图驱逐的页面的大小小于我需要替换的页面，如果我也想遵循 LRU，我应该根据需要驱逐尽可能多的 LRU 页面以适应我的新页面。

假设我需要驱逐 n 个最近使用的页面。然而，这些页面在缓冲/内存池中不一定是连续的。

我想到的一个简单方法是合并这些 n 页面，这意味着我需要适本地重新排序缓冲池。

最简单的方法是复制整个缓冲区并覆盖永久缓冲区并适当更新数据类型。然而，这假设我们有足够的 RAM 来为这个操作复制整个缓冲区。有没有我不必复制整个缓冲区的聪明方法？

谢谢

Answer 1

一旦你不得不移动缓冲区，在我看来它就不是“高性能”的，但是，这个怎么样:

您要驱逐的页面的总大小是页面大小 512 kB 的 k 倍，即传入页面的大小。

最坏情况下的布局是这样的(四个字符(除了 | 条)== 512 kB):

|X1  |1       |2   |X2  |3       |4       |

两个 X 是要驱逐的页面。现在的问题是要使缓冲区连续，您需要将 X2 移动到 X1 旁边(或相反)。我的方法是将 X1 之后的页面向右移动(进入 X2)。我们可以安全地覆盖 X2，因为无论如何我们都想驱逐它。

这样一来，我们只需更新 3 个页面大小，而不是复制整个缓冲区。

一个更复杂的问题是:

|X1  |1   |2       |X2   |3       |X3      |4       |5   |

仍然可以使用上面的朴素算法，但有可能进行优化。例如，可以安全地将 1 移动到 X2 而无需触及 2，因为它适合那里。 2 也是如此，它可以移动到 X3 中。

所以实际上，您总是可以使用动态数组插入和交换中已知的简单移动技术，但检查可能的优化可能是明智的，在这种情况下，枚举必须由天真的算法，并首先尝试将它们直接放入待驱逐的空间。只有在失败后(如第一个示例)才应使用移动。

只有在需要原子性时才需要复制整个缓冲区。在这种情况下，上面的优化方法也可以工作，但是一旦无法将挡在您面前的页面放入要被驱逐的页面中，您就会遇到麻烦。在这种情况下，您必须递归驱逐算法以找到合适的位置，可能驱逐更多页面。