We’re rewarding the question askers & reputations are being recalculated! Read more.

Hot answers tagged

75

This is called "inlining" and many compilers do this as an optimization strategy in cases where it makes sense. In your particular example, this optimization would save both space and execution time. But if the function was called in multiple places in the program (not uncommon!), it would increase code size, so the strategy becomes more dubious. (And of ...


47

According to legend, the original stack received its name by analogy to the stacks of dishes in the university cafeteria: you put one on top, and the (spring-loaded) stack of dishes goes down a bit, you take one away and it pops up a bit. Therefore 'pushing' received a connotation of operating downwards, even though you don't actually push down on the plate -...


45

Well, you can certainly implement a stack with an array. The difference is in access. In an array, you have a list of elements and you can access any of them at any time. (Think of a bunch of wooden blocks all laid out in a row.) But in a stack, there's no random-access operation; there are only Push, Peek and Pop, all of which deal exclusively with the ...


44

Think about a Pez dispenser. That's your mental model for a stack - last in, first out. So adding an item to a stack requires you to push down the existing items to make room.


36

Those data structures typically have properties the OS stack has not: Linked lists don't require contiguous address space. So they can add a piece of memory from wherever they want when they grow. Even collections that need contiguous storage, like C++'s vector, have an advantage over OS stacks: They can declare all pointers/iterators invalid whenever they ...


26

In practice, it's difficult (and sometimes impossible) to grow the stack. To understand why requires some understanding of virtual memory. In Ye Olde Days of single-threaded applications and contiguous memory, three were three components of a process address space: the code, the heap, and the stack. How those three were laid out depended on the OS, but ...


24

The problem with stacks is that you can't "free" memory unless it is on top of the stack. For instance, say you allocated 3 things of varying sizes: a = allocate(2000000); // 2000000 bytes b = allocate(1); c = allocate(5000000); The stack would have a on the bottom, b in the middle, and c on top. This becomes problematic if we want to free b: free(b); // ...


23

There are two different memory limits. The virtual memory limit and the physical memory limit. Virtual Memory The virtual memory is limited by size and layout of address space available. Usually at the very beginning is the executable code and static data and past that grows the heap, while at the end is area reserved by kernel, before it the shared ...


23

What purpose does this stack actually serve, as opposed to explaining its structure? You have many answers which accurately describe the structure of the data stored on the stack, which I note is the opposite of the question you asked. The purpose that the stack serves is: the stack is part of the reification of continuation in a language without ...


21

I believe it comes from the very early days of computing, when memory was very limited, and it was not wise to pre-allocate a large chunk of memory for exclusive use by the stack. So, by allocating heap memory from address zero upwards, and stack memory from the end of the memory downwards, you could have both the heap and the stack share the same area of ...


20

It is strongly operating system specific (& computer specific) and on some OSes you have some ways to configure (and even increase) the limit. It is even compiler specific (or your-programming-language-implementation specific), since some compilers (including recent GCC for some limited kind of C code) are able to optimize some tail calls. (some ...


19

There is no advantage. You have correctly realized that using Queues to implement a Stack leads to horrible time complexity. No (competent) programmer would ever do something like this in “real life”. But it's possible. You can use one abstraction to implement another, and vice versa. A Stack can be implemented in terms of two Queues, and likewise you could ...


17

It depends on your operating system. On Windows, the typical maximum size for a stack is 1MB, whereas it is 8MB on a typical modern Linux, although those values are adjustable in various ways. If the sum of your stack variables (including low-level overhead such as return addresses, stack-based arguments, return value placeholders and alignment bytes) in the ...


16

Consider this, let's say we got rid of all loops in Java (the compiler writers are on strike or something). Now we want to write factorial, so we might right something like this int factorial(int i){ return factorial(i, 1);} int factorial(int i, int accum){ if(i == 0) return accum; return factorial(i-1, accum * i); } Now we're feeling pretty clever, we'...


16

The red zone is, purely and simply, an optimization that can save instructions. It means that it's no longer necessary for the emitted code for every function to subtract from the stack pointer to make local storage like so sub XXX, %rsp at the beginning of every function call, even if they are not leaf functions. Often times the code emitted from the ...


16

Allocating a variable on the stack and deallocating it is a simple addition and subtraction of the stack pointer. Given that it happens anyway when entering a function means that local variables are so cheap that trying to optimize them to anything else will generally incur more cost. Putting it in the data segment will incur a cache cost, the stack will ...


16

Stacks allow us to elegantly bypass the limits imposed by the finite number of registers. Imagine having exactly 26 globals "registers a-z" (or even having only the 7 byte-sized registers of the 8080 chip) And every function you write in this app shares this flat list. A naive start would be to allocate the first few registers to the first function, and ...


14

Is it a hybrid type of thing? (e.g., does my .NET program use a stack until it hits an async call then switches over to some other structure until completed, at which point the stack is unwound back to a state where it can be sure of the next items, etc?) Basically yes. Suppose we have async void MyButton_OnClick() { await Foo(); Bar(); } async Task Foo() ...


13

It's possible to write an operating system that doesn't require stacks to be contiguous in address space. Basically you need some extra messing about in the calling convention, to ensure that: if there isn't enough space in the current stack extent for the function you're calling, then you create a new stack extent and move the stack pointer to point to the ...


12

Who said the compiler will reserve any space (could be register only). This is completely undefined. All that you can say is that it (x) can only be accessed from inside the inner block. How the compiler allocates memory (on a stack if it even exists) is completely upto the compiler (as the memory region may be re-used for multiple objects (if the compiler ...


12

You know when you break to the debugger for whatever reason, and the IDE gives you a stack trace? And each method (stack frame) has its own set of local variables that you can examine in the debugger? That's the "execution stack" of your program. It shows what the local state of your program looks like at the moment. What the author is saying is that ...


12

You don't implement amortized analysis. It's a technique to get more accurate O bounds. The essential observation you have to make is, that expensive operations cannot happen at any time. In the case of an array-backed data structure, the array needs resizing every now and then – when it's full. This is the most expensive operation and takes O(n) ...


12

The CLR standard does not require a stack or a heap, so lets get that out of the way first. But C# implemented on paper isn't very useful. I describe here the implementations we can run code with "in practice", like the Microsoft C# or Mono C#. Regardless, the method and local variables have a conceptual relationship with classes and object instances that ...


12

Since most implementations take the heap and the stack from the same block of memory (growing from either end) it doesn't matter. Size is not a reason to prefer the heap over the stack. The lifetime of your object is. Should it die once it goes out of scope or not? If not, when?


11

Typically, the stack is a memory region. It is possible to add data to the stack ("push"), or to retrieve it and take it out of the stack ("pop"). The last data added to the stack is the first to be retrieved. PUSH 1 PUSH 2 PUSH 3 POP -> Result 3 PUSH 4 POP -> Result 4 POP -> Result 2 POP -> Result 1 The processor pushes bits through ...


11

This depends on the calling convention being used. Whoever defines the calling convention can make this decision however they want. In the most common calling convention on x86, registers aren't used for passing parameters; the parameters are pushed on to the stack starting with the rightmost parameter. The return value is placed in eax and can use edx if ...


Only top voted, non community-wiki answers of a minimum length are eligible