65.9K
CodeProject 正在变化。 阅读更多。
Home

C++ 内存池

DanDanger2000
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.55/5 (34投票s)

2006 年 9 月 8 日

CPOL

8分钟阅读

viewsIcon

260589

downloadIcon

11309

一个（简单的）C++ 内存池。

Console output (ScreenShot)

目录

引言

C/C++ 中的内存分配（通过 malloc 或 new）可能非常耗时。

更糟糕的是，内存会随着时间的推移而碎片化，因此应用程序在长时间运行和/或执行大量内存（取消）分配时性能会下降。特别是如果您经常分配非常小量的内存，堆就会变得碎片化。

解决方案：您自己的内存池

一个（可能的）解决方案是内存池。

“内存池”在启动时分配大量内存，并将此块分成更小的块。每次您从内存池请求内存时，它都将从预先分配的块中获取，而不是从操作系统获取。最大的优点是：

  • 堆碎片化非常小（几乎没有）
  • 比“正常”内存（取消）分配（例如，通过 malloc、new 等）更快

此外，您还将获得这些好处：

  • 检查任意指针是否在内存池内
  • 将“堆转储”写入硬盘（非常适合事后调试等）
  • 某种“内存泄漏检测”：当您尚未释放所有先前分配的内存时，内存池会抛出一个断言

它是如何工作的？

让我们看一下内存池的 UML 图

MemoryPool UML schema

内存池 UML 图

此图仅显示了 CMemoryPool 类的一小部分，有关详细的类描述，请参阅 Doxygen 生成的文档。

那么，它实际上是如何工作的呢？

关于 MemoryChunks 的说明

从 UML 图中可以看到，内存池管理着指向 SMemoryChunk 结构（m_ptrFirstChunk、m_ptrLastChunk 和 m_ptrCursorChunk）的指针。这些块构成了内存块的链表。每个块都指向列表中的下一个块。当从操作系统分配内存块时，它将完全由 SMemoryChunk 管理。让我们仔细看看这样的块。

typedef struct SMemoryChunk
{
  TByte *Data ;             // The actual Data
  std::size_t DataSize ;    // Size of the "Data"-Block
  std::size_t UsedSize ;    // actual used Size
  bool IsAllocationChunk ;  // true, when this MemoryChunks
                            // Points to a "Data"-Block
                            // which can be deallocated via "free()"
  SMemoryChunk *Next ;      // Pointer to the Next MemoryChunk
                            // in the List (may be NULL)

} SMemoryChunk ;

每个块都包含一个指向以下内容的指针：

  • 一小块内存（Data），
  • 从该块开始的总可用内存大小（DataSize），
  • 实际使用的大小（UsedSize），
  • 以及指向列表中下一个块的指针（Next）。

第一步：预分配内存

当调用 CMemoryPool 构造函数时，内存池将从操作系统分配其第一个（大的）内存块。

/******************
Constructor
******************/
CMemoryPool::CMemoryPool(const std::size_t &sInitialMemoryPoolSize,
                         const std::size_t &sMemoryChunkSize,
                         const std::size_t &sMinimalMemorySizeToAllocate,
                         bool bSetMemoryData)
{
  m_ptrFirstChunk  = NULL ;
  m_ptrLastChunk   = NULL ;
  m_ptrCursorChunk = NULL ;

  m_sTotalMemoryPoolSize = 0 ;
  m_sUsedMemoryPoolSize  = 0 ;
  m_sFreeMemoryPoolSize  = 0 ;

  m_sMemoryChunkSize   = sMemoryChunkSize ;
  m_uiMemoryChunkCount = 0 ;
  m_uiObjectCount      = 0 ;

  m_bSetMemoryData               = bSetMemoryData ;
  m_sMinimalMemorySizeToAllocate = sMinimalMemorySizeToAllocate ;

  // Allocate the Initial amount of Memory from the Operating-System...
  AllocateMemory(sInitialMemoryPoolSize) ;
}

此处将完成所有类成员的常规初始化，最后 AllocateMemory 将从操作系统请求内存。

