Are there stackless or heapless implementation of C++?

Question

C++ standard does not mention anything about the stack or the heap, they are implementation specific, which is true.

Even though they are not part of the C++ standard, we end up using them anyway, so much that it's like they are part of the language itself and have to be taken into consideration for memory or performance purpose.

Hence my question are there implementations of C++ that doesn't use stacks and heaps?

Quadrumanous

I don't know how you would do dynamic storage allocation without something that was effectively a heap. The call stack could be heap-based. Don't know of any implementations. – Subsidence

I've used heap-less versions of C. It was a real pain. A heap-less version of C++ would be possible, but painful. I don't think you could do without the stack. – Amoral

I've built compilers that use heap-base allocation of activation records. There's nothing conceptually hard about it, or would be affected by C++ (the language has no rules about "requiring stack-based activation records), so I don't see a technical issue. Building a real compiler is hard, and unless there's a specific, strong motivation its unlikely one would get built. – Subsidence

@Ira Baxter Crays used heap-based call stacks, you can see the scars of portability with that in the source of many implementations of alloca – Steamboat

Answer 1

Others have already given good answers about the heap, so I'll leave that alone.

Some implementations (e.g., on IBM mainframes) don't use a stack as most people would think of it, for the simple reason that the hardware doesn't support it. Instead, when you call a function, an activation record (i.e., space for the locals, arguments, and return address) is allocated from (their version of) the heap. These activation records are built into a linked list.

From a purely abstract viewpoint, this is certainly a stack -- it supports last-in, first-out semantics, just like any other stack. You do have to look at it pretty abstractly to call it a stack though. If you showed people a diagram of the memory blocks linked together, I think it's safe to guess most programmers would describe it as a linked list. If you pushed them, I think most would judge it something like "yeah, you can use it in a stack-like manner, but it's still a linked list."

Monomolecular

Could you please point me to any resource that would provide some technical details about such "stackless" IBM implementations? A specific machine model and language implementation, if such information is still available anywhere. – Gentleness

@AndreyT: IBM 360/370/3080/... are the architectures in question. They don't have a stack pointer register. The "call" instruction is named BAL (branch and link) which stores your current PC in a designated register, then branches to a specified address. It's up to you to decide what to do from there. In case you care, the Cray 1 was pretty much the same way--no direct, hardware support for a stack. On the Cray people still often handled things about like a normal stack, but on the IBMs, they didn't (at least in the compilers I've seen). – Monomolecular

Google GO language runtime is also doing it to avoid the 1MB stack allocation, they use 4K "heap" chunks. – Firewarden

@JerryCoffin agreed. Your answer mirrors my answer. On that IBM platform, they implemented a stack by using a special collection in the heap part of the memory. It's still a stack though. – Bolshevist

looks similar to MIPS. In MIPS the call instruction is simply jal (jump and link). There's no stack pointer either, you just use any registers to point to a memory region and call it stack. Push/pop operations will be handled manually – Nuggar

Answer 2

C++ standard does not mention anything about the stack or the heap

It actually does -- just not in those words, and without specifying how the stacks & heaps are implemented.

In C++03 there are three kinds of variables:

1. Those with static storage duration (3.7.1). These are "in-scope" for the duration of the program.
2. Those with automatic storage duration (3.7.2). These are in scope only in the context in which they are declared. Once they fall out of scope, the variable is destroyed & deallocated.
3. Those with dynamic storage duration (3.7.3). These are created with a new expression, and are destroyed with a delete. the objects themselves are scopeless, in the sense that their lifetime is not bound to the context in which they were newed. Immediate Pointers to these object are, of course, scoped. The pointers are of automatic or, rarely (and usually wrongly) static storage duration.

"Stack" and "Heap" are really just where later second two types of objects live. They are platform-dependant implementation details which realize language requirements.

