快速访问(已排序)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或其他一些专门用于更好地扩展多线程应用程序的内存管理器;
• 重新发明轮子.

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

• 利用您的块大小,例如每16字节倍数,然后每块大小保持一个列表 - 这样您就可以快速到达好块"系列",而不必将每个块大小存储在内存中(如果它在32中存在)字节列表,它是一个32字节的块);
• 如果需要重新分配,请尝试猜测最佳增加因子以减少内存复制;
• 对每个大小的块进行排序,然后使用二进制搜索,这将比普通的i:= 0到Count-1循环快得多;
• 在列表中保留一个已删除项目块,在需要新项目时进行查找(这样您就不必删除该项目,只需将其标记为空闲 - 如果列表很大,这将加速很多) ;
• 而不是使用列表(在删除或插入具有大量项目的已排序项目时会有一些速度问题)使用链接列表,用于项目和已释放项目.

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