Shulou(Shulou.com)06/02 Report--

This article will explain in detail how to use the source code analysis C++ STL memory configuration design ideas, the article content quality is high, so Xiaobian share for everyone to make a reference, I hope you read this article after the relevant knowledge has a certain understanding.

The following will be combined with the key source code analysis of C++STL(SGI version) memory configurator design ideas.

A brief introduction to the allocator

The source code I read is SGI's version, which also looks the clearest version, and the various names are the easiest to understand. Allocator Some people call it a space allocator because space doesn't have to be memory, it can be disk or other secondary storage media. When I say memory allocation, I mean allocator.

The C++ standard specifies some of the necessary interfaces for allocators, which are implemented by various manufacturers. The SGI version differs from the standard specification in that it is called alloc rather than allocator and accepts no parameters.

Suppose you write allocator in your program instead of:

vector iv; //wrong

It has to be written like this:

vector iv //good

Although SGI STL does not conform to the specification, it seems natural to us to use it. This is because we use the time-space configurator by default and do not need to specify it ourselves. For example, the vector declaration in STL is as follows:

Note: I'll basically use screenshots to explain the code below, because I find it clearer (with color contrast) than pasting code.

2. A brief introduction to the source code file

STL standard: STL allocator is defined in the file, mainly contains some header files, we mainly say two:

Responsible for the allocation and release of memory space; responsible for the construction and destruction of object content

Construction and destruction tools: construct() and destroy()

Let's start with simple documents. This part doesn't involve any ideas either, just a version of destroy() that should be taken seriously.

(1) Construction tools: construct()

construct() has only one version:

Here we use the placement new expression, which is used to initialize the memory type T1 pointed to by p with value.

(2) Destructing tools

There are several versions of destroy():

*** Version:

You should also be familiar with this method of displaying calls to destructors.

Second version:

The second version can be said. The call hierarchy is as follows: destroy-> __destroy-> __destroy_aux,__destroy_aux eventually calls *** versions of destroy. This version of destroy takes a pair of iterators as arguments and destructs the scoped element to which the iterator points.

Before explaining this process, let's briefly talk about trivial_destructor.

If the user does not define a destructor, but uses the compiler to synthesize it, then the destructor is basically useless (but called by default) and is called a trivial destructor.

Then, if a pair of iterators point to elements that are trivial destructors, there is no need to waste time executing its destructor function on each object in turn, relying on the compiler's behavior. This is an improvement in efficiency. This is a point of optimization for STL allocator.

First, use value_type() to obtain the type of the object pointed to by the iterator, and then use__type_traits to determine whether the object's destructor function is trivial_destructor. If it is__true_type then do nothing, otherwise loop the *** version of destroy().

Third version:

This is a specialized version for iterators char* and wchar_t*, and seeing that their function bodies are empty, you should guess, there is no need to perform a destructor.

4. Memory application and destruction, std::alloc

The application and destruction of memory is the responsibility of. SGI's design philosophy on this point is:

1) Ask for space from the system heap.

(2) Consider multithreaded states.

(3) Consider contingency strategies when memory is insufficient.

(4) Consider the memory fragmentation problem that too many "mini-blocks" can cause.

In fact, the main thing I want to talk about is the design strategy of (3) and (4), especially the memory pool idea.

The overall design idea of std::alloc is:

SGI has designed a two-tier configurator. The *** configurator directly uses malloc and free; the second-tier configurator adopts different strategies depending on the situation: when the configuration block exceeds 128bytes, it is regarded as "large enough" and the *** configurator is called to process; when the configuration block is less than 128bytes, it is regarded as "too small". In order to reduce the extra burden, the memory pool (memory pool) processing mode is adopted, and the ** configurator is no longer used.

I. Resolution of *** level memory configurator

The main functions of the *** level configurator are: allocate memory, deallocate free memory, reallocate reallocate memory, etc.

（1）allocate

Call C function malloc directly, if memory does not meet the requirements, call oom_malloc function.

So, this is your own handler function, why do you realize it yourself? Because it does not use the memory configured by operator new, the C++new-handler mechanism cannot be used.

There's actually quite a bit to say about this mechanism, and if you're not familiar with its purpose or how to implement it yourself, I suggest you check out Effective C++ or my notes on Effective C++. I'm not trying to analyze grammar here.

（2）deallocate

Put the code on and you'll understand.

（3）reallocate

