这是一个创建于 1336 天前的主题，其中的信息可能已经有所发展或是发生改变。
如题，做了一个 C 语言小实验，我分别进行了两个操作，
其一是在堆上申请一个长度为一亿的向量，用来储存 double 类型的数据（包含初始化，全部为 0 ）
其二是在一个一万次的循环里重复创建长度为一万的数组，类型同样为 double，同样初始化为 0
理论上两者都涉及到 cpu 在内存上填入一亿个 0，但后者的速度比前者要快 30 多倍。这让我想到一个问题，就是传统都认为堆比较慢，而慢产生的原因是什么，堆和栈都是普通内存，理论上应并无硬件层面的区别。难道程序申请堆内存都必须要经过操作系统才导致速度变慢吗？但是感觉又跟传统经验不符，毕竟经过操作系统是一个非常昂贵的操作，总不可能程序内部所有动态特性都要经过操作系统吧。
不过不经过操作系统的话，又为什么会慢这么多呢？
 |
1
BrettD 2021-03-30 14:16:05 +08:00 via iPhone
申请堆内存走 malloc 啊
|
 |
2
Glauben 2021-03-30 14:43:31 +08:00
印象中是缓存位置不同，栈是一级缓存，堆是二级缓存，两者速度天差地别
|
 |
3
12101111 2021-03-30 14:53:08 +08:00
可以看一下 malloc 都干了什么 https://github.com/microsoft/mimalloc
|
 |
4
lsylsy2 2021-03-30 14:55:55 +08:00
其二是在一个一万次的循环里重复创建长度为一万的数组，类型同样为 double，同样初始化为 0
确认是一万个独立的数组吗？听起来有可能循环每次结束，数组都被释放了，所以你实际是反复写了同一个数组一万次。那么缓存等等差距就很显然了。 |
 |
5
Justin13 2021-03-30 14:59:29 +08:00 via Android  1
好像栈的开辟是无脑的，不用寻址，地址直接偏移就好，而堆必须扫描找到一个合适的位置。这就费时间了
|
 |
6
dalabenba 2021-03-30 15:02:46 +08:00 via Android
不是因为堆和栈的问题，他们速度是一样的。是因为 cache,和 pagefault,第一个程序每个都是第一次访问，每个页面都会触发 pagefault，以及 cache miss 会比访问同一段地址高，第二因为在栈上没有 pagefault 的问题，而且放在栈上的话每次循环的地址相同，cache hit 率高
|
 |
7
LeeReamond OP @lsylsy2 显然是被释放了，栈空间有限怎么可能让你无限写下去。不过这个纯写入操作，缓存影响不大吧
|
|
8
dalabenba 2021-03-30 15:05:50 +08:00 via Android 1
@dalabenba 说叉了，栈上内存不会 pagefault 原因是实际访问的都是同一段，最多只要 pagefault 一次就好
|
|
9
LeeReamond OP @Justin13 堆内存逻辑上是连续的，应该只用扫描一次，感觉不是影响的主要原因
|
|
10
LeeReamond OP @12101111 看不懂啊大佬
|
|
11
LeeReamond OP @dalabenba 大佬，他这个 malloc 需要经过系统吗？学 io 的时候都说最好不要经过系统，开销大。这个 malloc 如果需要经过系统的话，那么系统必然也要经过用户态切换内核态，从 ring3 切换到 ring0 才能操作堆内存吧。如果是这样的话感觉应用程序不应该这么快啊，比如 java 当中也有大量的动态特性，如果全都需要经过操作系统的话开销不是非常大？
|
 |
12
ho121 2021-03-30 15:12:37 +08:00 via Android 1
首先需要了解进程的内存结构 https://www.geeksforgeeks.org/memory-layout-of-c-program/
然后了解一下在栈中申请内存的过程 https://stackoverflow.com/a/8629324/1968839 然后了解一下 malloc 是怎么工作的 https://stackoverflow.com/a/3479496/1968839 |
 |
13
Whurry 2021-03-30 15:35:19 +08:00
首先是栈空间能这么大吗？栈里应该存不下这些数据。
第二点是进程向操作空间申请内存空间时，一般是先虚拟内存给安排上，访问的时候发现没有对应的物理地址，触发 pagefault，然后才给虚拟地址安排上对应的物理地址。一个页一般是 4KB 。 不确定对不对，仅供参考 |
|
14
LeeReamond OP @ho121 感谢，看完了。另外我觉得这些回答写的不对，我又做了个小实验，在一百万次 for 循环里，每次循环新建一块被 malloc 的内存（该内存长度为 2 个 double，所以不会产生过大的问题），统计执行时间一百万次仅为 200ns，如果按照文章中说 malloc 都需要经过系统调用的话，传统一般认为系统调用最短也是百纳秒这个数量级的，怎么可能这么快呢。
|
 |
15
misaka19000 2021-03-30 15:48:13 +08:00
在栈上面只需要移动栈指针就可以
在堆上面有一大堆乱七八糟的操作，而且申请堆要走系统调用的 |
 |
