因为个人对java并没有什么热爱, (然而我的c++书籍的阅读却没有我小说的阅读进度快…) 加之近来身体不佳。 关于java同期的探索暂且告一段落———反正这个知识早晚会再次用到。(那时再来探索吧) 虽然我应该近期会优先探索非同期的部分——nodejs的部分。

关于rust

缘由是在知乎上偶然看到这个东西。我错把这个东西当成的c++的一个衍生物品。以为是类似于RAII一类的东西。 事实上随手查阅这个东西的时候,才发现是一门语言。 而且是Mozilla主导开发的。一下子好感度大增,撇下只是看维基百科没有看的太明白的RAII,读起了rust的document。

rust的document很完备。 我这里就权当一个读书笔记了。

heap和stack

为什么讨论heap和stack?

  • rust的文档中提到了他俩
  • 事实上语言在内存中运用的时候,有时候会考虑到这两个数据结构。因为这是计算机内部的系统结构的一部分。

基础概念

关于algorithm上heap和stack是怎么一个定义这里就不多赘述了。因为stack的结构简单,所以 理论上stack会比heap要快。 在acm中heap常会被用一个array来实装,而stack由于一般大多的stl都会提供实装,所以并不需要手动实装。

这里需要说一个点就是,日文维基百科中会说到heap的删除时间是O(log(n))。 这个给我绕住了。 因为我印象中,比如容纳{4, 5, 6}的一个heap的话,指定删除一个值6,事实上不可能是log(n)。 然后我看到了搜索一个值需要的时间是O(n),我迷惑了,怎么搜索的时间会比删除的时间要长。 然后我意识到,容纳{4, 5, 6}的一个heap的话,删除一个值是说,删除一个指定index值的值。 相当于删除index是0 or 1 or 2 的一个值。这样的话删除时间的确是O(log(n))。

(PS:英文和中文维基百科就讲的很清楚:“delete-max [or delete-min]”)

绕开heap和stack这些繁复的algorithm的基础定义。 我们来看rust中是如何定义内存中heap和stack的使用的。

The heap, on the other hand, is slower, and is explicitly allocated by your program. But it’s effectively unlimited in size, and is globally accessible. – rust first-edition document 4.1. The Stack and the Heap

Accessing data in the heap is slower than accessing data on the stack because we have to follow a pointer to get there. Contemporary processors are faster if they jump around less in memory. When our code calls a function, the values passed into the function (including, potentially, pointers to data on the heap) and the function’s local variables get pushed onto the stack. When the function is over, those values get popped off the stack.

– rust second-edition document 4.1. What is Ownership?

也就是说,

  • 在内存中,stack是被你的rust确保的,而heap是被你写的程序所确保的。
  • 确保空间大小的时候,stack是必须是固定大小。heap是pointer式的指向,所以不用固定大小。
  • heap往往是全局类的(global)。

关于stack

再详细的讲。 在呼叫一个函数(function)的时候。函数的一部分情报,以及函数内部的定义的局部变量,会被记忆到stack中。 这也是在acm中,使用递推(Recursion )来解决一些问题的时候,由于呼叫自己的次数过多,导致内存不够用, 产生著名的stack over flow问题。(这里并不是在说同名问答论坛)

这样的stack空间,在这个函数结束的时候,会被解放。 也就是说,哪怕你的这个函数内部定义了1GB大小的非pointer式指向的array, 但是是被线性呼叫的,而不是被同时呼叫。 那么在4GB的内存上理论上也是没有问题的。

关于heap

也就是说,在函数内部呼叫例如

1
std::set<int> a{1, 2, 3};

的一行的时候,这里使用的就是heap。

使用heap的时候需要注意产生的一个问题就是,由于属于pointer指向,会产生这个内存领域没有被解放的问题。

比如,函数内部呼叫上面的一行指令的时候,会在stack(根据rust的document)生成一个pointer,指向heap领域。 在函数结束的时候,这个pointer会跟着一起被毁灭。但是所指向的heap领域在有时候并不会被毁灭。 在c++中,大部分stl(可能是所有的?)在函数结束的时候都会自动运行destructor(如果我没有记错)。 来进行内存的解放。 然而过分的解除和确保heap领域可能会造成fragmentation问题 (?)(参见ヒープとスタック 这里就已经是硬件方面的编程了,属于我不懂的领域)

rust是如何处理这一问题的呢?

结语

这里我有一个疑问,那么全局变量呢(global variables)呢?如果是array或者int的话? 是属于stack还是heap? 答案是在c中,这是使用了另一个叫做data segment的区域。(参见関数や変数のメモリ配置

那么rust是如何处理这些繁复的内容的呢? 这些疑问留给下次吧,我累了= =

参考资料:


creativ common license