So, technically you're right. The Standard doesn't say anything about heaps & stacks. But it does say quite a bit about different flavors of storage duration which requires some kind of implementation on a real platform. On most modern PC-type hardware, this is implemented as heaps & stacks. Could the different types of storage duration be implemented on a platform without using heaps or stacks? Anything is possible -- I suppose that it could. But whatever that implementation ended up being, it would probably have characteristics similar to at least one of the two.

In addition to all this, there is the consideration that both automatic and dynamic storage duration are required by the Standard. Any language implementation that didn't meet both of these requirements wouldn't be C++. It might be close, but it wouldn't really be C++.

Canea

"It actually does" followed by several paragraphs about how it doesn't. – Glindaglinka

@LightnessRacesinOrbit that's what John Dibling meant by clarifying with "not in those words, and without specifying how the stacks & heaps are implemented". Stack and heap are abstract concepts, and the ESP register and the malloc function are not important here. – Bolshevist

Answer 3

For small programming environments, for example the arduino platform which was based on an 8K Atmel microprocessor (now it has 32K or more), a heap is not implemented and there is no new operator defined by the library. All objects are created statically or on the stack. You lose the advantages of the standard library, but gain being able to use an object-oriented language to program a very small platform - for example,creating classes to represent pins configured as particular output modes or serial ports, create an object of that class giving it the pin number and then calling functions on that object rather than having to pass the pin number around to your routines.

If you use new on an arduino, your program compiles but does not link - the compiler is g++ targeting the avr instruction set, so is a true C++ compiler. If you chose to provide your own implementation, you could do so, but the cost of providing an implementation on so small a footprint is not worth the gain in most cases.

Vestige

Pedantry: If there is no new operator, it's not C++. – Canea

@JohnDibling lots of g++ users would consider g++ a C++ compiler. – Vestige

@nikhil yes, g++-avr is what arduino uses. John was arguing the language wasn't C++ because the avr libraries don't include new. – Vestige

(operator new was added to arduino in release 1.0, so this example is now obsolete) – Vestige

The compiler SYSTEM would not be C++ – Firewarden

Agree, that pre-1.0 language without new is not C++, so doesn't qualify as an answer. – Bolshevist

@JohnDibling new is keyword rather than operator – Tamberg

@陳力 The library was missing the implementation of the replaceable allocation functions named 'operator new ', numbers (1) and (2) listed at en.cppreference.com/w/cpp/memory/new/operator_new . The parser wasn't missing the 'new' keyword. – Vestige

Answer 4

Yes there are, mainly MCUs like Freescale and PIC

2. Stackless processors are being used now.

We don't look at cores the way assembly programmers do. We're happy with bare-bones programmer's models, so long as the required fundamentals are present. A stack is not one of them: we've run into several stackless cores recently, and have had no problems developing C compilers for them.

The eTPU is a 24-bit enhanced time processing unit, used in automotive and general aviation engine control, and process control. eTPU may be a co-processor, but it has a complete instruction set and a full CPU core, and it's stackless. It is a mid-volume processor: chances are you'll drive or fly home tonight courtesy of C on a stackless processor.

We have a C compiler for the eTPU based on C99 and ISO/IEC 18037. We run standard C test suites on this processor.

The Freescale RS08 is a more traditional MCU that is stackless. In the process of "reducing" the HC08/HCS08 core, Freescale removed the CPU stack. We consulted on the architecture of RS08, and we never felt the need to insist on a hardware stack.

To mention another co-processor we consulted on, the Freescale XGATE has a very friendly ISA and programmer's model, but it doesn't have a stack.

Then there are the "nearly stackless". Microchip PIC never had data stacking, with only an 8-entry (or 16-entry in the enhanced 14-bit core) call-return stack. Nobody doubts that C is available for PICs.

These parts, especially the eTPU, were designed to be compiler friendly and encourage machine-generated code.

There are other non-stack-based processors, some created recently, spanning a range of applications and enjoying their own C compilers. There are mid- to high-volume stackless parts. Performance is usually the primary reason that parts do not have a stack.

http://www.bytecraft.com/Stack_controversy

Nuggar

Answer 5

