c++ - stl内存池中使用union节省空间的问题.

Question

最近在看sgi stl的内存池实现, 里面有如下的数据结构 :

typedef union obj {   
    union obj *free_list_link;   
    char client_data[1];    }obj;

据说可以节约空间, 但是不懂, 我个人感觉这种池应该是这样的, 也不知道对不对, 但是这为什么可以省内存呢? 难道说这个union省内存的地方在于它不需要一个指针来特意指向真正分配给用户的内存, 而是直接在这个union中分配, 也就是我图中这个下面的方块其实是由很多个union组成, 但是除了最后一个union其实是一个指针用来指向下一个方块的, 其它的其实都是用来直接分配给用户的, 不知道这样的理解对不对?

如图就是的左边就是我所理解的它的这种内存池的实现, 而右边就是那种使用结构体式的内存实现, 这样看得话确是每一个区块可以节约一个指针大小的空间, 但是我感觉其实用结构体也可以达到相同的效果啊, 并不会浪费内存啊... 比如如果我把右边的结构体中指向用户分配的内存那部分指针直接改成和左边一样, 直接用来作为用户所获得的区块, 那样两者就没有区别了...

Answer 1

Thank you for the invitation

This sentence is correct: It does not need a pointer to specifically point to the memory actually allocated to the user, but is allocated directly in this union

A 自由链表(free_list) at the same moment has and only has one of the following functions:
1. As a free linked list pointer, pointing to the next free linked list
2. It serves as a piece of available memory for users to use
Since the above uses cannot occur at the same time, obj is defined as union, and free_list_link and client_data share the same memory to save memory.

This sentence is wrong: Except for the last union which is actually a pointer used to point to the next block, the others are actually used to be allocated directly to the user

Note that this is a linked list. The distribution of the linked list in the memory is messy and discontinuous, not the continuous area you show.
As mentioned above, a obj structure is either used as a piece of allocated memory for users to use, or exists in a free linked list as an area to be allocated. Therefore, each block in the free linked list points to the next free linked list block, which is understood as:

struct node{
    node *next;
};

Once this free list block is allocated to a user, then it is removed from the free list and is no longer considered a free list block (by the semantics of union, henceforth It is an ordinary piece of memory allocated to the user. It will not be added to the free linked list again until it is released by the user)

This sentence is not appropriate: In fact, the same effect can be achieved with a practical structure
Once the memory is allocated, the pointer of this memory (i.e., the free linked list block) will bemalloc()/newReturn to the user, and then the task of saving the pointer is handed over to the user. Why do I still keep this thing in the memory configurator? Wouldn’t it waste space to save more pointers? Only unallocated memory can exist in a free linked list!

Also, I recommend "STL Source Code Analysis" translated by Hou Jie

Answer 2

You understand basically no problem, just to save the space of a pointer, there are two situations for any node:

1. The node allocates memory, then this union is a pointer to the actual allocated memory

2. The node does not allocate memory, so this union is a pointer to the next node

It is possible to use a structure, for example, there is only one pointer in the structure, but the type of your pointer can only be void *, and you have to force the type every time, which is quite ugly. Union is much more elegant