/******************
AllocateMemory
******************/
<CODE>bool CMemoryPool::AllocateMemory(const std::size_t &sMemorySize)
{
  std::size_t sBestMemBlockSize = CalculateBestMemoryBlockSize(sMemorySize) ;
  // allocate from Operating System
  TByte *ptrNewMemBlock = (TByte *) malloc(sBestMemBlockSize) ;
  ...

那么，内存池是如何管理这些数据的呢？

第二步：分配内存的细分

如前所述，内存池在 SMemoryChunk 中管理所有数据。从操作系统请求内存后，我们的块与实际内存块之间还没有任何连接。

MemoryPool after inital allocation

初始分配后的内存池

我们需要分配一个 SMemoryChunk 结构的数组来管理该内存块。

//(AllocateMemory() continued) : 
  ...
  unsigned int uiNeededChunks = CalculateNeededChunks(sMemorySize) ;
  // allocate Chunk-Array to Manage the Memory
  SMemoryChunk *ptrNewChunks = 
    (SMemoryChunk *) malloc((uiNeededChunks * sizeof(SMemoryChunk))) ;
  assert(((ptrNewMemBlock) && (ptrNewChunks)) 
                           && "Error : System ran out of Memory") ;
  ...

CalculateNeededChunks() 将计算管理给定内存量所需的块数。在分配块（通过 malloc）后，ptrNewChunks 指向一个 SMemoryChunk 数组。请注意，数组中的块只包含垃圾数据，因为我们尚未将块成员分配给任何有意义的数据。内存池“堆”将如下所示：

After SMemoryChunk allocation

分配 SMemoryChunk 后的内存池

仍然没有数据块和块之间的连接。但是 AllocateMemory() 现在将负责处理它。LinkChunksToData() 将最终将内存块和块链接在一起。这还将为每个块成员分配有效数据...

//(AllocateMemory() continued) : 
  ...
  // Associate the allocated Memory-Block with the Linked-List of MemoryChunks
  return LinkChunksToData(ptrNewChunks, uiNeededChunks, ptrNewMemBlock) ;

让我们仔细看看 LinkChunksToData()。

/******************
LinkChunksToData
******************/
bool CMemoryPool::LinkChunksToData(SMemoryChunk *ptrNewChunks, 
     unsigned int uiChunkCount, TByte *ptrNewMemBlock)
{
  SMemoryChunk *ptrNewChunk = NULL ;
  unsigned int uiMemOffSet = 0 ;
  bool bAllocationChunkAssigned = false ;
  for(unsigned int i = 0; i < uiChunkCount; i++)
  {
    if(!m_ptrFirstChunk)
    {
      m_ptrFirstChunk = SetChunkDefaults(&(ptrNewChunks[0])) ;
      m_ptrLastChunk = m_ptrFirstChunk ;
      m_ptrCursorChunk = m_ptrFirstChunk ;
    }
    else
    {
      ptrNewChunk = SetChunkDefaults(&(ptrNewChunks[i])) ;
      m_ptrLastChunk->Next = ptrNewChunk ;
      m_ptrLastChunk = ptrNewChunk ;
    }
    
    uiMemOffSet = (i * ((unsigned int) m_sMemoryChunkSize)) ;
    m_ptrLastChunk->Data = &(ptrNewMemBlock[uiMemOffSet]) ;

    // The first Chunk assigned to the new Memory-Block will be 
    // a "AllocationChunk". This means, this Chunks stores the
    // "original" Pointer to the MemBlock and is responsible for
    // "free()"ing the Memory later....
    if(!bAllocationChunkAssigned)
    {
      m_ptrLastChunk->IsAllocationChunk = true ;
      bAllocationChunkAssigned = true ;
    }
  }
  return RecalcChunkMemorySize(m_ptrFirstChunk, m_uiMemoryChunkCount) ;
}

让我们一步一步地看看这个重要的方法：前几行检查列表中是否已有块。

  ...
  if(!m_ptrFirstChunk)
  ...

开始时，情况并非如此。所以我们第一次分配我们的内部类成员。

  ...
  m_ptrFirstChunk = SetChunkDefaults(&(ptrNewChunks[0])) ;
  m_ptrLastChunk = m_ptrFirstChunk ;
  m_ptrCursorChunk = m_ptrFirstChunk ;
  ...

m_ptrFirstChunk 现在指向块数组中的第一个块。每个块精确管理内存块中的 m_sMemoryChunkSize 字节。将计算出一个“偏移量”，以便每个块都指向内存块的特定部分。

  uiMemOffSet = (i * ((unsigned int) m_sMemoryChunkSize)) ;
  m_ptrLastChunk->Data = &(ptrNewMemBlock[uiMemOffSet]) ;

此外，数组中的每个新 SMemoryChunk 都将被添加到链表的最后一个元素（并最终成为最后一个元素本身）。

  ...
  m_ptrLastChunk->Next = ptrNewChunk ;
  m_ptrLastChunk = ptrNewChunk ;
  ...

在随后的“for 循环”迭代中，内存池将依次为数组中的所有块分配有效数据。

Memory and chunks linked togehter

内存和块链接在一起，指向有效数据

最后，我们必须重新计算每个块可以管理的内存总量。这非常耗时，并且每次将新的内存从操作系统添加到内存池时都必须进行。每个块的总内存量将分配给块的 DataSize 成员。

/******************
RecalcChunkMemorySize
******************/
bool CMemoryPool::RecalcChunkMemorySize(SMemoryChunk *ptrChunk, 
                  unsigned int uiChunkCount)
{
  unsigned int uiMemOffSet = 0 ;
  for(unsigned int i = 0; i < uiChunkCount; i++)
  {
    if(ptrChunk)
    {
      uiMemOffSet = (i * ((unsigned int) m_sMemoryChunkSize)) ;
      ptrChunk->DataSize = 
        (((unsigned int) m_sTotalMemoryPoolSize) - uiMemOffSet) ;
      ptrChunk = ptrChunk->Next ;
    }
    else
    {
     assert(false && "Error : ptrChunk == NULL") ;
     return false ;
    }
  }
  return true ;
}

在 RecalcChunkMemorySize 之后，每个块都知道它指向的可用内存量。因此，很容易确定一个块是否能够容纳特定量的内存：当 DataSize 成员大于（或等于）请求的内存量且 UsedSize 成员为 0 时，该块就能容纳该内存。最后，内存细分完成。为了使事情不那么抽象，假设内存池包含 600 字节，并且每个块持有 100 字节。

Memory-Segmentation finished

内存细分完成。每个块精确管理 100 字节

第三步：从内存池请求内存

那么，如果用户从内存池请求内存会发生什么？最初，内存池中的所有数据都是免费可用的。

All Memory available

所有内存块均可用

让我们看看 GetMemory。

/******************
GetMemory
******************/
void *CMemoryPool::GetMemory(const std::size_t &sMemorySize)
{
  std::size_t sBestMemBlockSize = 
    CalculateBestMemoryBlockSize(sMemorySize) ;  
  SMemoryChunk *ptrChunk = NULL ;
  while(!ptrChunk)
  {
    // Is a Chunks available to hold the requested amount of Memory ?
    ptrChunk = FindChunkSuitableToHoldMemory(sBestMemBlockSize) ;
    <CODE>if(!ptrChunk)
    {
      // No chunk can be found
      // => Memory-Pool is to small. We have to request 
      //    more Memory from the Operating-System....
      sBestMemBlockSize = MaxValue(sBestMemBlockSize, 
        CalculateBestMemoryBlockSize(m_sMinimalMemorySizeToAllocate)) ;
      AllocateMemory(sBestMemBlockSize) ;
    }
  }

  // Finally, a suitable Chunk was found.
  // Adjust the Values of the internal "TotalSize"/"UsedSize" Members and 
  // the Values of the MemoryChunk itself.
  m_sUsedMemoryPoolSize += sBestMemBlockSize ;
  m_sFreeMemoryPoolSize -= sBestMemBlockSize ;
  m_uiObjectCount++ ;
  SetMemoryChunkValues(ptrChunk, sBestMemBlockSize) ;

  // eventually, return the Pointer to the User
  return ((void *) ptrChunk->Data) ;
}

当用户从内存池请求内存时，它将搜索列表以查找能够容纳请求量的块。这意味着：

  • 该块的 DataSize 必须大于或等于请求的内存量
  • 该块的 UsedSize 必须为 0

这由 FindChunkSuitableToHoldMemory 方法完成。如果它返回 NULL，则内存池中没有可用内存。这将导致调用 AllocateMemory（上面已讨论），该调用将从操作系统请求更多内存。如果返回值不是 NULL，则找到了一个有效的块。SetMemoryChunkValues 将调整块的内部值，最后将 Data 指针返回给用户...

/******************
SetMemoryChunkValues
******************/
void CMemoryPool::SetMemoryChunkValues(SMemoryChunk *ptrChunk, 
     const std::size_t &sMemBlockSize)
{
  if(ptrChunk) 
  {
    ptrChunk->UsedSize = sMemBlockSize ;
  }
  ...
}

示例

假设用户从我们的内存池请求了 250 字节。

Memory in use

正在使用的内存

如您所见，每个内存块管理 100 字节，因此 250 字节无法容纳。会发生什么？嗯，GetMemory 将返回第一个块的 Data 指针，并将其 UsedSize 成员设置为 300 字节，因为 300 字节是块可以管理的最小内存量，并且大于或等于 250 字节。（300 - 250 = 50）字节剩余的称为内存池的“内存开销”（除了块本身所需的内存）。这并不像听起来那么糟糕，因为内存仍然可以使用（它仍在内存池中）。

当 FindChunkSuitableToHoldMemory 搜索有效块时，它只会从一个“空块”跳转到另一个“空块”。这意味着，如果有人请求另一个内存块，则示例中的第四个块（持有 300 字节的那个）将是下一个“有效”块。

Jump to next valid chunk

跳转到下一个有效块

使用代码

使用代码简单明了：只需在您的应用程序中包含“CMemoryPool.h”，并将所有相关文件添加到您的 IDE/Makefile 中。

  • CMemoryPool.h
  • CMemoryPool.cpp
  • IMemoryBlock.h
  • SMemoryChunk.h

您只需创建一个 CMemoryPool 类的实例，就可以开始从中分配内存。所有内存池配置都在 CMemoryPool 构造函数中完成（通过可选参数）。请查看头文件（“CMemoryPool.h”）或 Doxygen 文档。所有文件都已（通过 Doxygen）进行了大量注释。

使用示例：

MemPool::CMemoryPool *g_ptrMemPool = new MemPool::CMemoryPool() ;

char *ptrCharArray = (char *) g_ptrMemPool->GetMemory(100) ;
...
g_ptrMemPool->FreeMemory(ptrCharArray, 100) ;

delete g_ptrMemPool ;

关注点

内存转储

您可以随时通过 WriteMemoryDumpToFile(strFileName) 将“内存转储”写入硬盘。让我们看一下一个简单的测试类的构造函数（重载了使用内存池的 new 和 delete 运算符）。

/******************
Constructor
******************/
MyTestClass::MyTestClass()
{
   m_cMyArray[0] = 'H' ;
   m_cMyArray[1] = 'e' ;
   m_cMyArray[2] = 'l' ;
   m_cMyArray[3] = 'l' ;
   m_cMyArray[4] = 'o' ;
   m_cMyArray[5] = NULL ;
   m_strMyString = "This is a small Test-String" ;
   m_iMyInt = 12345 ;

   m_fFloatValue = 23456.7890f ;
   m_fDoubleValue = 6789.012345 ;

   Next = this ;
}
MyTestClass *ptrTestClass = new MyTestClass ; 
g_ptrMemPool->WriteMemoryDumpToFile("MemoryDump.bin") ;

查看内存转储文件（“MemoryDump.bin”）。

如您所见，这些都是内存转储中 MyTestClass 类成员的值。显然，“Hello”字符串（m_cMyArray）在那里，整数值 m_iMyInt（3930 0000 = 0x3039 = 12345 十进制）等也在那里。这对于事后调试非常有用...

速度测试

我在 Windows 上进行了一些非常简单的速度测试（通过 timeGetTime()），但结果应该表明内存池可以大大加快应用程序的速度。所有测试均使用Microsoft Visual Studio .NET 2003 的调试版本进行（测试机器：Intel Pentium IV 处理器（32 位），1GB RAM，MS Windows XP Professional）。

//Array-test (Memory Pool): 
for(unsigned int j = 0; j < TestCount; j++)
{
    // ArraySize = 1000
    char *ptrArray = (char *) g_ptrMemPool->GetMemory(ArraySize)  ;
    g_ptrMemPool->FreeMemory(ptrArray, ArraySize) ;
}
  
//Array-test (Heap): 
for(unsigned int j = 0; j < TestCount; j++)
{
    // ArraySize = 1000
    char *ptrArray = (char *) malloc(ArraySize)  ;
    free(ptrArray) ;
}

Speed test Results for the array-test

“数组测试”结果

//Class-Test for MemoryPool and Heap (overloaded new/delete)
for(unsigned int j = 0; j < TestCount; j++)
{
    MyTestClass *ptrTestClass = new MyTestClass ;
    delete ptrTestClass ;
}

Speed test Results for the classes-test

“类测试”（重载的 new/delete 运算符）结果

关于代码...

该代码已在MS Windows 和Linux 上使用以下 C++ 编译器进行了测试：

  • Microsoft Visual C++ 6.0
  • Microsoft Visual C++ .NET 2003
  • MinGW (GCC) 3.4.4 (Windows)
  • GCC 4.0.X (Debian GNU Linux)

下载中包含Microsoft Visual C++ 6.0（*.dsw、*.dsp）和Microsoft Visual C++ .NET 2003（*.sln、*.vcproj）的项目文件。此内存池仅使用 ANSI/ISO C++，因此应该可以在任何具有可靠 C++ 编译器的操作系统上编译。在 64 位处理器上使用应该没有问题。

注意：内存池不是线程安全的！

待办事项

这个内存池远非完美 ;-) 待办事项列表包括：

  • 对于大量的内存，内存“开销”可能相当大。
  • 通过重新设计某些方法可以去除一些 CalculateNeededChunks 调用 => 进一步提高速度。;-)
  • 更多的稳定性测试（特别是对于非常长运行的应用程序）。
  • 使其线程安全。

历史

  • 2006.09.05：初始发布。

文件结束

© . All rights reserved.