EverybodyOrzInSomeWay's blog

How does dynamic memory allocation work?
By EverybodyOrzInSomeWay, history, 4 years ago, In English

Earlier today I was writing a dynamic segment tree for the problem 915-E

My solution gave Memory Limit Exceeded Verdict. Then I made a small change in my code, surprisingly it got accepted.

Submission with MLE:-

node* create()
{
	node *tmp=new node;
	// Some more lines to initialize the variables
	return tmp;
}

Accepted Submission:-

node ns[15000000];
int cnt=0;

node* create()
{
	node *tmp=&ns[cnt++];
	// Some more lines to initialize the variables
	return tmp;
}

I was very confused I had no idea why it worked. I even added the assertion assert(cnt < 15000000) and it still passed. I do not understand why my second solution is consuming less memory. It probably has something to do with how dynamic memory allocation works. Can anyone explain?

Here is the full code:

  • Vote: I like it
  • +87
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Someone please help this poor soul!

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Probably has to do something with byte alignment — if each time a new chunk of memory is not aligned perfectly, it will take some extra padding bytes.

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

https://stackoverflow.com/questions/34662323/c-new-allocates-more-space-than-expected
Last but not least, a successful request to give you 8 bytes of memory might well have allocated a much larger chunk behind the scenes. After all, asking malloc/new for a specific amount of memory only guarantees that you'll get a chunk of at least that size, not exactly that size.

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Heap allocation can require some additional memory for each allocation (4 or 8 bytes). Seems the required number $$$N$$$ of node structs is very large and $$$N * sizeof(struct \space node)$$$ is near ML of 256M (15000000 * 16 bytes). With allocations the solution consumes 15000000 * 20 (or * 24) bytes which is MLE.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +29 Vote: I do not like it

General purpose memory allocators have to handle the program requesting new memory and freeing old memory at arbitrary points during execution. There are many ways to do this but they all have some memory overhead. One common way is for each chunk of memory to store a pointer to the next available chunk. If you look up "program your own malloc" or something similar there will probably be some resources.

For competitive programming, usually you just want to allocate memory and you never have to free it. I would almost never use the default new in CP. What you did is sometimes called a bump allocator and is what I've seen a lot of people do. You can replace new if you want like in

https://github.com/kth-competitive-programming/kactl/blob/master/content/various/BumpAllocator.h

https://github.com/kth-competitive-programming/kactl/blob/master/content/various/BumpAllocatorSTL.h

This claims the overhead for the default new is 16 bytes per object, but it's probably compiler/OS dependent.

Further reading:

https://en.wikipedia.org/wiki/Memory_management

https://en.wikipedia.org/wiki/Allocator_(C%2B%2B)

→ Reply