Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

All programs I have seen organize their data memory into one or more call stacks (usually fixed size, but sometimes not), the heap, and static memory. Lately thread-local static storage has been added to this as well.

Have there been any attempts to organize data memory layout in a radically different way, e.g. without the call stack? Or organize memory in a different way that accomplishes the same thing?

share|improve this question
    
Depends on what you mean by "stack". You can put the call stack frames into the heap (link them with pointers). Then you don't have a dedicated linear memory region for the stack, but conceptually you still have a call stack. –  delnan Dec 29 '13 at 0:14
    
and depends on what you mean by "recently". I think thread local storage is as old as threads. But previously was accessible via system calls, whereas now newer languages give you access to it directly. –  DXM Dec 29 '13 at 3:06
    
The call stack is necessary because procedural functions need to know who called them so they can return results and continue execution. The current mechanism if doing that is actually quite cheap in terms of CPU cycles and with x64 at least, almost all function args are passed through registers –  James Dec 30 '13 at 0:39
2  
You may find Eric Lippert's post, Why Have a Stack? of interest. His main point is that a stack provides an efficient, simple way to track memory locations. He discusses one alternative in a several much older posts, Continuation Passing Style. –  Brian Dec 30 '13 at 5:16

2 Answers 2

You might want to step back and see where and why those existing models come from. When a process is created, it is simply given a flat storage area which is simply indexed from 0 to N. Because this storage area (talking about RAM here) is backed by a dedicated hardware and some fancy semiconductors it happens to be pretty fast, but it's not the only one of its kind. Other devices such as hard drives are essentially the same thing, flat space addressable by an index, but many orders of magnitude slower.

The reason why "a heap" exists is because it would be impractical for each application to attempt to manage the use of RAM by itself. Way back in the day, that's exactly how it happened, programmers planned ahead of time exactly what each RAM location would be used for. As software got more complex someone said, wouldn't it be nice if I could just go to some black box and say "I need 10 bytes so gimme" and not have to worry about all the intricate details of where and how those 10 bytes come from or how they are reclaimed. That's what a heap is, doesn't really get more basic then that.

Each time a thread is created, there are some data structures (and a stack), which are acquired using the same "gimme operation" I just described. A stack just about universally used because it fits perfectly with function call stack frames and their LIFO nature. In theory, each function invocation and local variables could be allocated on the heap, but that would simply be too expensive, compared with just a few assembly instructions that it takes to update stack pointer (ESP on x86) register.

Thread local storage (TLS) is also built on top of heap. When a thread is created, as part of a trip to the heap to allocate memory for management structures, a separate space for TLS is also allocated from the heap.

So in the end, all you really have is a generic memory allocator (i.e. the heap) and everything else is a specialized form on top of that. In other words, if you are willing to give up some aspect of "I want to allocate as much (or as little) as I want, keep it for as long as I want and free whenever I want", you could get away trading off generic heap allocator for another model that offers speed but at the cost of some other limitation.

Take stack. It is incredibly fast when compared to the heap, but the two trade offs are 1) you don't control when memory is freed; instead once the function exits, whatever you allocated is gone and 2) because stacks are generally limited in size, you should be careful allocating large amounts of data directly on the stack.

Another type of "memory model" is the Virtual Memory Manager (VMM) offered by just about every major OS via system calls. VMM is very similar to heap in a sense that you can ask for any amount of memory and keep it as long as you want. However, the limitation is that you can only allocate memory in page size multiples (e.g. 4KB) so using VMM directly would cause a lot of overhead in a typical application that often allocates 8-24 bytes at a time. In fact, just about every heap implementation is built on top of VMM specifically for purposes of allowing a very generic, non-specialized, small-block allocation. Heap goes to VMM whenever it needs more memory and then doles out many small chunks of that memory to the application.

If you have an app, that has a need for allocating large blocks, you might consider going directly to VMM, although some heaps have an if-statement inside malloc() and if block size is greater than some threshold, they simply go to VMM for you.

Another form of allocators instead of directly using heap, would be pools. A pool is a specialized allocator where all blocks are of the same size. Pools (just like stack and TLS) are built on top of heap or VMM. Pools are useful in places where you allocate a lot (millions) of short-lived, small objects of the same size. Think a network service processing incoming requests. Each client requests may result in same N byte structure being allocated to handle that request. The trade off with using pools is that each pool only handles one block size (but you can create multiple pools). The advantage of pools is that because all objects are same size, it doesn't require intricate logic. Instead, whenever you need a new block, it just gives you the one that was recently freed. So it kind of behaves like a heap in terms of giving you blocks that you can hang on to for as long as needed, but it's alloc/free operations are almost (but not quite) as cheap as using stack.

And lastly, remember that hard drive thing I mentioned way up top. You could have a memory model that behaves like a file system and duplicates same idea of directory entries and i-nodes to allow you hierarchical allocation of data blocks where each data block as addressed with a path. That's exactly what tmpfs does.

Beyond the stuff I mentioned, I'm sure there are other more specialized models, but in the end since everything is based on flat address space (that is until some genuis comes up with some kind of weird-a$$ non-flat space), it all goes back to that generic "gimme" allocator which is either VMM or the heap.

share|improve this answer

The only cases I can think of are in specialised hardware where you might have everything running in fixed locations in memory. Pretty much everything in the current memory model is required if you want fully flexible programs.

Without the stack you can't have local variables, call stacks, etc. Anything else you write to implement that is going to end up looking a lot like the stack.

Static memory and the heap you could potentially drop for certain applications, but again you are going to need them back in some form or other to do anything more advanced.

So anything you invent to replace one of these three is going to end up looking a lot like one of these three in the end...

To approach it from the other angle, what might you add that is new? You could potentially argue things like graphics/physics processors/cpu caches/etc are a new memory location, but really they are just a separate instance of or a way of speeding up access to the existing models.

...so until someone comes up with a giant conceptual leap of some kind I think we are unlikely to see any major changes in this area for a long time...

share|improve this answer
3  
Most people tend to assume that the current way is the best/only way, and if given a blank slate would just copy what already exists. The other people are the ones who actually advance technological progress. Not to say that I personally know of any serious competing models (unless you count quantum computers), but claiming that anything that one could come up with would look the same as what already exists is essentially a form of circular reasoning. –  Aaronaught Dec 29 '13 at 2:01
    
@Aaronaught: the flip-side to your argument is that other people spend tons of time, money and energy thinking outside the box and for every 1000 (maybe much more) of them, one might eventually advance technological progress, while the rest get nowhere. Whereas the first group, who one might consider more practical, takes these existing models as-is and innovates on top of them :) –  DXM Dec 29 '13 at 3:05
    
@aaronaught I think I covered that with "so until someone comes up with a giant conceptual leap of some kind" ;) If you have a better alternative model feel free to suggest it... if not it feels a bit hypocritical to complain about "some people" when you are one of them :) –  Tim B Dec 29 '13 at 10:59
    
@DXM: So? Did I say that we should all be investing our time into researching new memory models? I was only pointing out the (significant) flaw in the claim that a person can only invent things that have already been invented. –  Aaronaught Dec 29 '13 at 19:46
    
A claim which I never made... –  Tim B Dec 29 '13 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.