Here again, call C's realloc function, and if it fails, call oom_realloc.

It can be seen that oom_realloc is also a handler function.

Basically, the *** level memory configurator explains it clearly. One more thing: SGI allocates memory with malloc instead of operator new for historical reasons, and C++ does not provide realloc. This causes SGI to not be able to use C++ set_new_handler() directly, and can only simulate one by itself. How to emulate set_new_handler, which has a specific pattern.

Second, the second level of memory configurator analysis

The second-level memory allocator adds mechanisms to avoid memory fragmentation caused by too many small blocks. Not only do small blocks create memory fragmentation, but the extra burden of configuration is also a big problem. The extra burden was unavoidable. After all, the system needed this extra space to manage memory. However, the smaller the block size, the greater the proportion of extra burden. Naturally, the more wasted it was.

The overall idea of the second-level memory configurator is:

(1) If the requested block exceeds 128bytes, it will be handed over to the *** level memory configurator for processing.

(2) If the requested block is less than or equal to 128bytes, use memory pool management.

Specifically, the second-level memory allocator raises the memory requirements of any small block to a multiple of 8 and maintains 16 free-lists, each managing small blocks of sizes 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, and 128 bytes.

The structure of nodes in free-lists is as follows: (I have annotated this union)

Note: This use of union is also called a "flexible array" member. Essentially, it has to do with small end alignment, which is a trick.

（1）allocate

The memory allocation interface of the second-level memory configurator__default_alloc_template is the allocate function.

I've highlighted the key parts in red boxes. The FREELIST_INDEX(n) function returns the index of the appropriate one of the 16 free-lists based on the value of n.

Let's look at ROUND_UP(n), which I think is cleverly written to adjust bytes to multiples of 8 bytes.

To understand this function, you can take a few bytes and see what the return value is. The refill() function is useful, and I'll show you more below.

（2）deallocate()

First determine the block size, call the *** level configurator if it is greater than 128 bytes, otherwise determine which free list it should return to according to the byte size to be recovered, and then recover it from this free list.

（3）refill()

This function is very important, so I will introduce it separately. This function is called when there are no blocks available in the free list to refill a portion of the free list. The new space is taken from the memory pool (done by chunk_alloc). By default, 20 new blocks are obtained, and if the memory pool is insufficient, the number of new blocks obtained may be less than 20.

The two red boxes in the graph are two points worth noting. Once you get a chunk of memory from the memory pool, take one out for the caller and find the appropriate free list to "wear".

(4) Memory pool function chunk_alloc()

Memory pools have always been used to supply free lists. The following is a screenshot of this function.

*** Branch: See if the capacity in the memory pool is enough, if it is enough, just take it away.

The second branch: the memory pool is not enough for 20 blocks, but is greater than or equal to 1 block in length, giving away the rest. At this point, the memory pool is empty.

The third branch: If the memory pool cannot even provide a corresponding block, such as 32 bytes, but only 8 bytes, then *** is to link these 8 bytes to the corresponding free list utilization. Not surprisingly, the memory pool is empty at this point.

The fourth branch: the memory pool is empty, so the memory pool turns to the runtime heap, and the heap does not have that much space, so check which blocks in the 16 free lists have not been used, and add these to the memory pool.

The fifth branch: Yes, heap can do nothing, the memory pool simply calls the *** level configurator directly, because the *** level configurator has a new-handler mechanism, perhaps there is a chance to release other memory to call here. If yes, it succeeds; otherwise, a bad-alloc exception is thrown.

Summary:

If someone asks me STL memory configuration thoughts. I might say something like: C++STL is a two-level configuration of memory, specifically: *** level is responsible for managing large blocks of memory, to ensure that there is a mechanism similar to new- handler; the second level is responsible for managing small blocks of memory, in order to better manage memory fragments, establish 16 linked lists, each linked list "wear" a piece of fixed-size memory, these 16 linked lists (0 to 15) respectively "wear" memory is 8, 16, 24…128 multiples. When memory is needed, it is taken from the "appropriate" list, if the "appropriate" list memory is insufficient, it is taken from the memory pool, if the memory pool is insufficient, it is taken from the runtime heap, and if the heap also overflows, it is handed over to the *** level configurator because it has a new-handler mechanism.

About how to use the source code analysis C++ STL memory configuration design ideas to share here, I hope the above content can be of some help to everyone, you can learn more knowledge. If you think the article is good, you can share it so that more people can see it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.