Thread: Buffers , heaps , stacks ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    43

    Buffers , heaps , stacks ...

    a bit ago i was searching about buffers , heaps and stacks .. trying to find out what each of one does . but unfortunately i got confused so decided to come hear and ask u guys .. what does each one do ? i read about the stack that it holds some data with the LIFO system .. but if it holds temporary data .. what's the RAM's use then ? stuff like that really confuse me .. anyway all help is really appreciated ..

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by BlaX View Post
    a bit ago i was searching about buffers , heaps and stacks .. trying to find out what each of one does . but unfortunately i got confused so decided to come hear and ask u guys .. what does each one do ? i read about the stack that it holds some data with the LIFO system .. but if it holds temporary data .. what's the RAM's use then ? stuff like that really confuse me .. anyway all help is really appreciated ..
    Since you mention heap and stack in the same context, I'll assume you're asking about the execution stack, not the stack as a general purpose data structure.

    If you think about how functions execute, they execute in a LIFO manner -- if a function A() calls a function B(), then A() cannot finish until B() has finished. In other words, as code executes you descend a sequence of calls and then ascend back up. This is exactly what a stack does. So it is natural to use a stack as the data structure to maintain the state associated with function calls. The entries of the stack are "activation records," and yes, they are temporary in the sense that each record exists only for the duration of the call it represents.

    Whenever a function is invoked, an activation record for it is created and pushed on the stack. When the function returns, this record is popped. This activity always occurs at the top of the stack, since as I already mentioned, only the most deeply nested function can return. (Let's leave aside the complications of something like longjmp() )

    The heap is a more flexible data structure in that memory can be allocated and freed from the heap in any order desired. It is not limited to LIFO. This means that when you need data to exist in a pattern which can't be described by LIFO, you need something like a heap. For instance, if some deeply nested function creates a piece of data and wants to return it to a higher level, this data must come from the heap -- if it came from the stack, the data would be destroyed when the function which generated it returns.

    A "buffer" is a piece of memory used to store something. If that sounds vague, that's because it's a vague concept. Buffers can come from either heap or stack, depending on how they are intended to be used. A buffer which only has to exist for the duration of a single function's activation, can be placed on the stack. If the lifetime of a buffer has to EXCEED the lifetime of the function which created it, or if its lifetime is not immediately clear when it is created, then it must come from the heap.

    Another factor which plays into whether a piece of data goes on the heap or the stack, is whether the size of that data is known at compile time. In standard C and C++, local arrays must have a size that can be determined at compile time. For instance, you can't do this:

    Code:
    int func(int size)
    {
        int array[size]; // size is not determined at compile time
    }
    In this case, even if the lifetime of the array is LIFO, you still must use the heap because it's not possible to allocate dynamically from the stack. This is not a limitation of stacks -- it is a limitation of the C and C++ languages.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    Registered User
    Join Date
    Feb 2008
    Posts
    43
    so functions call use the stack .. that was something i knew .. but lods of new info about the heap and the buffer .. but the image is still vague
    where are these things found in ? are they all in the RAM ? where is the buffer ? the heap .. ? where's the stack found ?

    so no variable is stored in the stack (neither local nor global .. or are the locals in the heap)? or just calls use the stack ?

    i didnt really get what's the heap ? is it something physical .. or its just a mechanism that allocates blocks of memory during runtime?

    and u mentioned "Buffers can come from either heap or stack" what does that mean ? and what is the buffer's role ? is it also a part of RAM ?

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by BlaX View Post
    so functions call use the stack .. that was something i knew .. but lods of new info about the heap and the buffer .. but the image is still vague
    where are these things found in ? are they all in the RAM ? where is the buffer ? the heap .. ? where's the stack found ?
    All of these things are in RAM. Stacks and heaps are just ways of organizing RAM. The RAM itself is just a huge array of bytes. We impose data structures on this RAM as needed.

    so no variable is stored in the stack (neither local nor global .. or are the locals in the heap)? or just calls use the stack ?
    Local variables are stored on the stack. In fact, declaring local variables is the only way to put things on the stack.

    i didnt really get what's the heap ? is it something physical .. or its just a mechanism that allocates blocks of memory during runtime?
    The latter. The "heap" just means memory which is reserved for dynamic allocation. The way the allocations are managed is up to the dynamic allocation system.

    and u mentioned "Buffers can come from either heap or stack" what does that mean ? and what is the buffer's role ? is it also a part of RAM ?
    A buffer's role is to simply store data. Usually a buffer means an array of something -- typically a piece of memory which holds a single piece of data is not called a buffer. And yes, buffers are in RAM.

    Here is a buffer that comes from the stack:

    Code:
    void func()
    {
        char buffer[1024];
    }
    And this buffer comes from the heap:

    Code:
    void func()
    {
        char *buffer = malloc(1024);
    }
    In the latter case, we have a local variable "buffer" which is stored on the stack (since it's a local variable, by definition it is on the stack). But this variable is a pointer which points to a piece of memory that was allocated on the heap.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by BlaX View Post
    and u mentioned "Buffers can come from either heap or stack" what does that mean ? and what is the buffer's role ? is it also a part of RAM ?
    A buffer is literally how many keys you press before something happens. What you type is usually input, and input must persist long enough to be processed. Any memory which holds input can potentially be called a buffer.

    That is vocabulary only... your later comment gives me the impression that you believe it is something more. While RAM probably holds most buffers you will use, you could use other storage.

    Also, it shouldn't really matter where these things are in the context of programming as most if not all languages will be sufficiently high-level so that you do not need to think about that.

    Allow me to assume the converse of what brewbuck thought and talk about the data structures heap, stack and queue.

    but unfortunately i got confused ... i read about the stack that it holds some data with the LIFO system ..
    This describes a queue. A queue is a sequence of items that must be processed in a certain order and that difference from stacks is of import. Stacks will typically let you decide how to process items, depending on how you build the stack. Hence you can build a stack and end up with a type of queue.

    A heap on the other hand is any structure which holds to the heap property.

    I suspect that you read about these data structures and then applied what you learned to the wrong area. The 'heap' you've probably been wanting to know more about is less ambiguously known as the "free store" and has very little to do, even, with how the computer works.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Heap and stack is all RAM. There is no concrete definition of what memory should be stack or heap in systems in general, but each system has it's convention, e.g. Linux will put the stack at an address just under 3GB, whilst Windows puts the stack at an address around 1.2MB. The heap is somewhere else, and whilst there are CONVENTIONS, there is no defined space that is heap in general - it is entirely up to the OS designer to set aside some memory to be used as heap (and it is really an arbitrary choice). Also, you can write assembler code that "moves" the stack if you want, and as long as the stack is at valid memory, it is perfectly fine to do that. [Although this is of course not something I'd recommend beginners to do - you need to seriously understand what's going on to be able to move the stack around in a system].

    Buffers is not a defined type of memory [in my nomenclature at least]. There are all kinds of things called "buffer" in computers, it could be a piece of hardware, or a piece of memory (RAM) used for some sort of "holding stuff" purpose, e.g. an input buffer that holds what you have typed in so far, before the program itself has processed the data.

    The difference between heap and stack is that the stack is "self cleaning" - that is, when you return from a function, anything on the stack has automatically been cleared when you get back to the previous level. The heap, you call malloc() or new [or some such thing] to get access to memory, and when you no longer need it, you MUST free it, using the opposite function of the "get access", such as free(), delete or some other function to "release" the memory back to the system to use for other purposes.

    Locals are all on the stack.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Feb 2008
    Posts
    43
    that really lightens up all... thank you

    so buffers are just arrays .. ?

    like if u have int arr[100] arr is a buffer ? (since u said "Usually a buffer means an array of something")

    and are all prone to overflow ?

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by BlaX View Post
    that really lightens up all... thank you

    so buffers are just arrays .. ?
    You're asking us to define something that has no concrete definition. A buffer is usually used to store data for later processing, but that's about the best definition I can give.

    like if u have int arr[100] arr is a buffer ? (since u said "Usually a buffer means an array of something")
    Whether "int arr[100]" is a buffer depends on how it is used. If it is used to store transient data, it's probably a buffer. If it's used to store a lookup table, I would not call it a buffer.

    And yes, any piece of memory is prone to overflow if proper bounds checking is lacking.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    >> and are all prone to overflow ?

    Well no. If it's just an array, then yes, generally. But if it's a piece of hardware, or something that you didn't write (for lack of a better description) then no. For instance, text displayed on the screen can be line buffered like input is. But the buffer being used is flushed when it is full, automatically, so there is no potential for overflow there. As a rule, consider arrays prone to "overflow" (out of bounds access, rather).

    But you wanting specific information about something so general is kinda funny (in a nonpejorative way). It really depends on what.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by whiteflags View Post
    >> and are all prone to overflow ?

    Well no. If it's just an array, then yes, generally. But if it's a piece of hardware, or something that you didn't write (for lack of a better description) then no.
    Hardware usually relies on software to do the right thing with limited resources. Many hardware buffers are ring buffers, which you can "overflow" by writing too many elements before the hardware has a chance to empty the buffer. In such a case, you will lose data.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 01:11 PM
  2. Reading in 16 and 24-bit audio data into (32-bit) integer buffers
    By theblindwatchma in forum C Programming
    Replies: 2
    Last Post: 04-13-2008, 11:12 PM
  3. Please Help Me With This Code Of Implementing Stacks
    By raghu_equinox in forum C Programming
    Replies: 3
    Last Post: 10-19-2006, 07:22 AM
  4. ...multiplication using stacks
    By iiwhitexb0iii in forum C Programming
    Replies: 1
    Last Post: 10-09-2006, 01:28 AM
  5. Stacks stacks stacks
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 06-06-2002, 02:01 AM