Reduce the number of malloc calls by slicing one large malloc'd memory

Question

Firstly, here where I got this idea from:

Once upon a time there was an application that I wrote that used a lot of small drops of memory, each of which is allocated using malloc (). It worked correctly, but slow. I replaced many malloc calls with just one, and then cut this big block in my application. It was much faster.

I was profiling my application and I received an unexpectedly nice performance boost when I reduced the number of malloc calls. However, I still allocate the same amount of memory.

So, I would like to do what this guy did, but I'm not sure if this is the best way to do this.

My idea:

// static global variables static void * memoryForStruct1 = malloc(sizeof(Struct1) * 10000); int struct1Index = 0; ... // somewhere, I need memory, fast: Struct1* data = memoryForStruct1[struct1Index++]; ... // done with data: --struct1Index; 

Gotchas:

• I have to make sure I don't exceed 10,000
• I need to free memory in the same order that I occupied. (Not my main problem, as I use recursion, but if possible, I would like to avoid it).

---

Inspired by Mihai Maruseyak:

First, I create an int linked list that basically tells me which memory indices are free. Then I added a property to my structure called int memoryIndex , which helps me return the memory occupied in any order. And, fortunately, I’m sure that my memory needs will never exceed 5 MB at any given time, so I can safely allocate so much memory. Solvable.

Answer 1

The system call that gives you memory, brk . The usual functions malloc and calloc , realloc simply use the space specified by brk . If this space is not enough, another brk is created to create a new space. Typically, space increases in the size of the virtual memory page.

Thus, if you really want to have a ready-made pool of objects, then do not forget to allocate memory several times. For example, you can create one 4KB pool. 8KB , ... space.

Next idea, look at your objects. Some of them have one size, some have a different size. It will be a big pain to process distributions for all of them from one pool. Create pools for objects of different sizes (2 degrees are best) and select them. For example, if you had a 34B object, you would allocate space for it from the 64B pool.

Finally, the remaining space can either be left unused or moved to other pools. In the above example, you have 30B on the left. You would split it into 16B , 8B , 4B and 2B pieces and add each piece to your pool.

Therefore, you should use linked lists to manage the predefined space. This means that your application will use more memory than it actually is, but if it really helps you, why not?

Basically, what I described is a combination between a buddy distributor and a slab allocator from the Linux kernel.

Change After reading your comments, it will be quite easy to allocate a large area using malloc(BIG_SPACE) and use it as a pool for your memory.

Answer 2

If you can, take a look at glib , which has a memory that supports this. It is very easy to use and eliminates the need to re-implement it.