I dare to say there is no such C++ implementation, but simply because the stack and heap are very useful abstractions for which basically all processors on the market provide some HW support to make them very efficient.

Since C++ aims at efficiency, C++ implementations will make use of them. Additionally, C++ program don't typically operate in a vacuum. They must integrate into the platform ecosystem, which is defined by the platform's Application Binary Interface. The ABI - for the very same reasons - defines stack and other memory structures the C++ implementation will need to obey to.

However, let's assume your C++ program is targeted to a simple, small, resource constrained embedded platform with an exotic microcontroller and no Operating System (your application will be the OS!) and no threading or processes.

To start with, the platform may not provide dynamic memory at all. You will need to work with a pool of static memory defined at link time, and develop your own memory allocation manager (new). C++ allows it, and in some environments it is indeed used.

Additionally, the CPU may be such that stack abstraction is not that useful, and therefore not worth implementing. For instance, CPUs like SPARC define a sliding register window mechanism that - combined with a large amount of registers - makes use of the stack not efficient for function calls (if you look at it, the stack is already done in HW!).

Long story short, all C++ implementation use stack, most use the heap, but the reason is strongly correlated to the platform properties.

Suspender

That hypothetical implementation of C++ on a platform without an OS and memory management and with a custom "heap" using the static memory still makes it a "heap" implementation. You're just using a very limited amount of memory for it. As far as SPARC using a different way to track call stacks using registers as opposed to RAM, that's also still a stack - just implemented differently. So no, even in your special HW scenario, C++ always uses a heap and a stack, however limited, basic or unusual the OS services and CPU registers happen to be. – Bolshevist

Answer 6

This is essentially echo'ing Mr. TA's answer (+1 BTW). Stack and heap are abstract concepts.

The new and delete operators (and malloc and free functions) are really just an interface to the abstraction called a heap. So, when you ask for a C++ implementation to be "heapless", you are really asking for the implementation to not allow you to use these interfaces. I don't think there is anything preventing an implementation from always failing these interfaces.

Calling functions and resuming the current execution after the call returns (and optionally retrieving a return value) are interfaces to a stack abstraction. When you are asking for the C++ implementation to be "stackless", you are asking for the C++ implementation to disallow the program from performing these actions. I can't think of a conforming way for the compiler to impose this condition. The language dictates the source code be allowed to define functions, and to define code to call functions.

So my answer in terms of what is possible: "stackless" no, "heapless" yes.

Pluvious

I would actually disagree with your yes answer to heapless. A C++ implementation without new/delete is no longer a C++ implementation, more like a C implementation. You can implement a part of C++, namely functions and variables, and no memory allocation; but that's not C++ anymore. Still +1 for correctly understanding the abstract concepts behind heap and stack. It seems that a lot of people are failing to grasp that concept. – Bolshevist

@Mr.TA: I was more thinking new would always throw or return NULL. – Pluvious

That's hardly a difference. Something that always fails at runtime, vs something that doesn't even compile, yields the same result: no C++ :) – Bolshevist

@Mr.TA: It's a quality of implementation issue. The programmer can override new and delete to treat a global array as a heap if they wish. – Pluvious

The way I see it is that new/delete and functions are such an important part of C++, that it can't just be discounted as "quality issue". These are indeed the defining parts of the language, not some minutia detail that can be omitted while preserving the gist of the language. The new is the gist. And it requires a heap (of some sort). – Bolshevist

@Mr.TA: Consider it from a different point of view. If the C++ library was written so that new always used mmap(), but there is no more available memory. It is not incorrect for it to return NULL or throw. But a program written to behave correctly even in the face of that can operate in a "heapless" mode. – Pluvious

Answer 7

There can't be a stack-less and heap-less implementation since C++ defines constructs such as functions and the new operator. Calling a function requires a stack, and "new"ing up an instance requires a heap. How those are implemented can be different between platforms, but the idea will be the same. There will always need to be a memory area for instance objects, and another memory area to track the execution point and call hierarchy.

