heap and stack 堆和栈在内存管理和数据结构中的差异

  1. 数据结构中的栈（Stack）和堆（heap）和内存分配中的堆和栈没有直接的关联，只是因为名称相同而容易混淆。
  2. 内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。

内存管理中的堆栈

  1. Stacks in computing architectures are regions of memory where data is added or removed in a last-in-first-out manne
  2. Heap is a common name for the pool of memory from which dynamically allocated memory is allocated

内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据，动态数据区又分为栈区和堆区。我们可以称其为内存四区。

一个可执行程序在存储（没有调入内存）时分为代码段、数据区和未初始化数据区三部分，可执行程序（调入内存后）在运行时又多出两个区域：栈区和堆区。

内存四区：代码区、全局区、栈区、堆区

程序执行前，生成代码区、全局区；程序执行后，生成栈区、堆区。

  1. 代码区：存放CPU的机器指令（即代码的二进制形式）。具有两个特性：共享性和只读性
  2. 全局区：全局区的数据在程序结束后才释放。存放了全局变量、静态变量、字符串常量、全局常量
  3. 栈区：由编译器自动分配和释放。存放了函数的参数值、局部变量（函数体内的变量）等
  4. 堆区：由程序员分配和释放，若程序员未释放，程序结束时（也就是把exe关掉以后）由操作系统自动回收。
  • 栈区的数据由编译器管理，调用完之后就自动释放，压栈，出栈。先进后出的原则，栈的内存地址生长方向与堆相反，由高到底（从内存高地址向低地址存储），栈中存储的数据的生命周期随着函数的执行完成而结束。栈区是有大小的，一般是1M左右，所以别定义太大的数组。
  • 堆区中的生长方向由低到高（从内存低地址向高地址存储），并不一定按照申请顺序分配地址空间的高低。

为什么会出现两种形式？

堆栈从本质上讲是提供程序运行所需要的内存空间

因为程序不仅仅是由数据构成，还包括处理数据的逻辑方法。而这些方法的编码和执行顺序是非常符合后出先进的设计逻辑。
因此栈的存在更多是为程序的方法服务，所以我们经常说的调用栈就是指可以查看程序调用顺序的内存空间，在栈顶部的就是最后执行的方法。
方法中的临时变量如下图所示，也会存在栈中。理论上这些变量全部在堆(Heap)中生成也是可行的。
Stack由高地址向低地址索取空间，Heap则相反从低向高。但是也有很别处是Stack自上而下，Heap相反。所以是不是写错了？到底哪种才是正确的分配方案。
其实根据系统架构的不同，这两种方式都是存在的。只是顺序的颠倒?️，没有其它不同。

为什么会放在一起?

上古时期，内存有限的情况下，Heap和Stack能共享一段连续空间，根据自身情况，在保证安全的情况下，向对方霸占一些领地。从而更好的利用内存。 在现今的操作系统和硬件上，就很少出现这么紧俏的情况，而且Stack和Heap也不会在连续的物理内存中。Heap和Stack连续的情况更多是出现在以虚拟内存中，来表示程序的结构。

栈为什么不大？

  • ulimit -s查看，可能只有几M的大小。相较8GB的内存，为何栈大小只有区区几MB。
  • 其中的一种说法是，栈的调用，也就是程序执行的速度，不仅仅依赖于CPU，也同样依赖内存的读取速度。
  • 所以栈的存储会依赖于大小有限的高速缓存，如果栈过大，则高速缓存会出现大量内存空间的交换，反而降低了执行的速度。
  • 而珍贵有限的栈空间，就应该尽量避免存储容量大或者声明周期长的数据。
  • 所以堆(Heap)就有它存在的场景了，内存空间大，数据存在时间长 （依赖于不同的内存释放策略），通过地址引用，也相对松散。

程序通常牵涉三个可能的内存管理器的操作

  1. 让内存管理器分配一个某个大小的内存块
  2. 让内存管理器释放一个之前分配的内存块
  3. 让内存管理器进行垃圾收集操作，寻找不再使用的内存块并予以释放

C++ 通常会做上面的操作 1 和 2。Java 会做上面的操作 1 和 3。而 Python 会做上面的操作 1、2、3。这是语言的特性和实现方式决定的。

堆和栈的主要区别

  1. 管理方式：对于栈来讲，是由编译器自动管理，无需我们手工控制；对于堆来说，释放工作由程序员控制，容易产生memory leak。
  2. 空间大小：一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲，一般都是有一定的空间大小的。当然，我们可以修改
  3. 碎片问题：对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出
  4. 生长方向：对于堆来讲，生长方向是向上的，也就是向着内存地址增加的方向；对于栈来讲，它的生长方向是向下的，是向着内存地址减小的方向增长。
  5. 分配方式：堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。
  6. 分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。
　　堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；
　　由于没有专门的系统支持，效率很低；
　　由于可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。
　　所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，EBP和局部变量都采用栈的方式存放。
　　所以，我们推荐大家尽量用栈，而不是用堆。

为什么栈地址从高到低生长，堆从低到高?

这个问题与虚拟地址空间的分配规则有关，每一个可执行C程序，从低地址到高地址依次是：text，data，bss，堆，栈，环境参数变量；
其中堆和栈之间有很大的地址空间空闲着，在需要分配空间的时候，堆向上涨，栈往下涨。

如此设计可以使得堆和栈能够充分利用空闲的地址空间。如果栈向上涨的话，我们就必须得指定栈和堆的一个严格分界线，但这个分界线怎么确定呢？平均分？但是有的程序使用的堆空间比较多，而有的程序使用的栈空间比较多。所以就可能出现这种情况：一个程序因为栈溢出而崩溃的时候，其实它还有大量闲置的堆空间呢，但是我们却无法使用这些闲置的堆空间。所以呢，最好的办法就是让堆和栈一个向上涨，一个向下涨，这样它们就可以最大程度地共用这块剩余的地址空间，达到利用率的最大化

数据结构中的堆栈

  • 栈：是一种连续存储的数据结构，特点是存储的数据先进后出。
  • 堆：堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树；看成是一棵完全二叉树结构，特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。
    1. 大顶堆：每个结点的值都大于或等于其左右孩子结点的值；对应公式：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
    2. 小顶堆：每个结点的值都小于或等于其左右孩子结点的值；对应公式：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

计算机中为什么要用二进制？

计算机使用二进制是由它的内部物理结构所决定的，由于计算机内部都是由一个个门电路所构成，当计算机工作的时候，电路通电工作，于是每个输出端就有了电压。
电压的高低通过模数转换即转换成了二进制：高电平是由1表示，低电平由0表示。
也就是说将模拟电路转换成为数字电路。这里的高电平与低电平可以人为确定，一般地，2.5伏以下即为低电平，3.2伏以上为高电平。
数据在计算机中以器件的物理状态表示，采用二进制数字系统，计算机处理所有的字符或符号也要用二进制编码来表示。

发表回复