Hello everyone! I've lurked enough, now it's the time I ask one more question.

I've been pondering on this for months, and I didn't feel ready to ask until now.

Basically, when I allocate a new variable, I just have to move the stack pointer in order to leave some room for it in the stack. When I want to remove the last variable in the stack, I can move the stack pointer in the opposite direction in order for the variable to be outside of the stack range.

This is good, since you just need to initialize variables in the reverse order that you will want to remove them.

The fragmentation problem arises when you want to create a variable type that can grow without having to be continuous such as a linked list.

Just to be sure we are on the same page, here is the definition of a linked list:

More info: http://en.wikipedia.org/wiki/Linked_list

Once you start introducing linked lists, it becomes impossible to remove variables in a general way for all programs since there is no real way of knowing which variable will be last in the stack at compile time.

The only thing I can think of to fix this problem is to have a sort of garbage collector. Is that were a garbage collector comes in? Or is there something simpler that wouldn't have a too big performance impact?
_______________
Example code snippets are welcome, but what I am looking to find is the theory explaining how it should be done.

Hopefully this won't be too hard to understand. I've tried to explain this as best as I could.

Linked lists are really easy to handle. For my systems I use two list head pointers where one list is "used" sections and the other is "free" sections. As the memory is used or freed it just moves sections from one list to the other. You can also compact the lists occasionally to bring all sections of the same type into contiguous memory locations and then realloc the memory to free up space and return it to the OS.

Garbage collectors are very different things and work in an entirely different way. They usually end up being very complicated (as with most HLL related things) and I would hesitate before deciding upon such a complex solution.

one of the best solutions.
in my ART (Assembly RunTime) you will find one of my dozens implementations of something concerning the method above, from line 227:
http://code.google.com/p/x64lab/source/browse/develop/shared/art.asm

that works very good and fast, using size of chunks from the equates here:
http://code.google.com/p/x64lab/source/browse/develop/shared/art.equ
but i dont use it anymore because i have now one even faster and better
(but no open source sorry) i called memmuth (tm) for the record.
this is but the ancestor of it.

Cheers,

Thanks a lot so far! I think my synapses are connecting.

If I understand correctly, when there is an element from the "free" sections at the end of the stack, then it is safe to remove it from the stack range.

I've done a few diagrams to make sure I get this right:

General case:


General case with the "free" sections:


I'm guessing this next case would be when I would be required to move the "Used List Element 3" above the variables that need to be removed? (Or overwriting them.)


Note: The left stack is before the stack pointer has been moved and the right stack is after.

In other words, the "free" sections can only be removed when they are at the end of the stack. If I would want to remove them when they are in the middle, I would have to move all the other variables up and overwrite it doing so.

Am I getting this right?

basically yes.
but it seems you are trying to stack linked lists of mem-chunks.
i.e. mixing stack+lists.
if so, well, this is not suggestable because a very complex management of the stack pointer
is required. anyway that stack size of your allocator would result not growable, and consequently by reserving/using the maximum of it
(on Win 64bit max stack size is ~1Gb),
your allocator should do acrobatics to distinguish/trace the areas marked free/used from those stack areas used by the client app for itself,
and those the client app requires from your allocator.
ergo: memory becomes very fragmented and allocator slow because it accesses very distant areas/pages. exactly what we want to avoid.
(reducing the reloading of memory pages into the cache is an imprtant goal too)

here explained some methods,
http://www.memorymanagement.org/articles/alloc.html
http://gee.cs.oswego.edu/dl/html/malloc.html

Cheers,

Why not use the heap for the allocation?

1. call HeapCreate as your function begins
2. in the function call HeapAllocate as many times as you need
3. call HeapDestroy as your function ends (no need to call HeapFree)

mmh, yes but once you have malloc why avoid it ? anyway for an allocator i suggest VirtualAlloc because very flexible.
other case is under portability restrictions wher i cannot see other methods than LIBC-ing it.
some quasi-benchmarks here
http://f0dder.reteam.org/memalloc.htm

Cheers,

Well... my mind just got blown! This thread is really amazing already.

Sorry not to have responded earlier, I was still processing all that I had learned. I have gone through everything that was posted here a couple times, reading the articles that were linked. I also found a book about memory allocation which seems pretty good by Charles Weir and James Noble (http://www.smallmemory.com/book.html) (mostly chapter 6). It had this nice analogy:

Changing the subject slightly, there is one question that came to my mind after seeing the stack memory limit, does it mean there is something else than the stack that I can use to store my program's memory? Does it have to do with the heap? (Or is the heap separated from the stack?)

(I probably could have looked up these questions easily, but I thought it was appropriate to ask them here.)

yes, why not. and the matter is not so obvious as it seems.
i will try using some guidelines and hints instead of
explaining one more time how the wheel works.

because everything has a limit in size,
- the stack
- the process space

and in hardware speed:
- the BUS
- the DRAM modules
- the cache

your app should have what i call magnitudo
i.e. an awareness of data quantities it manages.
this awareness should be a MUST, a policy

1) by design
2) if you want your app to work better than other software
3) if your app is "Umweltfreundlich" i.e it tries to reduce
damages against the environment.

you choose a memory system,(or an OS) accordingly.
when you say, for example

format PE64 GUI 5.0
heap 2000000h
stack 100000h

you'll agree to
a) the process rules assigned to your app by windows
b) the OS loader will try to reserve your app that sizes of heap and stack
c) debugger consequently will try to adjust debugging to those values.

then further knowledge about those params on windows PE tell us how
behave stack and heap of your app on windows, according its process-rules.

anyway the question again is wether your app is
aware of the quantities it manages. because if your app
manages movies in the size-order of Gbytes, well, an alternative
memory system should apply here, whenever keeping those above
stack-heap values of your app constant.
an alternative for big files may be by using memory mapped files
or Virtual allocation.

also, different memory systems may live together (and most do in the
best software) and co-operate together for better performances.

thus definitions of heap, stack, virtual spaces, etc.,
you can find it everywhere on the net, OS accordingly.

Cheers,