Efficient C++ 第六 & 七章单/多线程内存池

桃扇骨 2022-04-11 05:47 178阅读 0赞

转自  
\[url\]http://blog.chinaunix.net/uid-25872711-id-3025357.html\[/url\]  
\[url\]http://blog.chinaunix.net/uid-25872711-id-3027155.html\[/url\]  
  
Code Project  
\[url\]http://www.codeproject.com/Articles/15527/C-Memory-Pool\[/url\]  
\[url\]http://www.codeproject.com/Articles/27487/Why-to-use-memory-pool-and-how-to-implement-it\[/url\]  
  
\[align=center\]\[b\]Efficient C++ 第六章 单线程内存池 \[/b\]\[/align\]  
  
\[b\]Memory Pooling\[/b\]  
　　频繁的进行内存分配和释放是降低程序性能的重要原因，性能降低的主要原因在于默认的内存管理器是通用的，这导致它的实现较复杂，需要考虑并适用所有内存分配情况。默认的new()操作符转化为甚至有上百个指令。应用程序可能只以一种特定的方式使用内存，所以我们可以开发自己的内存管理器，减少性能损失。可以从如下几方面设计：  
\[color=red\] 1）固定大小：分配固定大小内存块的内存管理器  
2）可变大小：分配任意大小内存块的内存管理器  
3）单线程：内存管理器仅限于单线程  
4）多线程：内存管理器用于并发执行的多个线程\[/color\]  
下面实现几个版本的内存管理器以对比其执行效率：  
  
\[b\]版本0：全局new()和delete()\[/b\]  
　　它很灵活，可以适用任何使用内存的情况。但是通常，应用程序并不需要其全部强大的功能，比如，客户端代码只在单线程中执行，那么全局new()、delete()提供的并发保护并不需要，这是极大的性能浪费。  
　　使用如下类的分配测试：

class Rational {
       
    public:
        Rational (int a = 0, int b = 1 ) : n(a), d(b) {}
    private:
        int n; // Numerator
        int d; // Denominator
    };
    
    int main()
    {
       
        Rational *array[1000];
        ...
        // Start timing here
    
        for (int j = 0; j < 500; j++) {
       
             for (int i = 0; i < 1000; i++) {
       
                  array[i] = new Rational(i);
                  }
             for (i = 0; i < 1000; i++) {
       
                  delete array[i];
                  }
             }
    
        // Stop timing here
    
        ...
    }

测试结果，使用全局内存管理器，耗时\[color=red\]1500ms\[/color\]。  
  
  
\[b\]版本1：专用Rational内存管理器\[/b\]  
　　我们设计一个简单的，专门为Rational使用的内存管理器，这样内存分配大小是固定的。代码如下：

class NextOnFreeList {
       
    public:
        NextOnFreeList *next;
    };
    
    class Rational {
       
    public:
        Rational (int a = 0, int b = 1 ) : n(a), d(b) {}
    
        inline void *operator new(size_t size);
        inline void operator delete(void *doomed, size_t size);
    
        static void newMemPool() { expandTheFreeList(); }
        static void deleteMemPool();
    
    private:
        static NextOnFreeList *freeList; // A free list of
                                            // Rational objects.
        static void expandTheFreeList();
        enum { EXPANSION_SIZE = 32};
    
        int n; // Numerator
        int d; // Denominator
    };
    
    inline
    void * Rational::operator new(size_t size)
    {
       
        if (0 == freeList) {// If the list is empty, fill it up.
           expandTheFreeList();
           }
    
        NextOnFreeList *head = freeList;
        freeList = head->next;
    
        return head;
    }
    
    inline
    void Rational::operator delete(void *doomed, size_t size)
    {
       
    　　NextOnFreeList *head = static_cast <NextOnFreeList *> doomed;
    
    　　head->next = freeList;
    　　freeList = head;
    }
    
    void Rational::expandTheFreeList()
    {
       
         // We must allocate an object large enough to contain the next
         // pointer.
         size_t size = (sizeof(Rational) > sizeof(NextOnFreeList *)) ?
             sizeof(Rational) : sizeof(NextOnFreeList *);
    
         NextOnFreeList *runner =
         static_cast <NextOnFreeList *> new char [size];
    
         freeList = runner;
         for (int i = 0; i < EXPANSION_SIZE; i++) {
       
             runner->next =
                    static_cast <NextOnFreeList *> new char [size];
             runner = runner->next;
              }
    
         runner->next = 0;
    }
    
    void Rational::deleteMemPool()
    {
       
        NextOnFreeList *nextPtr;
        for (nextPtr = freeList; nextPtr != NULL; nextPtr = freeList) {
       
               freeList = freeList->next;
               delete [] nextPtr;
               }
    }
    //测试代码
    
    NextOnFreeList *Rational::freeList = 0;
    
    int main()
    {
       
        ...
        Rational *array[1000];
    
        Rational::newMemPool();
    
        // Start timing here
    
        for (int j = 0; j < 500; j++) {
       
             for (int i = 0; i < 1000; i++) {
       
                  array[i] = new Rational(i);
                  }
             for (i = 0; i < 1000; i++) {
       
                  delete array[i];
                  }
             }
    
        // Stop timing here
    
        Rational::deleteMemPool();
        ...
    }

