where do the extra bytes go while using Malloc ?

Discussion in 'C Programming' started by karthikbalaguru, Oct 23, 2007.

  1. 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
    karthikbalaguru, Oct 23, 2007
    #1
    1. Advertising

  2. karthikbalaguru

    Ian Collins Guest

    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.
    Ian Collins, Oct 23, 2007
    #2
    1. Advertising

  3. [This reply written in comp.lang.c, and followups set to that group.]

    karthikbalaguru said:

    > Hi,
    > 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.


    C doesn't require that 4 bytes are used for pointers. On some systems, 2
    suffice. On others, 8 are needed. Indeed, 1-byte pointers are feasible
    (think 32-bits-per-byte DSPs, for example).

    > 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.


    Well, to be more general, yes, it is likely that the memory management
    subsystem will incur a per-call overhead (although C does not mandate
    this).

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


    There can be, yes.

    > But, How does malloc/calloc then allocate the exact size of data


    The C Standard requires that malloc etc return NULL if they fail, or a
    pointer to the requested amount of memory if they succeed. Thus, those
    functions must allocate *at least* the amount of memory requested (or
    return NULL). But the Standard doesn't forbid them from allocating more,
    and indeed they might do so. Or they might not, of course.

    > 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 ?


    You mean, where is the management info stored? Well, it depends on the
    implementation. Several possible solutions exist. If you really need to
    know, C can't tell you - but your implementation's documentation might be
    able to.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
    Richard Heathfield, Oct 23, 2007
    #3
  4. karthikbalaguru

    Filip Larsen Guest

    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:glibc-2.5/malloc/malloc.c "malloc_chunk details:"



    Regards,
    --
    Filip Larsen
    Filip Larsen, Oct 23, 2007
    #4
  5. In article <ffkjhr$snq$>,
    Mark Bluemel <> wrote:

    >> 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
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Oct 23, 2007
    #5
  6. karthikbalaguru

    Mark Bluemel Guest

    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?
    Mark Bluemel, Oct 23, 2007
    #6
  7. karthikbalaguru

    santosh Guest

    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?
    santosh, Oct 23, 2007
    #7
  8. 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.
    James Kuyper Jr., Oct 23, 2007
    #8
  9. karthikbalaguru

    user923005 Guest

    On Oct 23, 12:41 am, karthikbalaguru <>
    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.
    user923005, Oct 23, 2007
    #9
  10. karthikbalaguru

    santosh Guest

    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?
    santosh, Oct 23, 2007
    #10
  11. 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
    glen herrmannsfeldt, Oct 23, 2007
    #11
  12. karthikbalaguru

    CBFalconer Guest

    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
    CBFalconer, Oct 23, 2007
    #12
  13. "karthikbalaguru" <> wrote 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, Oct 23, 2007
    #13
  14. "glen herrmannsfeldt" <> wrote 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
    Malcolm McLean, Oct 23, 2007
    #14
  15. karthikbalaguru

    Mark Bluemel Guest

    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.
    Mark Bluemel, Oct 24, 2007
    #15
  16. On Oct 24, 3:50 am, "Malcolm McLean" <> wrote:
    > "karthikbalaguru" <> wrote 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
    karthikbalaguru, Oct 24, 2007
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. martin
    Replies:
    4
    Views:
    3,506
    mikeb
    Mar 6, 2004
  2. mathieu
    Replies:
    3
    Views:
    585
    Bo Persson
    Sep 4, 2009
  3. Robert Jackson

    Strange extra f added to bytes object

    Robert Jackson, Oct 6, 2013, in forum: Python
    Replies:
    3
    Views:
    111
    Ian Kelly
    Oct 7, 2013
  4. MRAB
    Replies:
    0
    Views:
    90
  5. Ned Batchelder

    Re: Strange extra f added to bytes object

    Ned Batchelder, Oct 7, 2013, in forum: Python
    Replies:
    2
    Views:
    120
    Robert Jackson
    Oct 7, 2013
Loading...

Share This Page