where do the extra bytes go while using Malloc ?

[karthikbalaguru]

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory. So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.

So, there should be wastage of memory for managing the linked list
(heap).
But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

Thx in advans,
Karthik Balaguru

[Ian Collins]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory. So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.
>

That might be one implementation, the working of malloc are not covered
by the standard. Don't forget the value returned by malloc is correctly
aligned for any type.

So, there should be wastage of memory for managing the linked list
(heap).
But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?
>

You can't get something (functionality) for nothing.

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?
>

That's up to the implementation.

--
Ian Collins.

[Filip Larsen]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

While this in principle is an implementation issue it is to my knowledge
fairly common to place (some of) this management data for each malloc
block just in front of the block. Or it was, at least, on the systems I
was using 10-20 years ago.

For example, if you look at the code for malloc in one of the latest
glibc releases it says:

"Minimum overhead per allocated chunk: 4 or 8 bytes. Each malloced chunk
has a hidden word of overhead holding size and status information."

The more detailed description in the code [1] seem to indicate that the
management bytes are placed both in front and at the end of the
application data block.

[1]

http://www.google.com/codesearch?q=file%3Aglibc-2.5%2Fmalloc%2Fmalloc.c+%22malloc_chunk+details%3A%22

Regards,
--
Filip Larsen

[Mark Bluemel]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.

There doesn't have to be a heap. The overheads don't have to be as you
state.

That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory.

Why? 1) If I have the size, I can (perhaps) find the next block of
memory, 2) sizes (and pointers) may not necessarily be 4 bytes long.

So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.

As Richard H has said, putting this more generally, there must be some
overhead involved in managing malloc()ed memory.

The nature and size of the overhead is dependent on the implementation.

So, there should be wastage of memory for managing the linked list
(heap).

It doesn't have to be a linked list - other data structures are
available and may be applicable.

But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

It doesn't allocate the exact size of data requested. It allocates "at
least enough" to satisfy the request, taking into account its management
overheads and the contract it has to provide memory aligned
appropriately for any data type.

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

Where the implementers put them. There is no guaranteed general answer
to the question - you'd need to examine a specific malloc implementation.

If you wish to discuss a specific implementation, I suggest doing it
somewhere other than "comp.lang. c"

Thx in advans,

If you mean "thanks in advance" why not write that?

[santosh]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory.

This is just one possible scenario under one possible implementation.
Pointer sizes can vary, as can the accounting data used by malloc.

So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.

In your scenario eight bytes are needed just to record the minimal
necessary book-keeping information. In most "real world" malloc
implementations rather more space would be set aside.

So, there should be wastage of memory for managing the linked list
(heap).

Not necessarily. If the malloc implementation can embed all necessary
information into the pointer itself. The point is, numerous schemes are
possible and there are many factors responsible for the choice made.

But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

Why should the book-keeping overhead prevent malloc from allocating the
exact amount of data requested? Indeed, though it might allocate more
than what was asked, if it could not allocate at least as much as was
requested, then the implementation is broken.

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

This _really_ depends on the implementation. It could be anywhere from
being embedded in the pointer itself, behind the allocated block, after
the allocated block, elsewhere in memory, on a file on disk, on a
remote server on a network... you get the idea?

[Richard Tobin]

Re: where do the extra bytes go while using Malloc ?

In article <ffkjhr$snq$1@a ioe.org>,
Mark Bluemel <mark_bluemel@p obox.comwrote:

>That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
>pointer to the next block of memory.

>Why? 1) If I have the size, I can (perhaps) find the next block of
>memory,

And why would you need to keep the allocated memory in a linked list
at all? If you were using such a list, it would be of free memory, in
which case the allocatable memory itself could be used for the link.
So (granting the other assumptions) there would not be an 8 byte
overhead but a 4-byte overhead with an 8-byte minimum.

What's more, if you only allocate in certain sizes you can keep
separate lists for each size, which makes finding a suitable size
block easy, and removes the need for storing the size in free blocks.
And there are ways to avoid storing the size at all, by allocating
different size blocks from different areas of memory.

-- Richard
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[James Kuyper Jr.]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory. So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.

As many people have pointed out, the amount of space that is needed can
differ from one implementation to another, and the way in which that
information is stored can also be implementation-dependent. You
shouldn't write code that depends upon such details.

However, I've often found that it's useful when thinking about a
function, to have a particular implementation in mind. Without a
specific implementation in mind, it's easy for a newbie to get lost.
Just keep in mind that any particular implementation might be quite
different from the one you're thinking of. Here's a couple of models
that you can use for that purpose:

One approach: when malloc(n) is called, memory for at least n+x bytes is
actually allocated, for some value of 'x'. The first x bytes of the
allocated space is used to store the control information you're talking
about; the value returned by malloc() actually points at the first byte
after the control information.

Second approach: all allocations are rounded up to the next power of
two. malloc() maintains blocks of memory for each power of two currently
in use, from which it allocates one piece at a time. When free() is
called, it can figure out the rounded-up allocation size (it doesn't
have any need to know the original requested allocation size), just by
determining which of those blocks of memory is pointed at by the pointer
being free()d.

[user923005]

Re: where do the extra bytes go while using Malloc ?