Since x86 (and x64) have convenient facilities for these things (ie. the ESP register), the compiler uses that. Other platforms might be different, but the end result is logically equivalent.

Bolshevist

You could get away without the heap, as you can write code without new. You'd lose much of the standard library, of course, as that uses new. To do it, you'd either need a very large stack or be writing small programs. – Amoral

Calling a function does not require a stack. It requires someplace to store the callers context, and someplace for the function to use as space for local variables. Heaps can do that just fine in principle. – Subsidence

It would be hard to call a langauge C++ if you outlawed "new". – Subsidence

As Ira Baxter says, the call 'stack' could be heap based, which would qualify as a stackless implementation of C++ for the purposes of the question. The performance characteristics would be quite different from the traditional execution stack. – Housum

That's my point though - using the heap as a stack doesn't mean you don't need a stack; you're still using a heap and a stack. Same goes the other way. Heap is a crappy way to implement a stack, and the stack is a bad place for heap. – Bolshevist

@IraBaxter Well, you could still create classes, templates, etc. You'd probably have to write your own standard library, but considering that that didn't exist originally in C++, I don't think that's a requirement to call it C++. – Amoral

@StevenBurnap: But, if you eliminated "new" and decided not to call it C++, its social/market acceptance would go to zero. Where's the motivation to build such a thing? – Subsidence

None whatsoever. As I mentioned above, I used a heapless version of C many years ago. It really sucked. It was possible though. – Amoral

Doing what you suggested (eliminating "new" or using the heap to make calls) means it's not C++ anymore. Secondly, as I stated earlier, eliminating "new" means everything will live on the stack, which means you're using the stack to implement a "heap". (and vice-versa) It's important to understand the difference between the need for a execution/call tracking and instance objects storage, and stack and heap, respectively: the latter are the implementations of the former. – Bolshevist

Again, you can write code that never uses the heap for object storage. It requires developing using a more functional design philosophy. (Objects are always either globals or scoped to method calls.) You can use basically all other C++ features, and could also rewrite a lot of library routines without using the heap. I'm not saying it is a good idea, but it is perfectly possible. – Amoral

Using the heap to make calls would not change whether you got C++ behavior not, unless you can find something in the standard that says you cannot do that. – Subsidence

My point is only that you can write significant programs in C++ without ever using new, or libraries that use new. It's surely a bad way to go, but it is possible. – Amoral

@StevenBurnap you can, but that doesn't mean you're not allocating objects. If you don't "new" them up, they'll probably live on the stack. Which means you're using the stack as a storage mechanism for objects, aka heap. You're still logically using a heap. Keep in mind that both heap and stack live in the same place which is the memory (RAM/cache/page file, w/e). "Heap" and "stack" are logical partitions of what's essentially the same pool of storage. If you elect to partition them differently, ie. using the memory pointed to by ESP register to store objects, you're still using a (bad) heap. – Bolshevist

Well, no. If you were still logically using a heap, then you could create and destroy objects regardless of scope. The stack doesn't work at all like the heap. With stack allocation, you don't search some structure to find free memory, you just change the stack pointer and hope you don't hit the end. – Amoral

Many hard realtime systems are made using only stack memory using mechanisms like "alloca". It requires more reasoning about object lifetimes and more careful and tedious design of data structures, but it is actually done in practice. – Hussite

@StevenBurnap creating objects using stack semantics only, which in C++ is achieved by declaring a variable like ClassFoo x; inside a function, will in fact allocate that on the heap. However, the question was, whether C++ as a whole can be implemented without one or the other and answer is no, because of "new" and function calls. You could implement a subset of C++, but that's not the same as implementing C++. Taking away "new" turns C++ into something that's not C++. – Bolshevist

@TimSeguine sure, but that language is no longer C++. You could use a subset of C++ to achieve what you're describing, but that wasn't the question. You can take different subsets of C++ and implement them on a variety of platforms, some very limited; say, you wanted to implement just variables and no functions - all programs are one big function. Then you don't require a stack, and you implement a part of C++. That doesn't mean you implemented C++, though. – Bolshevist

