有多少个叫做堆栈的东西? [英] How many things called stack are there?
问题描述
有多少种不同的东西叫做堆栈"，它们如何相互联系?而且，如果有人说堆栈"，我是否可以合理地假设它们是其中之一，或者我只能从上下文中找出来?
但是首先，我想概述一下我目前的理解.
在编程中似乎有很多含糊不清的东西，都被称为堆栈"，堆栈"或类似的东西.除了数据结构之外，我什至不确定该术语是指同一事物还是不同事物.
基于此页面，看来堆栈"甚至不是堆栈数据结构.尽管您只将东西放在上面，但是您可以访问堆栈中的任何元素，而无需弹出所有元素.除非我完全误解了数据结构.在我读到这篇文章之前，使用堆栈作为变量的数据结构的想法似乎是一个非常糟糕的决定.
然后是堆栈"，调用堆栈和硬件堆栈的问题.我认为硬件堆栈是调用堆栈，因为您可以在其中放入指令(?)，但是它也可能不是存储固定大小变量的位置.还是吗?为什么甚至必须在硬件中实现堆栈?我认为变量存储在RAM中，而不是处理器的内存中.还是调用堆栈语言是特定的，因此不是硬件?
然后是堆栈框架，这似乎对所有堆栈来说都是通用的，除了数据结构之外.
我不知道如何正确搜索此内容，因为我不确定人们是否在谈论同一件事.我越了解，就会越困惑
TL; DR
当我们允许程序调用子例程时，我们需要跟踪调用堆栈(如下所述).这可以通过多种方式来实现，而这种方式仅受您的创造力的限制，但是最简单，最快的方式是每次我们推入/弹出某物时指针都会增加或减少.由于这很容易实现和使用，因此CPU可以提供删除样板代码的指令和寄存器(并可以对其进行优化).那就是硬件堆栈.
需要堆栈结构
堆栈是支持 LIFO 范例的任何结构.
CPU根本不需要为堆栈提供支持(例如MIPS不会这样做)，但是无论如何您最终都会使用它.
要了解原因，只需考虑调用子例程的行为.
在调用子例程时，我们需要记住其返回地址.
即使CPU将地址存储在寄存器中，例如 $ ra ，问题仍然在于被调用方可能需要自己调用另一个子例程！
因此，我们需要先保存 $ ra ，然后进行新的调用.
同样，这个新的被叫方可能需要打另一个电话，问题可能会重复无限次.
考虑一下，您将意识到:
- 我们需要记住每个寄信人地址及其顺序.
- 返回时，我们将从最后一个到第一个使用这些地址.
这是 LIFO 行为，我们需要一个堆栈，因此命名为调用堆栈.
实现调用堆栈
实际上如何实现堆栈是由体系结构定义的，如果CPU是通用的，则不太可能使用某种形式的内部不可访问的内存.我们已经可以访问RAM，为什么不使用它呢?这样，我们对递归的深度没有任何内部限制.
组装时，一切都由其用途组成.
我们不需要复杂的元数据来实现堆栈，只需一个简单的指针.
程序员要确保它不会弹出的时间超过它所推送的时间，或者要确保新推送的元素不会覆盖某些内容.
大多数汇编程序员最终都会使用寄存器来跟踪堆栈的头部.
由于这是一种普遍实施的技术，因此CISC CPU具有专用的寄存器和用于管理堆栈的指令.
- 您可以使用隐式堆栈指针将操作数压入/弹出堆栈.
- 调用将使用隐式堆栈指针将返回地址压入堆栈.
- 返回将使用隐式堆栈指针在堆栈上弹出返回地址(并跳转到该地址).
如果要使用该名称，则为硬件堆栈.
您不是很自由地选择一个实现，因为您的程序通常不是在裸机上单独运行的，所以您需要坚持使用ABI来指示如何实现堆栈
不是那么堆
汇编编程就像量子物理学，是程序员(观察者)决定事物的本质.
由于程序可以自由访问其RAM，因此可以在不使用专用指令的情况下重新实现上述所有堆栈操作. 如果程序员可以访问堆栈指针(应该可以，或者我们将无法首先设置堆栈)，我们可以将其用作基本指针，并欺骗访问不位于顶部的元素的堆栈结构.
这是普通的汇编程序.一切都是通过使用来定义的，而不是通过固定规则来定义的.
注意，我们不能删除元素不在最上面，因为唯一定义堆栈的是它的头指针，所以堆栈的每个属性都由该指针定义.
包括它的大小.
堆栈的其他用途
一个统一的约定是使用堆栈来存储子例程参数(如果我们已经填充了所有寄存器)和局部变量.
这是由于堆栈的一个非常有趣的属性所致:在堆栈上分配/释放内存非常容易.
只需前后移动指针即可.
假设堆栈指针指向了一些足够大的内存区域，可用于一般用途，您可以将其视为已分配的大块内存，并且堆栈指针后面的所有内容都在使用中(前面的所有内容都可能突然被覆盖).
如果重新考虑调用堆栈，您会发现这是做事的自然方法.
调用新的子例程时，通过更改堆栈指针来分配堆栈上的新空间，返回时释放该空间，以恢复堆栈指针.
调用者始终将其数据相对于堆栈指针放在相同的相对位置.
每个例程也可以在堆栈的最后看到其数据(和参数)，而与之前已执行的调用次数无关.
How many different things called "stack" are there, and how do they relate to one another? And if someone says "the stack" can I reasonably assume they mean one of these, or can I only figure it out from context?
But first, I would just like to give an overview of what my understanding is at this point.
There seems to be an awful lot of vaguely related things in programming that are all called "a stack", "the stack", or something of the sort. Aside from the data-structure, I am not even sure if the term refers to the same thing or different things.
Based on this page it seems like "the stack" is not even a stack data-structure. While you do only put things on top of it, you can access any element from the stack without having to pop off all the elements before it. Unless I am completely misunderstanding the data-structure. Before I read this, the idea of using a stack as a data-structure for variables seemed like a really bad decision.
Then there's the issue with "the stack", a call stack, and the hardware stack. I figure that the hardware stack is the call stack, because you can put instructions in it (?), but it couldn't possibly also be the place you store your fixed-size variables. Or is it? Why does a stack even have to be implemented in the hardware? I thought variables were stored in RAM and not the processor's memory. Or is the call stack language specific, and thus not hardware?
Then there's the stack frame, which seems to be a general thing for all stacks, except for the data-structure.
I can't figure out how to google this properly, because I am never sure if people are talking about the same thing. The more I try to understand, the more I get confused
TL;DR
When we allow programs to call subroutines, we need to keep track of the call stack (as explained below). This can be implemented in a variety of ways limited only by your creativity, but the simplest and fastest ways is a pointer that get incremented or decremented each time we push/pop something. Since this is so easy to implement and so used, a CPU can provide instructions and registers that remove boilerplate code (and can be optimized). That is the hardware stack.
The need for a stack structure
A stack is any structure that support the LIFO paradigm.
There is no intrinsic need for the CPU to provide support for a stack (MIPS don't do that for example), but you will anyway end up using it.
To understand why, simply consider the mere act of calling a subroutine.
When calling a subroutine, we need to remember its return address.
Even if the CPU stores the address in a register, say $ra, the problem is that the callee may need to call another subroutine itself!
So we need to first save $ra and then make the new call.
Again this new callee may need to make another call, and the problem repeat, potentially infinite times.
If you think about it, you will realize that:
- We need to remember every return address and their order.
- On return we will consume these addresses from the last one to the first.
This is LIFO behavior, we need a stack, hence the name call stack.
Implementing the call stack
How the stack is actually implemented is architecture defined, if the CPU is general purpose it is unlikely that some form of internal, non accessible, memory is used. We already have access to the RAM, so why not using it? This way we impose no internal limit on the depth of the recursion.
In assembly everything is made up by its use.
We don't need complex meta data to implement a stack, just a simple pointer.
It's up to the programmer make sure it will never pop a time more than it pushed or to make sure the new pushed element won't overwrite something.
Most assembly programmers ends up using a register for keeping track of the head of the stack.
Since this is a universally implemented technique, CISC CPUs have dedicated registers and instruction for managing the stack.
- You can push/pop an operand on the stack, using the implicit stack pointer.
- A call will push the return address on the stack, using the implicit stack pointer.
- A return will pop the return address (and jump to it) on the stack, using the implicit stack pointer.
This is the hardware stack if you want to use that name.
You are not so free to pick up an implementation, since your program isn't usually running on its own on bare metal, you need to stick to the ABI with dictate how the stack is implemented.
Not so stack
Assembly programming is like quantum physic, it is the programmer (observer) that dictate the nature of the things.
Since a program can freely access its RAM, all the above stack operations can be reimplemented without using the dedicated instructions.
If the stack pointer is accessible to the programmer (and it should be or we won't be able to set the stack up in the first place) we can use it as a base pointer and cheat on the stack structure accessing elements not on top.
This is ordinary assembly programming. Everything is defined by use, not by fixed rules.
Note that we cannot remove element not on top, since the only thing that define the stack is its head pointer, every property of the stack is defined by that pointer.
Including its size.
Other uses of the stack
A consolidated convention is to use the stack to also store subroutines parameters (if we already have filled all the registers) and local variables.
This is due to a very interesting property of the stack: it is very easy to allocate/free memory on the stack.
Just move the pointer back and forth.
It is assumed that the stack pointer points to some memory area large enough for common purpose, you can think of it as an already allocated chunk of memory and that everything behind of the stack pointer is in use (while everything ahead can be suddenly be overwritten).
If you rethink about the call stack you'll find out that this is the natural way of doing the things.
When a new subroutine is called, new space on the stack is allocated by altering the stack pointer, when it return, that space is freed, restoring the stack pointer.
The caller will always have its data at the same relative location with respect of the stack pointer.
Also each routine see its data (and parameters) at the very end of the stack, independently on how many calls have been done before.
这篇关于有多少个叫做堆栈的东西?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
