algorithm - 比多个 Free List 方法更快的内存分配和释放算法

Question

我们分配和释放许多内存块。我们使用 Memory Heap .但是，堆访问的成本很高。

为了更快的内存访问分配和释放，我们采用全局 Free List .当我们制作多线程程序时，空闲列表受 Critical Section 保护。 .但是，关键部分会导致并行性瓶颈。

为了移除临界区，我们为每个线程分配一个空闲列表，即Thread Local Storage .然而，线程T1总是内存块，线程T2总是释放它们，所以线程T2中的Free List一直在增加，同时Free List没有任何好处。

尽管 Critical Section 存在瓶颈，但我们再次采用 Critical Section，但采用了一些不同的方法。我们准备了几个Free Lists以及分配给每个Free List的Critical Sections，因此有0~N-1个Free Lists和0~N-1个Critical Sections。我们准备了一个 atomic-operated突变为 0, 1, 2, ... N-1 然后 0, 1, 2, ... 的整数值。对于每次分配和释放，我们得到整数值 X，然后对其进行变异，访问第 X 个临界区，然后访问第 X 个空闲列表。但是，这比以前的方法(使用线程本地存储)要慢得多。由于有更多线程，原子操作非常慢。

由于以非原子方式改变整数值不会导致损坏，因此我们以非原子方式进行了改变。然而，由于整数值有时会过时，不同线程访问相同临界区和空闲列表的可能性很大。这又造成了瓶颈，尽管比以前的方法少了很多。

我们使用线程 ID 代替整数值，哈希范围为 (0~N-1)，然后性能变得更好。

我想一定有更好的方法来做到这一点，但我找不到确切的方法。有什么想法可以改进我们所做的吗？

Answer 1

处理堆内存是操作系统的任务。没有什么能保证您可以比操作系统做得更好/更快。

但是在某些情况下您可以获得一些改进，特别是当您了解一些操作系统不知道的内存使用情况时。 我在这里写下我未经测试的想法，希望你能从中受益。

假设您有 T 个线程，它们都在保留和释放内存。主要目标是速度，所以我会尽量不使用 TLS，也不使用关键阻塞，不使用原子操作。

如果(重复:如果，如果，如果)应用程序可以适应多个离散大小的内存块(不是随机大小，以避免碎片和无用的漏洞)然后开始向操作系统询问这些离散 block 的数量.

例如，您有一个 n1 block 数组，每个 block 大小为 size1，一个 n2 block 数组，每个 block 大小为 size2，一个n3的数组……等等。每个数组都是二维的，第二个字段只存储已用/空闲 block 的标志。如果您的数组非常大，那么最好为标志使用专用数组(因为连续内存使用总是更快)。

现在，有人要求一 block 大小为 sB 的内存。专门的函数(或对象或其他)搜索大小大于或等于 sB 的 block 数组，然后通过查看 used/free 标志来选择一个 block 。就在结束这个任务之前，正确的 block 标志被设置为“已使用”。

当两个或多个线程请求相同大小的 block 时，标志可能会损坏。使用 TLS 将解决这个问题，关键阻塞也是如此。我想你可以在搜索标志数组的开始时设置一个 bool 标志，这使得其他线程等待标志改变，这只发生在 block 标志改变之后。使用伪代码:

MemoryGetter(sB)
{
    //select which array depending of 'sB'
    for (i=0, i < numOfarrays, i++)
        if (sizeOfArr(i) >= sB)
           arrMatch = i
           break //exit for

    //wait if other thread wants a block from the same arrMatch array
    while ( searching(arrMatch) == true )
        ; //wait
    //blocks other threads wanting a block from the same arrMatch array
    searching(arrMatch) = true

    //Get the first free block
    for (i=0, i < numOfBlocks, i++)
        if ( arrOfUsed(arrMatch, i) != true )
           selectedBlock = addressOf(....)
           //mark the block as used
           arrOfUsed(arrMatch, i) = true
           break; //exit for

     //Allow other threads
     searching(arrMatch) = false

     return selectedBlock  //NOTE: selectedBlock==NULL means no free block
}

释放 block 更容易，只需将其标记为空闲即可，没有线程并发问题。

处理没有空闲 block 由您决定(等等，使用更大的 block ，向操作系统请求更多，等等)。

请注意，整个内存都是在应用程序启动时从操作系统保留的，这可能是个问题。

如果这个想法能让您的应用更快，请告诉我。我可以肯定地说，使用的内存比使用普通操作系统请求时要大；但如果您选择最常用的“好”尺寸，则不会太多。

可以做一些改进:

• 缓存最后释放的 block (按大小)以避免搜索。
• 从没有那么多 block 开始，只向操作系统请求更多内存 需要的时候。根据每个大小玩“ block 数” 你的应用程序。找到最佳案例。