On Oct 23, 12:41 am, karthikbalaguru <karthikbalagur ...@gmail.com>
wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.

Not on a 16 bit machine or 64 bit machine.

That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory.

Unless it is 8 bytes + 8 bytes or 2 bytes + 2 bytes or something else.

So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.
>
So, there should be wastage of memory for managing the linked list
(heap).
But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

You are considering some particular implementation. Your actual
allocator may or may not work like that.

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

When there is wasted space, it does not go anywhere. It just gets
wasted. If you are worried about it because of tight space
requirements, write your own sub-allocator.

Look:

https://www.archmemory.com/index.asp?PageAction=VIEWCATS&Category=44417

1GB DDR2-800 ECC Module $94.99

Now calculate how much time you would spend trying to save a GB of RAM
by finagling little bits here and there.
That should tell you something important.

[glen herrmannsfeldt]

Re: where do the extra bytes go while using Malloc ?

Richard Heathfield wrote:

[This reply written in comp.lang.c, and followups set to that group.]
>
karthikbalaguru said:

>>In the case of heap , to keep track of a single chunk of memory it
>>requires 8 bytes of information.

Not necessarily. It might need only 1, or it may need a dozen or a
thousand.

>>That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
>>pointer to the next block of memory.

The way malloc() works, keeping track of the length of the allocated
block, requires at least that the length be stored somewhere.

The allocator used by OS/360, called GETMAIN/FREEMAIN, works a little
differently. There is no overhead in the allocated memory.
The length and starting address are specified for FREEMAIN.
One can free part of an allocated region, even as a hole in the
middle of a previously allocated region. The result is that the
free memory contains a linked list, but the allocated memory has
no overhead. (I believe allocations must be in multiples of
eight bytes, though, if no other reason than to guarantee alignment.)

I do wonder, though, why C supplies no routine to determine the length
of an allocated block.

-- glen

[santosh]

Re: where do the extra bytes go while using Malloc ?

glen herrmannsfeldt wrote:

<snip>

I do wonder, though, why C supplies no routine to determine the length
of an allocated block.

Because it's trivially easy to do this in the program, if wanted?

[CBFalconer]

Re: where do the extra bytes go while using Malloc ?

Filip Larsen wrote:

karthikbalaguru wrote:
>

>How does malloc/calloc then allocate the exact size of data as
>there must be some wastage of memory that has to be taken into
>account while allocating in heap memory (Memory consumed for
>managing the information in terms of linked list) ?

>
While this in principle is an implementation issue it is to my
knowledge fairly common to place (some of) this management data
for each malloc block just in front of the block. Or it was, at
least, on the systems I was using 10-20 years ago.

You can examine the C code for a fairly portable malloc in
nmalloc.zip, written for DJGPP. A malloc package cannot be
portable, since it depends on system knowledge. However nmalloc is
pretty close to standard C, requires the system provide an sbrk()
function to supply memory, and compiles under gcc. The gcc
requirement is due to a set of development macros, none of which
are in operation for the final package. You can find nmalloc.zip
at:

<http://cbfalconer.home .att.net/download/>

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>



--
Posted via a free Usenet account from http://www.teranews.com

[Malcolm McLean]

Re: where do the extra bytes go while using Malloc ?


"karthikbalagur u" <karthikbalagur u79@gmail.comwr ote in message

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?
>

The trick is to store the control block just before the pointer you return.
Then free() subtracts the block from the pointer passed to it, and has all
the information it needs to make the memory avaialble for further
allocations.

That's not the only way of doing it, and in fact most modern systems use a
rather different method for small allocations, but it is how a simple
malloc() works. If you check my website you will find a memory allocation
package. It is one of the free sample chapters of Basic Algorithms.


--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Malcolm McLean]

Re: where do the extra bytes go while using Malloc ?


"glen herrmannsfeldt" <gah@ugcs.calte ch.eduwrote in message

I do wonder, though, why C supplies no routine to determine the length
of an allocated block.
>

Should you return the length allocated or the length asked for? If the
second you need an extra field, if the first you need to educate programmers
not to use the function as a lazy array length.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Mark Bluemel]

Re: where do the extra bytes go while using Malloc ?

karthikbalaguru wrote:

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory. So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.
>
So, there should be wastage of memory for managing the linked list
(heap).
But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?
>
That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

British readers of the newsgroup might identify with me on this thread.

I can imagine Mark Benton in his bank manager persona explaining that
the extra bytes are saved up for the Directors' christmas party... Quite
what the Directors do with the bytes, I haven't worked out.

[karthikbalaguru]

Re: where do the extra bytes go while using Malloc ?

On Oct 24, 3:50 am, "Malcolm McLean" <regniz...@btin ternet.comwrote :

"karthikbalagur u" <karthikbalagur ...@gmail.comwr ote in message

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

>
The trick is to store the control block just before the pointer you return.
Then free() subtracts the block from the pointer passed to it, and has all
the information it needs to make the memory avaialble for further
allocations.
>
That's not the only way of doing it, and in fact most modern systems use a
rather different method for small allocations, but it is how a simple
malloc() works. If you check my website you will find a memory allocation
package. It is one of the free sample chapters of Basic Algorithms.
>
--
Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

Thx to all of you for the info :):)

Karthik Balaguru