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 ...


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 ...


29

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 ...


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 ...


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 ...


20

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 ...


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

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

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

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 ...


15

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() ...


14

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) ...


13

The only valid answer is vague: "too much is when the stack overflows." Unless you are in complete control over the implementation of every line of code between the program's entry point and the function in question, you can make no assumptions about how much stack is available. You cannot, for example, guarantee that calling this function will never cause ...


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

In addition to what Dirk said, an important use of stack frames is to save previous values of registers so that they can be restored after a function call. So, even on processors where registers are used for passing parameters, returning a value, and saving the return address, the values of those registers are saved on the stack before a function call so ...


12

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 ...


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

Cases which that approach cannot handle: function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; } function many(a) { for(i = 1 to a) { b(i); };} There are languages and platforms with limited or no call stacks. PIC microprocessors have a hardware stack limited to between 2 and 32 entries. This creates design constraints. COBOL bans ...


10

I just hacked up a little program that generates a set of random numbers restarting at the same seed each time, to ensure that it's "fair" and "comparable". As it goes along, it figures out the min and max of these values. And when it has generated the set of numbers, it counts how many are above the average of min and max. For VERY small arrays, it shows ...


10

Both pre- and postfix have basically the same advantages over infix notation. The most important of these are: much easier to translate to a format that is suitable for direct execution. Either format can trivially be turned into a tree for further processing, and postfix can be directly translated to code if you use a stack-based processor or virtual ...


10

Well, you are right, this is all very confusing. First of all, the frame pointer is not even necessary. Everything is addressable using only the stack pointer. The main reason for the existence of the frame pointer is that the value of the stack pointer may change during the execution of the function, (namely, as you are pushing into the stack ...


9

I think it's easier to answer this by the order of how the memory is used. Question 3: What about the text (code) and data sections, how are they limited? Text and Data are prepared by the compiler. The requirement for the compiler is to make sure that they are accessible and pack them in the lower portion of address space. The accessible address space will ...


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