@Mr.TA No, objects are never allocated on the heap unless the new keyword is used. ClassFoo x; is always a stack allocation. (Of course, the object may contain explicit calls to new inside it.) – Amoral

@StevenBurnap exactly, "unless the new keyword is used". The new keyword is part of C++. A C++ implementation without the new keyword is not a C++ implementation. – Bolshevist

Right, but there's no requirement you use every keyword in a language. You absolutely can write C++ code without ever using the heap, and that includes creating objects in functions. – Amoral

Oh yes, there very much is such a requirement. The question was "can you implement C++", not "can you implement some part of C++". As a programmer, you can choose to use or not use certain language features, but as a platform implementer, you have to support all of them - or you can't declare that you support the language. – Bolshevist

@Mr.TA An implementation could implement new using stack memory if they wanted. It would be a bad way to implement new, because it makes delete retarded, but I can't find any reason why it would be invalid according to the standard. – Hussite

@TimSeguine perhaps, but as you said, delete wouldn't work like you would expect it to. You're talking about some serious memory leaks here, as depending on where you are in the call stack, huge objects can just sit there without being disposed of. Again, I don't think this is C++ anymore, really. It's closer than not having new/delete at all, but not quite there. – Bolshevist

@Mr.TA If you define "C++" as what the ISO standard says C++ is, then it is indeed C++. Keep in mind that what the standard refers to as freestanding implementations have a lot more freedom in how they do certain things. – Hussite

@TimSeguine the standard cannot force (legally or contractually) people to implement anything. Obviously some platforms have limitations that only allow for parts of the language to be implemented and they do that - as they should. The question was, "can you have C++ without heap or stack" - not "can you have a part of C++ somehow jerryrigged to kind of work". – Bolshevist

@Mr.TA I didn't imply any of that. I only said you can implement an ISO compliant C++ implementation without a heap. If that doesn't fit your personal definition of C++, then that is your problem. The ISO committee doesn't include a provision for "what Mr. TA thinks a proper implementation of C++ should include". Quote me in the standard where it says I need a heap. – Hussite

PIC10, 12, 14 and 16 MCUs have hardware callstack and you can't manipulate it from code, so its compiler may not need to deal with stack. Lowprofile PICs have only 2 levels of stack so there are many tricks to overcome that and avoid the use of callstack, like a statemachine – Nuggar

@TimSeguine does the ISO C++ standard have new and delete operators? If so, how do you implement those without a heap? Similarly, how do you implement function calls, another C++ feature, without a stack? If you don't have heap, you can't have new/delete, or at best, you have a horrible ducttape workaround that should never see the light of day. Same for stack; I suppose it's easier to store the stack in a heap than the other way around, but it's still less efficient and is prone to errors. There are implicit requirements; speed and stability are some of them, and can't be ignored. – Bolshevist

@LưuVĩnhPhúc I'm unfamiliar with those platforms, however accessing the stack directly from C++ is not a language feature. Calling functions, however, is. When I say C++ needs a stack, I don't mean there is a keyword called "stack" which lets you manipulate the stack as you please. Rather, function calls by definition rely on a stack, and the hardware stack you mentioned will suffice. – Bolshevist

@Mr.TA The primary advantage of stack memory is cache locality. Allocating a stack on the heap doesn't change that. As for the other thing: as far as I know the standard doesn't guarantee much about what "releasing memory" actually means. In particular, as long as delete maintains the destruction guarantees, I believe it is allowed to leak memory willy nilly. If we define C++ as what the ISO standard defines, then we can probably come up with many compliant implementations nobody would want to use. That was my point. – Hussite

@TimSeguine I would disagree. An implementation of a language, which suffers from catastrophic flaws, like memory leaks, that are part of the design of the implementation, cannot be considered to be an implementation at all. As far as ISO goes, it's entirely possible that people who wrote it didn't even entertain the idea that somebody might construe the lack of explicit rules against memory leaks (among other issues), as carte blanche to not properly release memory. Again, maybe you can have a duct tape version of C++, but not a real version of C++, without heap and stack. – Bolshevist

