V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
vevlins
V2EX  ›  JavaScript

js 的 reference values 一定在堆上, primitive values 一定在栈上吗?

  •  
  •   vevlins · 2019-12-27 14:12:17 +08:00 · 3466 次点击
    这是一个创建于 1823 天前的主题,其中的信息可能已经有所发展或是发生改变。

    按照我对堆和栈的理解,区别主要是两个:

    1. 生命周期不同,栈与函数执行周期相同,堆则贯彻始终。所以想要某些数据的生命周期更长的话放在堆上
    2. 容量不同,栈的容量小,没有动态伸缩(?不太确定),而堆则比较大

    那么如果一个对象只在 fucntion 内使用,且容量不变,比如 arr = [1,2],一直不变。js 引擎会如何处理? 还是理论上可以放在栈上,但 js 没有静态检查的能力所以才放在堆上,又或者这些优化无足轻重?

    是否在堆在栈根本性上不取决于 primitive 与否,而是看数据是否 immutable ? 当然 primitive 的都是 immutable 的,只是讨论根本性质是否是啥。

    16 条回复    2019-12-29 14:22:08 +08:00
    vevlins
        1
    vevlins  
    OP
       2019-12-27 14:35:57 +08:00
    ecma 没有对内存分配做规定,那 v8 等主流的引擎是如何实现的呢? 我看到过有 stackoverflow 回答中提到 null\undefined\true\false 在 v8 实现中是放在堆上的,类似于 Java 中 Boolean.True 的概念,为何要这样设计?
    muzuiget
        2
    muzuiget  
       2019-12-27 14:45:10 +08:00   ❤️ 2
    JS 里又不能直接操作内存,谈在 JS 里谈堆 /栈内存无意义,都不是同一语境的东西。
    vevlins
        3
    vevlins  
    OP
       2019-12-27 14:50:24 +08:00
    @muzuiget v8 是用 c++写的,是否要看 c++中如何实现呢。我也有这种想法,但按照这种思考方式,哪些语言 /编译器才有直接操作内存的能力呢?
    vevlins
        4
    vevlins  
    OP
       2019-12-27 15:02:19 +08:00
    再明确一下讨论的范围,js 确实不直接操作内存,具体原理肯定要考虑到解释器 /编译器的实现,但这样思考感觉又像是套娃。至少按照这种说法,java 也没有内存一说了。

    但是按照我的理解,诸如 primitive 和 reference 这种在 ecma 中制定并描述了其行为的数据类型,JS 引擎为了实现这种行为规范,应该会在底层采取某种内存分配方式。

    讨论的范围仅限制在规范层面和 V8 实现层面。
    momocraft
        5
    momocraft  
       2019-12-27 15:14:56 +08:00
    建议先想清楚栈是什么。OS 线程的栈也叫栈,有个数据结构也叫栈。

    对于 JS 解释器来说,可能没法简单放在 OS 线程的栈上(否则无法同时实现闭包和 setTimeout )

    IMHO 可以自己试试写一个,会比抠字眼收获大很多
    lihongjie0209
        6
    lihongjie0209  
       2019-12-27 15:36:43 +08:00
    你应该问 js 的一个 runtime 是怎么实现的

    在浏览器中运行一段代码和在 Java 中运行一段 JS 代码是两个概念
    nfyig
        7
    nfyig  
       2019-12-27 15:37:11 +08:00
    一个闭包变量即使是 primitive values 也会在存在于堆上
    marcong95
        8
    marcong95  
       2019-12-27 15:52:48 +08:00
    考虑到 string/symbol 这种 primitive type,直觉觉得应该放堆上放栈上应该与 primitive 没有必然联系

    arr = [1, 2] 似乎从规范上应该等同于 { 0: 1, 1: 2 } 所以似乎也不怎么可能放堆上?

    primitive 的变量不是应该是 mutable 的吗,还是我对 mutable 的理解有什么偏差?
    marcong95
        9
    marcong95  
       2019-12-27 15:53:15 +08:00
    @marcong95 #8 第二段更正:似乎也不怎么可能放栈上
    vevlins
        10
    vevlins  
    OP
       2019-12-27 15:53:51 +08:00
    @nfyig 按照我的理解,本身这个变量确实是 primitive,但被引用做闭包后这个量被包含在了返回的的 function 对象内部,从 primitive 变为一个 reference 量下类似于 upvalue 之类 key 对应的 value 了。这跟题目中的说法不冲突。
    vevlins
        11
    vevlins  
    OP
       2019-12-27 15:59:14 +08:00
    @marcong95 v8 对 string 的存储似乎有些复杂,看了几篇文章没看懂,情况有些多。 但有的地方提到了 v8 对单个字符的上限有 512MB,应该是存在堆上。

    primitive 的确实是 immutable 的,重新赋值会重新开辟一个空间。当然我也没看过 v8 之类的实现,但大多数文章都是这样说的。
    vevlins
        12
    vevlins  
    OP
       2019-12-27 16:07:43 +08:00
    又想了想,感觉自己是被很多“深拷贝浅拷贝”之类的文章误导了。

    存储在哪里跟 primitive 与否没有任何关系,完全取决于实现方式。不过之前说的前提还是成立的,1 要考虑生命周期 2 要考虑会不会爆栈。 在这个前提下,即使是 primitive 的字符可以放在堆上,因为一个字符类型的量大小范围非常大。
    vevlins
        13
    vevlins  
    OP
       2019-12-27 16:34:34 +08:00
    再补充下,看到有文章说所有值都是存储在堆内存上(现在的 v8 不一定这样,跟上面说的一样应该怎么实现都可以,只是效率和稳定性的区别),栈中只存储指针,感觉这种说法很合理,指针的大小都是固定的且比较小的,如果还超过就爆栈。 垃圾回收机制应该跟大多数文章说的一样,按照我现在猜测,如果是 primitive 则在退出后清理引用的空间,reference 才走完整的垃圾回收机制。primitive 是 pass by value, object 是 pass by reference,所以才有深拷贝和浅拷贝的区别。

    至于 immutable 还是 mutable,还要再深入理解下。
    vevlins
        14
    vevlins  
    OP
       2019-12-27 16:36:19 +08:00
    @vevlins 正因为 reference 才需要走完整的垃圾回收机制,因为不确定该指针在什么地方被引用了。但 primitive 每次都是 pass by value,自然跟作用域保持一致就可以。
    secondwtq
        15
    secondwtq  
       2019-12-29 02:27:54 +08:00   ❤️ 1
    说来话长 ...

    首先明确一点,语言的 spec 里一般不会关心堆 /栈这些问题。也就是说楼主最开始的问题“reference values 一定在堆上,primitive values 一定在栈上吗?”的答案是否定的。

    然后说实现问题,JavaScript 是动态类型语言,虽然动态类型语言在语言本身定义和实现上和静态类型语言有很多不同,但是动态类型语言的编译器实现技术和静态类型语言没有本质上的差别。考虑静态类型语言和动态类型语言之间,最重要的区别是什么?当然是在动态类型语言中,一个变量的类型只能在运行时确定,或者说所有的 type checking 都发生在运行时。

    主流的动态类型语言优化编译器实现最大的区别是引入了一套新思想:在编译的过程中逐步去除语言的动态性,并对于 hotspot,根据上下文和运行时信息对类型等信息做 speculation,对常见的 path 做 specialization,在执行这些 specialized code 之前做 check,如果和预期不符则进行 deoptimization。其实也不算新,静态类型语言做 PGO 之类的跟这个很类似。

    但是无论是用解释器还是 JIT 优化编译器的方式实现动态类型语言,最后在一方面的结果是相同的:就是最后生成的代码和数据结构都可以转换成某种静态类型语言(不特指 C,因为存在结构体布局等一般是非标准的细节,另外 deoptimization 应该也不能以标准 C 来表示)。也就是说可以用静态类型语言来模拟动态类型语言——比如定义一个类型叫 any,这个类型实现了所有的操作符,同时还可以包含任意的字段。然后在运行时调用的时候检查是否合法。

    然后楼主的问题就转化为:这个 any 类型应该怎么存储? any 实际相当于一个 Union Type,但是我们知道 C/C++ 里面的 union 是不 type safe 的,原因是 C/C++ 里面的 union 本身并没有存储类型信息,C/C++ 项目中所有用到 union 的地方,要么是在其他地方存储了类型信息,要么就是依赖于某种 UB。动态类型语言要想做到“在运行时进行 type checking”,就必须在存储值的同时存储对应的类型信息(否则就退化成无类型语言了),在静态类型语言里面存储类型信息的例子并不少,比如 C++ 的虚函数表就属于这类东西,同理 Java/C# 的对象会有对象头信息,甚至会把整个类型塞进去做反射用。

    在这里可以对这一堆东西做个简单的区分:Java/C# 如果不考虑 boxing,它们的 Object 类型结合反射也可以用来模拟动态类型( Java 更统一一点,C# 本身有个 Dynamic 类型,还有 struct 之类的)。C++ 的虚函数 /RTTI 则是比较受限的一种形态——只限于预定义的有限的几个函数,只能在预先声明的 class hierarchy 里工作。

    Java/C#/C++ 的这些机制有一个共同的缺点就是:在实现中一般会对一些常见的类型做优化,因此语言中会出现 primitive type 和非 primitive type 的区别(此处的 primitive 不指 JavaScript 中的 primitive,比如 String 在 JavaScript 中按照标准是 primitive,但是在 Java 和 C++ 里面都只是普通的类而已),primitive type 无法直接利用这一机制,Java/C# 用 boxing 来绕过了这一限制,C++ 则需要手动实现 boxing (何况本来就是受限的)。

    Haskell、OCaml、Rust、Swift 等语言则基于 Algebraic Data Type,提供了 tagged union + pattern matching。这一套机制可以直接 cover 所有的类型,同时也不碍着编译器做优化。TypeScript 的类型系统允许用户手动实现这一套机制。其弱点是在实际应用中的扩展性受限,Scala 的 case class 则是另一个有趣的结合体,学术界另有若干论文尝试解决这个扩展性的问题。

    tagged union 这个扩展性问题具体说来就是:一个 tagged union 内部包含哪些选择,在声明时已经确定,不能像 Java 那样通过声明新类来添加新的类型。( OOP 另有自己的扩展性问题,这是另一个 topic,此处按下不表)这个问题带来的一个好处就是 tagged union 所占大小是可以在编译时确定的——在 C 的角度,最简的通用实现就是一个 struct 里面放了一个 union,但同时还放了一个字段表示当前使用的是 union 中的哪个类型,并且编译器帮你去做转换和检查工作。

    从实现角度看,可以说 Java/C#/C++ 更偏向于 pointer dispatch,tagged union 则是 tag dispatch。这是两种基本的实现手段。在实践中,tag dispatch 可以在堆上也可以在栈上,pointer dispatch 一般和堆分配有更强的关联(但是理论上,实现动态行为的机制和内存分配的机制是正交的)。但是要特别注意的是,tagged union 的实现一般都是以 C/C++ 的 union 为基础,所以 C/C++ 的 union 可以怎么分配,tagged union 就可以怎么分配。

    动态类型语言的 “any” 类型在绝对能力上则是最强的——可以包含一切类型,可以包含一切数据和操作。但是这个类型该如何实现呢?最后还是要落到上面两种实现手段上。(以上说的这些都是 type safe 的,C/C++ 的裸 union 因为不 type safe 被排除掉了)

    类 Java/C# 的这种模式,在一个大家很熟悉的动态类型语言里面被应用了:就是 Python 的 CPython 解释器实现,在 CPython 中,所有的数据都存在堆里面,CPython 的解释器栈仅仅会存储对堆数据的引用,就算是 primitive type 的值也会变成 PyIntObject、PyFloatObject。这些堆中的 object 的文件头会存储类型信息,在应用某个操作符的时候调用某个函数之类的。

    注意 JavaScript 也可以使用同样的方式实现。当然大家也知道 CPython 是出了名的慢(毕竟每一个操作都相当于过了一次 Java 的反射),这个现在的 JS 是没法接受的,你实现那么慢我们的垃圾代码怎么办?(什么你说优化代码?对不起我们只会写垃圾代码)那就要考虑进行优化,那这个 object 可不可以放在栈上呢?

    我前面说了这个 object 相当于一个 any 类型,即所有类型的 Union。一般在 C/C++ 中,union 所占的空间由其所有类型的大小的最大值决定(还要根据对齐调整一下)。any 类型理论上包含所有类型,而用户理论上可以定义无限大的类型——结果是如果同样按照 Python 一样教条式的做法,坚持把数据全放栈上不动摇,any 类型只能无限大,不存在足够大的内存可以容纳这个类型,直接 Game Over。

    解决方法就是改革开放,哦不变通一下——一般做法是由语言的实现钦定一些“primitive type”(注意此处的 primitive type 依然和 JavaScript 的 primitive 无关,而是实现角度的 primitive )使用栈分配 + tag dispatch,其他类型(包括用户定义的类型)作为“reference type”使用堆分配 + pointer dispatch。这和静态类型语言编译器针对一些 primitive type 做优化的思想是一样的。这样做的结果是,按照“union 所占的空间由其所有类型的大小的最大值决定+对齐调整”的规则,在 64 位机器上,假设钦定 bool, (unsigned) int 8/16/32/64, float, double 为 primitive type,再加上 reference type 所需的 64 位指针,这个 tagged union 的数据部分只需要 64 位就行了。前面说了单纯的 union 没用,还需要存储类型信息,那这个理论上需要 4 位来存储,实际会对齐成 ... 64 位,就是说一个值放栈里,占 128 位 /16 字节的空间。

    注意上面两段默认了一个公理,就是“union 所占的空间由其所有类型的大小的最大值决定+对齐调整”。因为前面说了“动态类型语言的编译器实现技术和静态类型语言没有本质上的差别”,而这个条件在大多数静态类型语言中都是成立的。于是才有了动态类型语言使用真·所有类型的 union 不可行->使用 primitive/reference type 做优化的结果。理论上,动态类型语言可以根据自己的特点,把值所占空间缩减到 实际数据大小+类型信息(也就是推翻以上公理),这么做的一个后果是:any 类型的大小不是无限的了(除非用户真的定义了无限大的类型),但是依然是不可确定的。“不可确定大小的类型”如何进行优化是少有先例的——比如在 C/C++ 中根本不允许使用 incomplete type 创建对象,唯一的例外是 C 里面极其受限的 VLA。

    上面最后还有一个问题,就是 tagged union 实现方式中,4 位的类型信息最后会被放大成 64 位,很大一部分空间被浪费了。这个同样有一个通用的做法,就是利用各种骚操作把至少为 2*sizeof(intptr_t) 的值大小优化成 1*sizeof(intptr_t)。这个具体的做法,Andy Wingo 称为 “value representation”,并且写了一篇文章来讲这个事情( https://wingolog.org/archives/2011/05/18/value-representation-in-javascript-implementations )。简单来说就是:现在的 64 位平台虽然名义上有 64 位地址空间,但是实际上只用了 48 位,另外 16 位是空的,所以可以拿 1 位来区分 reference 和 primitive ( 32 位平台没这福气,但是有一些其他的机会比如语言实现可以做一个“所有内存分配都会对齐到 4/8 字节”之类的保证,这就留了两位出来),但是这样就又有了其他的限制——原来 64 位的整数,有 1 位不能用了,那没办法只能用 63 位整数。另外只有 1 位用来存储类型信息就不能区分整数和浮点——相当于只区分了 63 位整数和指针。这些又可以有其他的优化手段。值得一提的是 JavaScriptCore 的做法:因为 JS 中只有 double 一种数值类型,所以它利用浮点类型的特性,在 64 位机器上实现了一个 64 位值对 64 位指针和 64 位浮点两种类型的区分 ... 实在是高

    但是绕来绕去,最后达到了一个目的:就是实现了一个固定大小的 any 类型(至于这个“固定大小”到底有多大是另一个问题,但是一般是实现为 1*sizeof(intptr_t))。我把这个叫做“uniform representation”。这个属性不仅对动态类型语言有用,对静态类型语言也有用。比如 GC 需要这项能力来区分指针和非指针。Java 通过 boxing,事实上也实现了 uniform representation,并且 Java 的泛型依赖于此来实现。同样的做法存在于 Haskell 和 OCaml 中(所以在 OCaml 中可以看到 int63 这种奇葩类型 ... OCaml 也有 int64,但是是 boxed 的)。实现 uniform representation 会方便更多动态语言特性的实现(简单的泛型可以不依赖 uniform representation,用 Monomorphization 来实现,但是 Higher Ranked Polymorphism 之类就没这么简单了)。

    如果要对楼主的问题简单给一个答案的话,那就是:在具备 uniform representation 的语言实现中,被钦定的那部分 primitive 是 有可能 放在栈上的,reference type 是 一定 放在堆上的。

    这个结论同样假设了一个前提:根据上文,reference type 的定义仅仅是“除开 primitive type 之外的所有类型”,在 any 类型中借助指针来表示,连 primitive 都不一定是分配在栈上,reference type 又怎么能钦定放在堆上呢?编译器能不能把一部分 reference type “优化”在栈上呢?

    理论上是可行的。比如静态类型语言编译器里面有一种优化叫 Scalar Replacement of Aggregates ( SRA/SRoA ),简单来说就是满足一定条件的前提下,把一个复合类型里面的字段展开成单个的变量。在静态类型语言中这有利于进行进一步的优化,在存在 reference type 的语言中,成功的 SRoA 还可以减少内存分配、访问和 GC 压力——你想想如果一个 reference type 值里面所有的值都是 primitive type,SRoA 之后不就相当于消灭了原来的 reference type 值,全变成 primitive type 了么。

    但是优化必须保证不影响原有语义。也就是说编译器不仅要实现 SRoA,还只能在经过分析确保安全的情况下才能进行。所有的优化都是可选的,编译器就像一个尸位素餐的用户公仆,觉得可能有问题就放弃优化——和人类的公仆不同的是,机器公仆虽然在执行时同样的懦弱,但是之前会尽量根据已有的信息做分析(对于 SRoA 来讲主要是 Escape Analysis 和 Alias Analysis )。这里就涉及到动态类型语言和静态类型语言在非技术层面设计思路的根本分歧:动态类型语言的设计者不仅不想让用户提供类型信息,也同样认为程序员不需要提供除了所谓“程序本身”之外的信息。动态类型语言的用户上行下效,通常也不屑于提供此类信息。静态类型语言则认为自由来源于合理的限制,所以很多静态类型语言并不拒绝在程序中提供显式的,有利于优化的信息,并且类型信息本身就是对优化最有价值的信息。

    一来二去造成了一个结果:就是静态类型语言实现在编译时可访问到的程序信息远远大于动态类型语言。

    动态类型语言的高性能实现为了填语言设计者挖的坑,就必须在没有额外信息的情况下,在运行时猜出所需要的信息。这个猜出的结果随时都可能失效,所以还得准备相应的 fallback。对动态类型语言做有效的优化,难度要比静态类型语言更大。

    当然,一般认为动态类型语言有它的优势:就是如果代码写得足够好,编译器在运行时通过运行时实际统计到的信息进行优化,理论上效果会比只能使用编译时信息的静态类型语言要好。但是这个优势明明是 JIT 的优势,不是动态类型语言的优势——静态类型语言同样也可以做 JIT,同样也可以在运行时收集信息并用于优化。并且 JIT 这种形式天然受 latency 限制,不能进行特别复杂的优化,在很多场景下,如果保持其他变量不变的话,静态类型语言的 PGO 绝对效果是更好的。总的来说就是,在编译器可以利用到的信息量方面,静态类型语言严格大于动态类型语言。指望 JS 靠 compiler magic 超过 C/C++ 并不现实。

    王垠前两天发了篇文章叫《我不是编译器专家》,在这篇文章中,王垠(再次)强调了业界对编译器和 PL 两个领域普遍的混淆,并且表达了对编译器技术上的藐视、对编译器人坐井观天、目中无人作风的批判。我们暂且忽略王垠三年半之前发了一篇内容相似的《我为什么不再做 PL 人》,并且把相似的罪名同样安到了 PL 圈子上的事实(不行我还是要笑),王垠所说的一些问题是确实存在的。编译器到底是夹在语言和硬件的 spec 之间,戴着镣铐跳舞的活。很多编译器费尽力气分析的结果,从语言上很简单就能解决。这是维度上的差异。新的 ECMA 标准加入的 strict mode、let、const、module、rest parameter 等特性都有尝试从语言层面改进性能的成分。

    反映到这个贴子的问题上就是,在 JS 中做同样的优化会更难。V8 据称是实现了 SRoA,但是具体效果我没研究过,楼主可以自己试一试。
    vevlins
        16
    vevlins  
    OP
       2019-12-29 14:22:08 +08:00
    @secondwtq 感谢回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1349 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 46ms · UTC 23:53 · PVG 07:53 · LAX 15:53 · JFK 18:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.