16
love 2021-03-30 15:54:49 +08:00
代码不放出来看看？
分配机制不一样，栈上肯定不能申请这么大的内存量，栈大小很小的，否则你总听说过 stack overflow 这个词 |
|
17
ho121 2021-03-30 15:55:48 +08:00 1
@LeeReamond 程序中 malloc 一次一个小的内存，比如 8 字节，实际 malloc 在背后不会老老实实的真的向系统只申请 8 字节，大部分情况下会一次申请较大的内存，以供后面使用。malloc 只有向系统申请内存时，才会用到系统调用
|
|
18
dalabenba 2021-03-30 15:58:59 +08:00 via Android 2
@LeeReamond malloc 是 libc 实现的不是系统调用，底层系统调用的接口是 mmap 或者 brk 。一般 malloc 会预先分配一的内存块，然后把内存块分割，加入到自己的内存池中。当 malloc 自己的内存池中没有足够的内存时候，才用系统调用会从系统中拿。pagefault 会发生在系统调用后拿到内存后，第一次写或者读。所以刚刚说得还不够严谨，要是内存是从内存池中拿，且已经访问过了，而不是系统调用新分配的话，是不会发生 pagefault 的
|
|
19
ho121 2021-03-30 16:00:39 +08:00
@LeeReamond 比如这里有介绍 https://medium.com/@andrestc/implementing-malloc-and-free-ba7e7704a473 sbrk 是 Linux 中的，Windows 系统中应该也有对应的 api
|
|
20
LeeReamond OP @love 请参考四楼和七楼，现在是手机操作暂时没法放代码，不过本身逻辑比较简单，我发帖时觉得没有必要放
|
 |
21
godblessumilk 2021-03-30 16:17:41 +08:00 via Android
土字旁的 [堆] 是一盘散沙。木字旁的 [栈] 是码放得整整齐齐的木板，一捧沙里找一颗沙子快，还是一摞木板里找一块木板快？
|
|
22
godblessumilk 2021-03-30 16:21:45 +08:00 via Android
可以查查英文单词 stack 和 heap 的区别，就明白了。话说中文里 stack 翻译成堆，heap 翻译成栈，还挺贴切的
|
|
23
LeeReamond OP 2
@godblessumilk 兄弟你这个堆栈自己都能写错就别来强答了吧。。
|
 |
24
3dwelcome 2021-03-30 16:29:31 +08:00
@LeeReamond "不过本身逻辑比较简单，我发帖时觉得没有必要放"
编译器会优化掉很多，你写出来的代码，不一定是最后运行的代码。比如只 new 不填充，系统是不会给你真正分配内存的。 个人经验，影响内存速度有三点。 1 。 寻址空间大小，我有一个程序，相同的代码，访问 256M 之内时超快，访问 4G 空间时，速度下降一半。 2 。内存对齐，x86 访问非对齐内存，会有额外多余开销。 3 。就是 malloc(堆)和 alloca(栈)区别了，后者是真的快，用飞速也不为过。 |
 |
25
aeon113 2021-03-30 16:42:49 +08:00 via Android 1
贴一下你的代码和编译选项吧
malloc 执行过程中是有可能会进入到内核态的，并且，我记得在 Linux 中，给用户进程分配出的虚拟地址事实上并没有对应物理内存，物理地址会在目标 page 第一次被访问时分配。这个可能会造成进程在写入大数组时又多次陷入内核态。 可以尝试 malloc 一次，然后多写几次，丢掉第一次写入的测试数据，用剩下的写入延迟算出一个平均值做结果。 另外，这里栈上的写入过程相当于对同一段栈内存写入了 10000 次。如果不是用 memset 来写的话，那有可能前 9999 次全部被优化掉了只剩下了最后一次。这个得看编译器的生成结果才能确定。 数组大小不同，占用的 CPU cache line 数量也不同。一块 CPU 不是只有一个进程在使用，每个进程对内存的每次读写都可能造成某个 cache line 内的原数据被刷出，新数据被读入。那么数据 size 越大，占用的 cache line 越多，其内部分数据被刷出的概率也就越高，相对性能也就会更差一些。 最后，如果机器内存不大的话，访问堆内存时也可能会因为 swap 和刷 dirty page 损失不少性能。 |
 |
26
hyyou2010 2021-03-30 20:12:32 +08:00
1，栈增加是索引地址加加，栈归还就是索引地址减减，几乎没有更快的空间分配方式
2，堆分配空间则是从整个堆空间寻找一片合适的，这个并不简单，要防止空闲空间成碎片以至于后续无法使用。归还时还得合并空闲空间，也是一笔很大的开支 |
 |
27
IsaacYoung 2021-03-30 20:27:46 +08:00 via iPhone
sbrk 更新页表
|
 |
28
kejialiu 2021-03-30 23:17:14 +08:00 via Android
还有寄存器优化。C 语言很多局部变量原则上是分配在栈上，但编译器优化后直接放通用寄存器就好了，都不需要进内存
|
 |
29
iceheart 2021-03-30 23:54:37 +08:00 via Android 2
以上一个答对的都没有。
栈比堆快只有一个原因: 栈一直在访问，没有机会被换出 cpu 缓存，所以栈内存访问总是高速缓存命中，快 30 倍是 cpu 高速缓存与内存实际访问速度的差距 |
 |