@Mr.TA You can implement a stack in a heap and a heap as a stack without memory leaks also. The standard just doesn't guarantee the presence or absence of any of those three things. I know of at least one gcc based production compiler(not publicly available) that doesn't have a heap. Heapless C++ systems are actually very common. They either don't implement a free store(because they don't want one) or do so by reserving stack space before main. In either case there is no heap. You probably haven't seen one because the compilers are often proprietary or unpublished open source modifications. – Hussite

@Mr.TA: Consider that void* ::operator new(size_t) { throw std::bad_alloc(); } is conforming and heapless. The C++ Standard allows dynamic allocation to fail. On a heapless system, it always fails (more usefully with a link error as with avr-gcc, more comformantly with bad_alloc()) – Carmagnole

@Mr.TA: Would you also like to argue that since the C++ Standard defines fstream that there are no C++ implementations without a filesystem? But the Standard does not say what filenames are required to be valid, or under what conditions fstream.open() must succeed. – Carmagnole

@BenVoigt I understand what you mean - there are platforms with limitations on which a subset of C++ can be compiled. That's fine. My original point still stands - the full C++ language with new operator working as expected needs a stack and a heap. Regarding fstream, this is one step removed from memory aspect - now we're talking about IO; obviously not all programs need IO and tons of platforms don't have IO. Furthermore, fstream is a class; new is an operator. There is a huge difference there. – Bolshevist

@Mr.TA: fstream is a class, ::operator new() is a function. avr-g++ is not missing the new operator or support for new expressions, it is missing the allocation function which makes them succeed. But they are not required to succeed any more than file I/O is. BTW every platform needs I/O, it's the most important thing for embedded platforms. But not file I/O. – Carmagnole

@BenVoigt so a person whose car doesn't have wheels has a mode of transportation, but it is missing the parts which make the transportation succeed? Got it. – Bolshevist

@Mr.TA: I would say they have a vehicle. I would not say that vehicle is a mode of transportation. Similarly, a C++ platform where heap allocation fails is a C++ platform, but not one supporting objects with dynamic lifetime. And a C++ platform with control over general-purpose I/O pins is a platform with I/O, but not a platform with a filesystem. "I/O" is not synonymous with std::fstream. – Carmagnole

@BenVoigt new operator and heap allocation are so central to C++ that without them, one can't really call what's left "C++". You can call it a subset of C++, but not C++. A car without wheels is a part of a car; it's not really a car in any useful sense. If anything, it's a giant paper weight. And you seem to be hung up on my choice of words. Yes I meant "file IO" not just any "IO". That doesn't change my point. File IO is not integral to C++. Allocating objects in memory is. – Bolshevist

@Mr.TA: The C++ committee apparently didn't feel that any minimum number of successful dynamic allocations was necessary to "be C++" the way that they did for say the number of atexit handlers. So an environment which can allocate only zero objects with dynamic lifetime is still conformant C++. – Carmagnole

@BenVoigt oh I don't doubt that the C++ committee makes decisions from time to and time, and since it's staffed with angels and gods it never makes any mistakes whatsoever. Besides that, their definition of "conformant" does not necessarily mean "meaningfully complete". They may pursue goals WRT market share and whatnot where advertising C++ as a viable option for these special situations is worthwhile. These are words and semantics, though. The cold fact is, a language whose chief improvement over its predecessor - C - was OOP, is not complete without new. – Bolshevist

@BenVoigt I suppose you could allocate objects on the stack as locals, then pass those as references down the call tree and as values up the call tree. However you have to agree this is very error prone and inefficient, and will not work in some scenarios where there is no direct call tree relationship. For ex., if you have threads, sharing objects becomes extremely tricky. This is firmly in the territory of "doing things the wrong way ONLY because there are firm limitations"; it's on the spectrum of "is this C++" somewhere in the middle, maybe a bit closer to yes than no, but not "yes". – Bolshevist