这代码比较简单，内存管理器是一个链表，它是Rational对象的指针列表。重载Rational的new操作符，每当new Rational对象，直接从链表中取出指针赋过去。内存块一次性分配32个，不够就扩展，所有内存一次性循环释放。这里有一点想不通，做内存分配时用new char\[size\]，有多少个Rational就进行了多少次new char\[size\]进行内存分配，为什么性能的提高了？？因为new char\[size\]的效率比普通new高吗？  
　　因为不受并发干扰，不用担心临界区，并且固定大小内存分配计算较少，经过测试执行时间为\[color=red\]43ms\[/color\]，提高非常明显。  
  
\[b\]版本2：固定大小对象的内存池\[/b\]  
　　版本1只限于Rational对象，用模板实现一个可适用不同类型的内存管理器。

template < class T >
    class MemoryPool {
       
    public:
        MemoryPool (size_t size = EXPANSION_SIZE);
        ~MemoryPool ();
    
        // Allocate a T element from the free list.
        inline void* alloc (size_t size);
    
        // Return a T element to the free list.
        inline void free (void *someElement);
    private:
        // next element on the free list.
        MemoryPool<T> *next;
    
        // If the freeList is empty, expand it by this amount.
        enum { EXPANSION_SIZE = 32};
    
        // Add free elements to the free list
        void expandTheFreeList(int howMany = EXPANSION_SIZE);
    };
    
    template < class T >
    MemoryPool < T > :: MemoryPool (size_t size)
    {
       
        expandTheFreeList(size);
    }
    
    template < class T >
    MemoryPool < T > :: ~MemoryPool ()
    {
       
        MemoryPool<T> *nextPtr = next;
        for (nextPtr = next; nextPtr != NULL; nextPtr = next) {
       
              next = next->next;
              delete [] nextPtr;
              }
    }
    
    template < class T >
    inline
    void* MemoryPool < T > :: alloc (size_t)
    {
       
        if (!next) {
       
           expandTheFreeList();
           }
    
        MemoryPool<T> *head = next;
        next = head->next;
    
        return head;
    }
    
    template < class T >
    inline
    void MemoryPool < T > :: free (void *doomed)
    {
       
        MemoryPool<T> *head = static_cast <MemoryPool<T> *> doomed;
    
        head->next = next;
        next = head;
    }
    
    template < class T >
    void MemoryPool < T > :: expandTheFreeList(int howMany)
    {
       
        // We must allocate an object large enough to contain the
        // next pointer.
        size_t size = (sizeof(T) > sizeof(MemoryPool<T> *)) ?
            sizeof(T) : sizeof(MemoryPool<T> *);
    
        MemoryPool<T> *runner = static_cast <MemoryPool<T> *> new char
    [size];
    
        next = runner;
        for (int i = 0; i < howMany ; i++) {
       
              runner->next =
                     static_cast <MemoryPool<T> *> new char [size];
              runner = runner->next;
              }
        runner->next = 0;
    }
    
    
    class Rational {
       
    public:
        Rational (int a = 0, int b = 1 ) : n(a), d(b) {}
    
        void *operator new(size_t size) { return memPool->alloc(size); }
        void operator delete(void *doomed,size_t size)
                      { memPool->free(doomed); }
    
        static void newMemPool() { memPool = new MemoryPool <Rational>; }
        static void deleteMemPool() { delete memPool; }
    private:
        int n; // Numerator
        int d; // Denominator
    
        static MemoryPool <Rational> *memPool;
    };
    
    MemoryPool <Rational> *Rational::memPool = 0;
    
    int main()
    {
       
        ...
        Rational *array[1000];
    
        Rational::newMemPool();
    
        // Start timing here
    
        for (int j = 0; j < 500; j++) {
       
             for (int i = 0; i < 1000; i++) {
       
                  array[i] = new Rational(i);
                  }
             for (i = 0; i < 1000; i++) {
       
                  delete array[i];
                  }
             }
    
        // Stop timing here
    
        Rational::deleteMemPool();
    
        ...
    }