30
irytu 2021-03-31 01:19:31 +08:00 via iPhone
堆内存分配挺复杂的 有可能会 trap 到内核里 在地址空间不够的情况下 需要 sbrk syscall 来增长 然后第一次访问的时候 page fault，其实栈也有类似的情况如果没理解错 栈的不够用了 也会 trigger 一次 page fault 更新 page table 直到 stack overflow ？😂
但是差距就在栈的分配比堆简单很多，堆分配我记得挺复杂的，csapp 上有讲过类似的例子，实际还要考虑楼上提到的地址空间碎片化的问题，分配的效率等，一般根据实现不同可能会有 O(n), O(logN) 这种时间开销 https://stackoverflow.com/a/283164 |
|
31
irytu 2021-03-31 01:25:32 +08:00 via iPhone
刚刚查了一下 似乎 sbrk 这个 syscall 渐渐被废弃了 用 mmap(2) 取而代之
|
 |
32
gyf304 2021-03-31 01:36:00 +08:00
你这个控制变量都没有，heap 比 stack 大那么多，cache miss 肯定很严重啊。
还有就是如上面说的，mmap 要经过内核，初次写入被分配的页的时候也是是要 page fault 的，也是要过内核的。 建议读一下《 CS:APP 》关于内存的内容 |
|
33
gyf304 2021-03-31 01:40:11 +08:00
@2435043xia 栈和堆内存物理上是没有区别的
|
|
34
gyf304 2021-03-31 01:47:10 +08:00
@godblessumilk
我个人认为用比喻的方式学习是比较糟糕的方式。入门可以，拿来解释东西不太妥当。“因为 A 像 B，所以我们用 B 来解释 A”是不合逻辑的。 堆和栈内存在物理上是没有区别的。 |
 |
35
geelaw 2021-03-31 03:06:17 +08:00 via iPhone
为什么楼上都有这么多答案…
这个问题会因为楼主使用了何种 C 语言编译器、如何申请的堆内存有千奇百怪的答案。如果楼主用的 malloc 内部维护一个结构，且优先考虑直接分配刚刚释放的内存，且没有发生优化，是不可能会有这么大的差别的。 |
 |
36
xiadong1994 2021-03-31 05:43:18 +08:00 via iPhone
可能的影响太多了，编译器优化，malloc 实现都没考虑。先看看优化后的汇编是不是你想的那样。
|
 |
37
myy1966 2021-03-31 09:39:21 +08:00
https://github.com/spuhpointer/stack-vs-heap-benchmark
都带数据初始化的话，堆和栈的速度几乎一样。你对栈的程序跟堆不同，栈上在循环里创建数组的话每次到下一个循环会把上一次创建的数据销毁，然后重新创建数组，这样你的数组实际上一直在使用一块相同的内存空间，这增大了缓存命中的概率。而你的堆的程序直接创建了长度为 1 亿的数据，这样连续的访存会产生很多缓存不命中，降低了性能。公平的对比办法是手动把操作系统预设的栈大小改大到可以容下 1 亿长度的数组，然后在栈的测试中直接创建长度为 1 亿的数组，这样测试出来的性能堆和栈应该是差不多的。 |
|
38
3dwelcome 2021-03-31 09:59:56 +08:00
```
double* test1 = new double[10000*10000]; for (int i=0;i<10000*10000;i++) test1[i] = 0; ``` ``` double* test2 = (double*)alloca(10000); for (int y=0;y<10000;y++) for (int x=0;x<10000;x++) { test2[i] = 0; } ``` 我的堆 /栈测试代码，test1 堆运行完是 0.4s, test2 栈是 0.2s ，很符合自己盲猜结果。哪有楼主说的 30 倍差距，肯定是有什么 bug 。 |
|
40
dalabenba 2021-03-31 10:22:27 +08:00 via Android
@3dwelcome cache 对于 cpu 访问内存是透明的，栈和堆只不过是进程地址空间划分的两个部分，下面映射的物理内存都是一样的
|
|
41
3dwelcome 2021-03-31 10:34:40 +08:00
@dalabenba 好像你们说的对。
我 test2 代码里，把 alloca(10000)换成了 malloc(10000)，两者用时结果是一样的。 原测试 test1 慢，可能就是寻址内存过大，cache miss 导致的。 本来以为 alloca 分配的地址，更接近运行代码块，就更容易被 cpu cache，速度就更快。也许看 cpu 心情才是最重要的。 |
 |
42
Claar 2021-03-31 11:43:11 +08:00 via iPhone
栈的申请在编译期已经确定，只是 esp 和 ebp 的偏移。堆的申请本身是在一个大范围空闲内存中进行空间申请，这涉及到 glibc 如何基于当前情况分配的问题(如何整理现有的小内存等操作)，是一个不算简单的过程，详情可以去看看 ctfwiki 中关于 pwn 下 linux 的堆管理器的讲解，或者直接看 glibc 的源码里关于 int_malloc 的部分
|
 |
43
wellsc 2021-03-31 22:21:06 +08:00 via iPhone
@godblessumilk 社死现场
|
Select Language