`

TCMalloc : Thread-Caching Malloc

阅读更多

原文http://google-perftools.googlecode.com/svn/trunk/doc/tcmalloc.html

Sanjay Ghemawat

Motivation

TCMalloc is faster than the glibc 2.3 malloc (available as a separate library called ptmalloc2) and other mallocs that I have tested. ptmalloc2 takes approximately 300 nanoseconds to execute a malloc/free pair on a 2.8 GHz P4 (for small objects). The TCMalloc implementation takes approximately 50 nanoseconds for the same operation pair. Speed is important for a malloc implementation because if malloc is not fast enough, application writers are inclined to write their own custom free lists on top of malloc. This can lead to extra complexity, and more memory usage unless the application writer is very careful to appropriately size the free lists and scavenge idle objects out of the free list.

TCMalloc also reduces lock contention for multi-threaded programs. For small objects, there is virtually zero contention. For large objects, TCMalloc tries to use fine grained and efficient spinlocks. ptmalloc2 also reduces lock contention by using per-thread arenas but there is a big problem with ptmalloc2's use of per-thread arenas. In ptmalloc2 memory can never move from one arena to another. This can lead to huge amounts of wasted space. For example, in one Google application, the first phase would allocate approximately 300MB of memory for its URL canonicalization data structures. When the first phase finished, a second phase would be started in the same address space. If this second phase was assigned a different arena than the one used by the first phase, this phase would not reuse any of the memory left after the first phase and would add another 300MB to the address space. Similar memory blowup problems were also noticed in other applications.

Another benefit of TCMalloc is space-efficient representation of small objects. For example, N 8-byte objects can be allocated while using space approximately 8N * 1.01 bytes. I.e., a one-percent space overhead. ptmalloc2 uses a four-byte header for each object and (I think) rounds up the size to a multiple of 8 bytes and ends up using 16N bytes.

Usage

To use TCMalloc, just link TCMalloc into your application via the "-ltcmalloc" linker flag.

You can use TCMalloc in applications you didn't compile yourself, by using LD_PRELOAD:

   $ LD_PRELOAD="/usr/lib/libtcmalloc.so" 

LD_PRELOAD is tricky, and we don't necessarily recommend this mode of usage.

TCMalloc includes a heap checker and heap profiler as well.

If you'd rather link in a version of TCMalloc that does not include the heap profiler and checker (perhaps to reduce binary size for a static binary), you can link in libtcmalloc_minimal instead.

Overview

TCMalloc assigns each thread a thread-local cache. Small allocations are satisfied from the thread-local cache. Objects are moved from central data structures into a thread-local cache as needed, and periodic garbage collections are used to migrate memory back from a thread-local cache into the central data structures.

TCMalloc treats objects with size <= 32K ("small" objects) differently from larger objects. Large objects are allocated directly from the central heap using a page-level allocator (a page is a 4K aligned region of memory). I.e., a large object is always page-aligned and occupies an integral number of pages.

A run of pages can be carved up into a sequence of small objects, each equally sized. For example a run of one page (4K) can be carved up into 32 objects of size 128 bytes each.

Small Object Allocation

Each small object size maps to one of approximately 170 allocatable size-classes. For example, all allocations in the range 961 to 1024 bytes are rounded up to 1024. The size-classes are spaced so that small sizes are separated by 8 bytes, larger sizes by 16 bytes, even larger sizes by 32 bytes, and so forth. The maximal spacing (for sizes >= ~2K) is 256 bytes.

A thread cache contains a singly linked list of free objects per size-class.

When allocating a small object: (1) We map its size to the corresponding size-class. (2) Look in the corresponding free list in the thread cache for the current thread. (3) If the free list is not empty, we remove the first object from the list and return it. When following this fast path, TCMalloc acquires no locks at all. This helps speed-up allocation significantly because a lock/unlock pair takes approximately 100 nanoseconds on a 2.8 GHz Xeon.

If the free list is empty: (1) We fetch a bunch of objects from a central free list for this size-class (the central free list is shared by all threads). (2) Place them in the thread-local free list. (3) Return one of the newly fetched objects to the applications.

If the central free list is also empty: (1) We allocate a run of pages from the central page allocator. (2) Split the run into a set of objects of this size-class. (3) Place the new objects on the central free list. (4) As before, move some of these objects to the thread-local free list.

Large Object Allocation

A large object size (> 32K) is rounded up to a page size (4K) and is handled by a central page heap. The central page heap is again an array of free lists. For i < 256, the kth entry is a free list of runs that consist of k pages. The 256th entry is a free list of runs that have length >= 256 pages:

An allocation for k pages is satisfied by looking in the kth free list. If that free list is empty, we look in the next free list, and so forth. Eventually, we look in the last free list if necessary. If that fails, we fetch memory from the system (using sbrk, mmap, or by mapping in portions of /dev/mem).

If an allocation for k pages is satisfied by a run of pages of length > k, the remainder of the run is re-inserted back into the appropriate free list in the page heap.

Spans

The heap managed by TCMalloc consists of a set of pages. A run of contiguous pages is represented by a Span object. A span can either be allocated, or free. If free, the span is one of the entries in a page heap linked-list. If allocated, it is either a large object that has been handed off to the application, or a run of pages that have been split up into a sequence of small objects. If split into small objects, the size-class of the objects is recorded in the span.

A central array indexed by page number can be used to find the span to which a page belongs. For example, span a below occupies 2 pages, span b occupies 1 page, span c occupies 5 pages and span d occupies 3 pages.

In a 32-bit address space, the central array is represented by a a 2-level radix tree where the root contains 32 entries and each leaf contains 2^15 entries (a 32-bit address spave has 2^20 4K pages, and the first level of tree divides the 2^20 pages by 2^5). This leads to a starting memory usage of 128KB of space (2^15*4 bytes) for the central array, which seems acceptable.

On 64-bit machines, we use a 3-level radix tree.

Deallocation

When an object is deallocated, we compute its page number and look it up in the central array to find the corresponding span object. The span tells us whether or not the object is small, and its size-class if it is small. If the object is small, we insert it into the appropriate free list in the current thread's thread cache. If the thread cache now exceeds a predetermined size (2MB by default), we run a garbage collector that moves unused objects from the thread cache into central free lists.

If the object is large, the span tells us the range of pages covered by the object. Suppose this range is [p,q]. We also lookup the spans for pages p-1 and q+1. If either of these neighboring spans are free, we coalesce them with the [p,q] span. The resulting span is inserted into the appropriate free list in the page heap.

Central Free Lists for Small Objects

As mentioned before, we keep a central free list for each size-class. Each central free list is organized as a two-level data structure: a set of spans, and a linked list of free objects per span.

An object is allocated from a central free list by removing the first entry from the linked list of some span. (If all spans have empty linked lists, a suitably sized span is first allocated from the central page heap.)

An object is returned to a central free list by adding it to the linked list of its containing span. If the linked list length now equals the total number of small objects in the span, this span is now completely free and is returned to the page heap.

Garbage Collection of Thread Caches

A thread cache is garbage collected when the combined size of all objects in the cache exceeds 2MB. The garbage collection threshold is automatically decreased as the number of threads increases so that we don't waste an inordinate amount of memory in a program with lots of threads.

We walk over all free lists in the cache and move some number of objects from the free list to the corresponding central list.

The number of objects to be moved from a free list is determined using a per-list low-water-mark L. L records the minimum length of the list since the last garbage collection. Note that we could have shortened the list by L objects at the last garbage collection without requiring any extra accesses to the central list. We use this past history as a predictor of future accesses and move L/2 objects from the thread cache free list to the corresponding central free list. This algorithm has the nice property that if a thread stops using a particular size, all objects of that size will quickly move from the thread cache to the central free list where they can be used by other threads.

Performance Notes

PTMalloc2 unittest

The PTMalloc2 package (now part of glibc) contains a unittest program t-test1.c. This forks a number of threads and performs a series of allocations and deallocations in each thread; the threads do not communicate other than by synchronization in the memory allocator.

t-test1 (included in tests/tcmalloc/, and compiled as ptmalloc_unittest1) was run with a varying numbers of threads (1-20) and maximum allocation sizes (64 bytes - 32Kbytes). These tests were run on a 2.4GHz dual Xeon system with hyper-threading enabled, using Linux glibc-2.3.2 from RedHat 9, with one million operations per thread in each test. In each case, the test was run once normally, and once with LD_PRELOAD=libtcmalloc.so.

The graphs below show the performance of TCMalloc vs PTMalloc2 for several different metrics. Firstly, total operations (millions) per elapsed second vs max allocation size, for varying numbers of threads. The raw data used to generate these graphs (the output of the time utility) is available in t-test1.times.txt.

  • TCMalloc is much more consistently scalable than PTMalloc2 - for all thread counts >1 it achieves ~7-9 million ops/sec for small allocations, falling to ~2 million ops/sec for larger allocations. The single-thread case is an obvious outlier, since it is only able to keep a single processor busy and hence can achieve fewer ops/sec. PTMalloc2 has a much higher variance on operations/sec - peaking somewhere around 4 million ops/sec for small allocations and falling to <1 million ops/sec for larger allocations.
  • TCMalloc is faster than PTMalloc2 in the vast majority of cases, and particularly for small allocations. Contention between threads is less of a problem in TCMalloc.
  • TCMalloc's performance drops off as the allocation size increases. This is because the per-thread cache is garbage-collected when it hits a threshold (defaulting to 2MB). With larger allocation sizes, fewer objects can be stored in the cache before it is garbage-collected.
  • There is a noticeable drop in TCMalloc's performance at ~32K maximum allocation size; at larger sizes performance drops less quickly. This is due to the 32K maximum size of objects in the per-thread caches; for objects larger than this TCMalloc allocates from the central page heap.

Next, operations (millions) per second of CPU time vs number of threads, for max allocation size 64 bytes - 128 Kbytes.

Here we see again that TCMalloc is both more consistent and more efficient than PTMalloc2. For max allocation sizes <32K, TCMalloc typically achieves ~2-2.5 million ops per second of CPU time with a large number of threads, whereas PTMalloc achieves generally 0.5-1 million ops per second of CPU time, with a lot of cases achieving much less than this figure. Above 32K max allocation size, TCMalloc drops to 1-1.5 million ops per second of CPU time, and PTMalloc drops almost to zero for large numbers of threads (i.e. with PTMalloc, lots of CPU time is being burned spinning waiting for locks in the heavily multi-threaded case).

Caveats

For some systems, TCMalloc may not work correctly on with applications that aren't linked against libpthread.so (or the equivalent on your OS). It should work on Linux using glibc 2.3, but other OS/libc combinations have not been tested.

TCMalloc may be somewhat more memory hungry than other mallocs, (but tends not to have the huge blowups that can happen with other mallocs). In particular, at startup TCMalloc allocates approximately 240KB of internal memory.

Don't try to load TCMalloc into a running binary (e.g., using JNI in Java programs). The binary will have allocated some objects using the system malloc, and may try to pass them to TCMalloc for deallocation. TCMalloc will not be able to handle such objects.


Sanjay Ghemawat, Paul Menage
<!----> <!----> Last modified: Sat Feb 24 13:11:38 PST 2007 (csilvers) <!---->
分享到:
评论

相关推荐

    【C++项目设计】高并发内存池.zip

    本项目实现的是一个高并发的内存池,它的原型是Google的一个开源项目tcmalloc,tcmalloc全称Thread-Caching Malloc,即线程缓存的malloc,实现了高效的多线程内存管理,用于替换系统的内存分配相关函数malloc和free...

    工作小计-性能优化-gperftools/tcmalloc/pprof

    tcmalloc(Thread-Caching Malloc)是gperftools的一部分,是一个高效的内存分配器。它通过将内存分配细化为多个小块并使用线程本地缓存来减少锁竞争,提高内存分配和释放的速度。tcmalloc还实现了内存碎片的最小化...

    Tcmalloc-v2.10

    Tcmalloc,全称为“Thread-Caching Malloc”,是Google开发的一款高效、优化的内存分配器,它被包含在gperftools库中,版本2.10提供了一系列性能优化和内存管理功能。tcmalloc的设计目标是在多线程环境中提高内存...

    控制内存增长TCMALLOC.docx

    为了解决这一问题,Google开发了一款名为TCMalloc(Thread-Caching Malloc)的内存分配器,它能够有效地减少内存碎片,提高内存利用率,并降低内存访问延迟。 #### 二、TCMalloc简介 TCMalloc是一种高性能的内存...

    vs2003-tcmalloc静态链接库

    Tcmalloc是Google开发的一款高效的内存分配器,其全称为"Thread-Caching Malloc"(线程缓存的内存分配器)。Tcmalloc设计的主要目标是提高多线程环境下的内存分配速度,减少系统调用,降低锁竞争,从而提升整体性能...

    google-perftools.rar

    Google Perftools是一款由Google开发的性能分析和内存管理工具包,主要包含tcmalloc(Thread-Caching Malloc)和CPU、内存等性能剖析器。tcmalloc是一种高效的内存分配器,它通过优化内存分配和回收过程来提高系统...

    基于numa架构的tcmalloc内存管理算法

    TCMalloc(Thread-Caching Malloc)是由Google开发的一种内存分配器,它通过线程缓存和中心缓存的方式,减少了线程间同步的需要,从而提高了内存分配的效率。TCMalloc使用线程本地缓存来管理内存,每个线程都有自己...

    gperftools-2.5.tar.gz

    Tcmalloc(Thread-Caching Malloc)是PerfTools中的一个内存分配器,它的设计目标是减少内存分配和释放的开销,尤其是在多线程环境中。传统的malloc函数在高并发环境下可能会成为性能瓶颈,而Tcmalloc通过在每个线程...

    google-perftools下载

    TCMalloc(Thread-Caching Malloc)是Perftools提供的一个高效的内存分配器,能够显著提升大规模并发环境下的内存性能。 首先,让我们关注CPU Profiler。当我们的Nginx服务器遇到性能问题时,CPU Profiler可以追踪...

    高并发内存池项目原始代码,开源项目

    这个开源项目“高并发内存池”是基于C++实现的,旨在模仿Google的tcmalloc(Thread-Caching Malloc)的核心设计。tcmalloc是一种高效的内存分配器,它引入了线程局部存储的概念,即每个线程都有自己的一小块内存,...

    Tcmalloc.zip

    Tcmalloc,全称为Thread-Caching Malloc,是Google开发的一款高效内存分配器。它被设计用于提升多线程环境下的内存分配性能,通过将内存分配细化到线程局部存储(TLS,Thread-Local Storage)级别,减少了锁竞争,...

    MySQL 使用Google的TCMalloc库,提高MySQL的性能.docx

    TCMalloc,全称为Thread-Caching Malloc,是Google开发的一款高效内存分配器,包含在开源工具包"google-perftools"中。与传统的glibc库中的malloc相比,TCMalloc在内存管理和分配方面表现出显著的优越性,特别是在...

    libtcmalloc.dll 下载

    它实现了TCMalloc(Thread-Caching Malloc),这种内存分配策略允许每个线程有自己的小块内存缓存,从而减少了跨线程的锁竞争,提高了多线程环境下的内存分配效率。此外,libtcmalloc还提供了堆分析和内存泄漏检测...

    memory_allocator-master.zip

    4. **tcmalloc**(Thread-Caching Malloc): - tcmalloc由Google开发,最初是作为PerfLib的一部分,后来被集成到gperftools中。 - 它的设计目标是最大化多线程环境下的性能,特别是在服务器和Web应用中。 - ...

    gperfTools分享

    #### TCMalloc(Thread-Caching Malloc)介绍及应用场景 TCMalloc 是一种替代标准 C 库中 malloc 实现的内存分配器,由 Google 开发。它主要设计用于提高多线程环境下的性能。通过在每个线程本地缓存内存块来减少锁...

    google-perftools-1.8.2.tar.gz

    1. `tcmalloc`(Thread-Caching Malloc):这是一个高效的内存分配器,通过线程缓存机制,减少了内存分配和释放时的系统调用开销。它还提供了内存泄漏检测的功能,可以追踪程序中未释放的内存块。 2. `pprof`:这是...

    gperftools:主要的gperftools存储库

    TCMalloc(Thread-Caching Malloc)是 gperftools 的一部分,是一个高效的内存分配器。它优化了多线程环境下的内存分配,通过在每个线程本地缓存小块内存请求来减少锁竞争,从而提高性能。TCMalloc 还提供了一些额外...

    iPhone IOS Hacker Handbook

    TCMalloc(Thread-Caching Malloc)是一种高性能的内存分配器,被广泛应用于Google的产品中。在iOS开发中,理解TCMalloc的工作原理有助于提高应用程序的性能和稳定性。 #### 控制TCMalloc 控制TCMalloc涉及到对...

Global site tag (gtag.js) - Google Analytics