2
typedef struct node{
  unsigned int v;
  struct node* next;
}Node;

When allocating at once, the memory used was around 4GB

Node* X= (Node*)malloc(sizeof(Node)*((long)1<<28));

and when allocating each Node dynamically the memory used was almost doubled to around 8GB

temp = (Node*)malloc(sizeof(Node)); //This is run 1<<28 times

Ideally both should take the same amount of memory if everything else stays the same. But the fact that it doesn't happen says that there is an overhead of some bookkeeping in the 2nd approach.

Please explain in detail why this is happening. I would appreciate fine details like the data structures used for bookkeeping using which we can calculate the expected usage of memory.

P.S I am using a 64-bit machine (8 byte pointer) and gcc 4.4.7 compiler.

I was accessing all of the allocated Nodes, so Virtual Memory and RAM used was the same. There is no smart allocation going on.

I will be happy to give out any details about my system if someone can find the time to give a detailed answer about everything happening under the hood.

ma08
  • 3,654
  • 3
  • 23
  • 36
  • 3
    Each memory block you allocate has some book-keeping associated with it (e.g. its length, and its place in the data structure that keeps track of all the allocations) – M.M Feb 29 '16 at 21:48
  • 1) The memory allocation system needs to keep track of what memory is allocated, so there is overhead for each block allocated. 2) The length of block of memories sometimes need to be a factor or some number, so there can be waste for each block allocated. – ikegami Feb 29 '16 at 21:48
  • @M.M If you can give details about the data structure used which causes the overhead and give some numbers, I would accept that as an answer. – ma08 Feb 29 '16 at 21:58
  • Are you compiling with debug flags turned on? Malloc in debug mode often allocates extra space before and after the allocated memory block to make it easier to detect memory corruption issues. – bruceg Feb 29 '16 at 21:58
  • 1
    The details of "how much overhead" will depend on your system's malloc implementation. It's usually part of the standard C library, not part of the compiler (so just saying "gcc" isn't enough information). – Nate Eldredge Feb 29 '16 at 21:58
  • @NateEldredge so are the data structures used for bookkeeping change are dependent on the OS? – ma08 Feb 29 '16 at 22:02
  • 2
    Data structures used for bookkeeping change are dependent on the OS and compiler (as an OS may not exist). They vary _widely_ over platform and time. New schmes for allocation come up from time to time. – chux - Reinstate Monica Feb 29 '16 at 22:08
  • @chux I hoping to see some data structure as part of an answer. As you guys say that it's too platform specific, I guess I will accept the generic answer. Thanks for taking time to respond :) – ma08 Feb 29 '16 at 22:13
  • Recommend a follow on post that details the platform, compiler and seeks to understand - under-the-hood algorithm. With gcc, the source code is usually findable. Note that applying various tools to detect memory leaks, etc, add further overhead. – chux - Reinstate Monica Feb 29 '16 at 22:17
  • @chux I ran valgrind. As far as I know, there were no memory leaks and the memory reported was when not running any analysis tool. – ma08 Feb 29 '16 at 22:18
  • I am not suggesting leaks, I am suggesting tools like Valgrind add to the overhead, more likely skewing the difference you see. Turn it off and then assess memory usage. – chux - Reinstate Monica Feb 29 '16 at 22:19
  • @chux got it. I read your comment wrong. I can confidently say that everything I reported was when running the program vanilla-ly. Anyway I accepted your answer, I will dig around further and see myself as to what's happening and hopefully find an answer and will post it. Thanks for being patient. – ma08 Feb 29 '16 at 22:22
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/104925/discussion-between-chux-and-ma08). – chux - Reinstate Monica Feb 29 '16 at 22:22

2 Answers2

3

The usable memory is the same. But there is overhead with each allocation.

1<<28 overheads is certainly more than 1 overhead.

Further details would required knowing the platform, compiler, and options (including packing). The reasons would vary upon the many combinations.

As commented by @M.M, various allocators cope with bookkeeping in various ways. Typically it is a trade-off between fast allocation/de-allocation and memory usage efficiency.

Packing could affect things. If OP can control packing options, possibility both allocation sizes will reduce - perhaps not proportionally. The structure appears to likely be 12-byte. (not a power of 2) and thus may benefit (size) with packing yet cost reduced access performance.

Another impact is the credibility of the purported memory usage of ~4GB and ~8GB. Smart allocators allocate, but do not "use memory until something interesting is written. See Why is malloc not “using up” the memory on my computer?

Community
  • 1
  • 1
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • If you can give a more detailed answer, that would be great. I already mentioned that it was due to overhead. Don't get me wrong, I am just curious :) – ma08 Feb 29 '16 at 21:54
  • I was accessing all of the allocated memory in a loop. So RAM used was equal to Virtual Memory. – ma08 Feb 29 '16 at 22:08
  • @ma08 does "accessing" mean code was _writing_ different info to the various elements? Hmm I see you assert "no smart allocation" – chux - Reinstate Monica Feb 29 '16 at 22:12
1

Each malloc'd chunk carries a certain overhead and the usable size associated with each malloc'd chunk is often a little bit larger than what you've requested. (You can find the usable size associated with a chunk my calling malloc_usable_size(chunk_ptr); (the prototype is in malloc.h)).

Petr Skocik
  • 58,047
  • 6
  • 95
  • 142