这和版本1基本一样，只是用模板实现了内存管理器。链表结构，固定大小内存分配，都没有改变。测试后，执行时间为\[color=red\]63ms\[/color\]。  
  
  
\[b\]版本3：单线程可变大小内存管理器\[/b\]  
　　实现如下：

class MemoryChunk {
       
    public:
        MemoryChunk (MemoryChunk *nextChunk, size_t chunkSize);
        ~MemoryChunk() {delete mem; }
    
        inline void *alloc (size_t size);
        inline void free (void* someElement);
    
        // Pointer to next memory chunk on the list.
        MemoryChunk *nextMemChunk() {return next;}
    
        // How much space do we have left on this memory chunk?
        size_t spaceAvailable()
              { return chunkSize - bytesAlreadyAllocated; }
    
        // this is the default size of a single memory chunk.
        enum { DEFAULT_CHUNK_SIZE = 4096 };
    private:
        MemoryChunk *next;
        void *mem;
    
        // The size of a single memory chunk.
        size_t chunkSize;
    
        // This many bytes already allocated on the current memory chunk.
        size_t bytesAlreadyAllocated;
    };
    
    MemoryChunk::MemoryChunk(MemoryChunk *nextChunk, size_t reqSize)
    {
       
        chunkSize = (reqSize > DEFAULT_CHUNK_SIZE) ?
                     reqSize : DEFAULT_CHUNK_SIZE;
        next = nextChunk;
        bytesAlreadyAllocated = 0;
        mem = new char [chunkSize];
    }
    
    MemoryChunk :: ~MemoryChunk() { delete [] mem; }
    
    void* MemoryChunk :: alloc (size_t requestSize)
    {
       
        void *addr = static_cast <void*>
             (static_cast <size_t> mem + bytesAlreadyAllocated);
        bytesAlreadyAllocated += requestSize;
        return addr;
    }
    
    inline void MemoryChunk :: free (void *doomed) {}
    
    class ByteMemoryPool {
       
    public:
        ByteMemoryPool (size_t initSize =
                        MemoryChunk::DEFAULT_CHUNK_SIZE);
        ~ByteMemoryPool ();
    
        // Allocate memory from private pool.
        inline void *alloc (size_t size);
    
        // Free memory previously allocated from the pool
        inline void free (void* someElement);
    private:
        // A list of memory chunks. This is our private storage.
        MemoryChunk *listOfMemoryChunks;
    
        // Add one memory chunk to our private storage
        void expandStorage(size_t reqSize);
    };
    
    // Construct the ByteMemoryPool object. Build the private storage.
    ByteMemoryPool :: ByteMemoryPool (size_t initSize)
    {
       
        expandStorage(initSize);
    }
    
    ByteMemoryPool :: ~ByteMemoryPool ()
    {
       
        MemoryChunk *memChunk = listOfMemoryChunks;
    
        while (memChunk) {
       
                listOfMemoryChunks = memChunk->nextMemChunk();
                delete memChunk;
                memChunk = listOfMemoryChunks;
                }
    }
    
    void* ByteMemoryPool :: alloc (size_t requestSize)
    {
       
        size_t space = listOfMemoryChunks->spaceAvailable();
    
        if ( space < requestSize ) {
       
           expandStorage(requestSize);
           }
    
        return listOfMemoryChunks->alloc(requestSize);
    }
    
    inline
    void ByteMemoryPool :: free (void *doomed)
    {
       
        listOfMemoryChunks->free(doomed);
    }
    
    void ByteMemoryPool :: expandStorage(size_t reqSize)
    {
       
       listOfMemoryChunks = new MemoryChunk(listOfMemoryChunks, reqSize);
    }
    
    class Rational {
       
    public:
        Rational (int a = 0, int b = 1 ) : n(a), d(b) {}
    
        void *operator new(size_t size) {return memPool->alloc(size);}
        void operator delete(void *doomed,size_t size)
                      {memPool->free(doomed);}
    
        static void newMemPool() { memPool = new ByteMemoryPool;}
        static void deleteMemPool() { delete memPool; }
    private:
        int n; // Numerator
        int d; // Denominator
    
        static ByteMemoryPool *memPool;
    };
    
    MemoryPool <Rational> *Rational::memPool = 0;
    
    int main()
    {
       
        ...
        Rational *array[1000];
    
        Rational::newMemPool();
    
        // Start timing here
    
        for (int j = 0; j < 500; j++) {
       
             for (int i = 0; i < 1000; i++) {
       
                  array[i] = new Rational(i);
                  }
             for (i = 0; i < 1000; i++) {
       
                  delete array[i];
                  }
             }
    
        // Stop timing here
    
        Rational::deleteMemPool();
    
        ...
    }

