delphi - 快速访问(排序的)TList

Question

我的项目(在 Delphi 6 上运行!)需要一个内存分配列表(TMemoryAllocation)，我将其存储在一个对象中，该对象还保存有关分配大小(FSize)以及分配是否正在使用或空闲(FUsed)的信息.我基本上将其用作 GarbageCollector 和一种始终保持分配/解除分配内存应用程序的方法(并且需要大量分配/解除分配)。

每当我的项目需要分配时，它都会查找列表以找到适合所需大小的空闲分配。为此，我使用了一个简单的 for 循环:

for I := 0 to FAllocationList.Count - 1 do
begin
  if MemoryAllocation.FUsed and (MemoryAllocation.FSize = Size) then
...

我的应用程序运行的时间越长，这个列表就会增长到几千个项目，并且当我非常频繁地运行它(每秒几次)时它会大大减慢。

我试图找到一种方法来加速这个解决方案。我考虑过按分配大小对 TList 进行排序。如果我这样做了，我应该使用某种智能方式来访问列表，以获得我在每次通话时需要的特定大小。 有一些简单的方法可以做到这一点吗？

我正在考虑的另一种方法是拥有两个 TList。一个用于未使用的分配，一个用于已使用的分配。这意味着尽管我必须从一个列表中提取 TList.Items 并一直添加到另一个列表中。而且我仍然需要使用 for 循环来遍历(现在)较小的列表。 这是正确的方法吗？

其他建议是 非常也欢迎!

Answer 1

你有几种可能性:

当然，使用经过验证的内存管理器作为 FastMM4或一些 others致力于更好地扩展多线程应用程序；

重新发明轮子。

如果您的应用程序对内存分配非常敏感，也许有一些关于重新发明轮子的反馈:

利用您的 block 大小，例如每 16 字节的倍数，然后为每个 block 大小维护一个列表 - 这样您就可以快速找到好的 block “系列”，并且不必将每个单独的 block 大小存储在内存中(如果它在 32 字节列表中，它是一个 32 字节的 block )；

如果需要重新分配，尽量猜测减少内存拷贝的最佳增加因子；

按大小对 block 进行排序，然后使用 binary search ，这将比普通的 for i := 0 到 Count-1 循环快得多；

在列表中维护一 block 已删除的项目，当您需要新项目时可以在其中查找(因此您不必删除该项目，只需将其标记为免费 - 如果列表很大，这将加快速度) ;

不要使用列表(在删除或插入具有大量项目的已排序项目时会出现一些速度问题)，而是对项目和已释放项目使用链表。

这绝对不是那么简单，因此您可能想先查看一些现有的代码，或者只是依赖现有的库。我认为你不必在你的应用程序中编写这个内存分配，除非 FastMM4 对你来说不够快，我会非常怀疑，因为这是一段很棒的代码!