版本3耗时\[color=red\]140ms\[/color\]，随着内存管理功能的增强，必须牺牲一些速度。  
  
通过这一章的学习，我基本解开了上一章中关于new操作性能的问题。全局new()，delete()性能低下的最主要原因是线程锁。  
  
  
\[b\]版本4：多线程内存池\[/b\]  
　　可以通过模板，直接利用前一章的代码实现新的多线程内存管理器，如下：

template <class POOLTYPE, class LOCK>
    class MTMemoryPool {
       
    public:
        // Allocate an element from the freeList.
        inline void* alloc (size_t size);
    
        // Return an element to the freeList.
        inline void free (void* someElement);
    private:
        POOLTYPE stPool; // Single-threaded pool.
        LOCK theLock;
    };
    
    template <class M, class L>
    inline
    void* MTMemoryPool<M,L>::alloc (size_t size)
    {
       
        void * mem;
    
        theLock.lock();
        mem = stPool.alloc(size);
        theLock.unlock();
    
        return mem;
    }
    
    template <class M, class L>
    inline
    void MTMemoryPool<M,L>::free (void* doomed)
    {
       
        theLock.lock();
        stPool.free(doomed);
        theLock.unlock();
    }
    
    class ABCLock {// Abstract base class
    public:
        virtual ~ABCLock() {}
        virtual void lock() = 0;
        virtual void unlock() = 0;
    };
    class MutexLock : public ABCLock {
       
    public:
        MutexLock() {pthread_mutex_init(&lock, NULL);}
        ~MutexLock() {pthread_mutex_destroy(&lock);}
    
        inline void lock() {pthread_mutex_lock(&lock);}
        inline void unlock() {pthread_mutex_unlock(&lock);}
    private:
        pthread_mutex_t lock;
    };
    
    class Rational {
       
    public:
        ...
        static void newMemPool() {
       
            memPool = new MTMemoryPool <MemoryPool <Rational>,
                                        MutexLock>;
            }
    private:
        ...
        static MTMemoryPool <MemoryPool<Rational>, MutexLock> *memPool;
    };

我们用了上一章中的模板固定大小分配的内存管理器，和MutexLock锁。使用上一章相同的测试后，运行时间为\[color=red\]1300ms\[/color\]，这与全局new(),delete()都很接近了，这表明全局内存管理性能主要是低在线程锁上面。  
  
　　接下来，书里又写了一个处理简单化的线程锁，这已经和内存管理几乎无关了。优化后，性能损失有了\[color=red\]30%\[/color\]左右的减少。