相关文章推荐
鼻子大的红金鱼  ·  hive 排序 ...·  3 周前    · 
曾深爱过的黄瓜  ·  mysql ...·  4 月前    · 
忐忑的土豆  ·  In a declarative ...·  1 年前    · 
活泼的木耳  ·  windows10 ...·  1 年前    · 
var intern_1 = makeExpoStr() ; intern_1 = internFunc(intern_1) ; var intern_2 = makeExpoStr() ; intern_2 = internFunc(intern_2) ;

case 1:flatten(扁平化)

flatten_1 === flatten_2;
                        

case 2:intern(常量化)

intern_1 === intern_2;
                        

通过测试我们发现常量化(case #2)比扁平化(case #1)字符串比较性能快 ~10x 倍左右。

(条状图越长,性能越高)

这里需要说明的是,这个性能差异会随着字符串长度而变化(越长性能差异越大)。

要解释这个现象,先要了解字符串中很重要的一个概念,常量字符串(InternalizedString)。

V8 为了最佳性能与最少内存使用将某些(如字面量构造的)字符串常量化。

在分配常量字符串时会先计算其 Jenkins's one-at-a-time hash 作为 key 在 string_table 中查出 hash 相同的字符串并比较内容是否相同:

  • 如相同则直接返回(不再额外分配空间)。
  • 未找到(不相同)才会在老生代(数据区)中分配空间并将 key 写入 string_table。
  • V8 定义计算 hash 的最大字符串长度为 kMaxHashCalcLength = 16383,大于此长度的字符串直接使用其长度作为 hash 值(存在较大的哈希碰撞 Hash-collision 风险)。

    hash 相同不代表字符串(内容)相同,需对其内容进行比较后才能最终确定。但 hash 不同的字符串内容肯定不同,所以在比较两个已计算 hash 的字符串是否相等时,可以以 hash 不相等作为快速负检查(Fast negative check)。

    StringTable 继承于 HashTable,实例 string_table 可理解为字符串的常量池。

    综上所述,内容相同的常量字符串具有相同的引用(共享同一块老生代空间),在比较时直接比较引用(指针)是否相等即可 。

    V8 规定常量字符串一定分配在老生代(data space)数据区空间。

    我们来看个例子:

  • 以字面量构造的字符串 #hello 、#world 为常量字符串。
  • b 由于赋值的缘故它与 a 有着相同的引用。
  • c 与 d 均不是常量字符串。
  • 两个(常量字符串) #world 也拥有相同的引用。
  • 在 V8 日志中,常量字符串以 # 号作为其前缀标识。

    在开发调试过程中,可以调用 V8 的 Runtime Call (%InternalizeString)来常量化字符串,如下所示:

    // flags: --allow-natives-syntax
    var a = "hello" + "world"; 
    // a = <ConsString>
    var b = %InternalizeString(a);
    // b = <SeqOneByteString>, Internalized
    // a = <ThinString>, Internalized
                            

    而在运营环境中,当字符串被设置为对象属性名时会被尝试改造为常量化版本,如下所示:

    var a = "hello" + "world"; 
    // a = <ConsString>
    var obj = {};
    obj[a] = true;
    // es2015: {[a] : true}
    var b = Object.keys(obj)[0];
    // b = <SeqOneByteString>, Internalized
    // a = <ThinString>, Internalized
                            

    为什么通过上述两(qi)种(ji)操(yin)作(qiao)可以常量化字符串了?

    我们要先从 Runtime Call (%InternalizeString) 说起,在 V8 内部其实是直接调用了 v8::internal::Factory::InternalizeString 方法,但这方法的 namespace 为 v8::internal 无法直接在外部(包括 JavaScript 与 外部 C++ 代码)进行调用。

    虽然我们不能直接进行调用,但是我们可以通过一些方法的 side effects 来隐式调用,而将字符串被设置为对象属性名就是运用了这个技术。

    在 V8 中有如上图的途径可以隐式调用到 InternalizeString 方法,而我们的奇技淫巧也正是利用了这条通路。

    根据 ECMA-262 标准,在设置对象属性名时,V8 会调用 TryConvertKey 尝试将传入类型转换为字符串类型,并调用 InternalizeString 将其常量化。

    InternalizeString 方法中的查找过程已在文章开头介绍过,而将常量化过程的实现如下:

  • 在老生代(data space)空间中分配一个 SeqString 实例(b)将字符内容拷入。
  • 新分配的 SeqString 实例(b)<Map> 中的 instance_type 加上 kInternalizedTag 标记,标识为常量字符串。
  • 用 ThinString<Map> 替换原实例(a)的 <Map>,actual 字段引用新分配的 SeqString 实例(b)。
  • 最后根据 ThinString 的大小调整原实例(a)在堆内的大小。
  • 我们在《奇技淫巧学 V8 之二,对象在 V8 内的表达》中提到:每个在堆内创建的实例均有一个描述其结构的 <Map> 。
    也就是说,当实例的 <Map> 发生变更时,实例的类型也会随之改变。

    最终形成如下图所示的结构:

    由于常量字符串(新生代)与非常量字符串(老生代)所在的分代不同,故不能直接将原实例(a)就地(in-place)常量化。

    V8 通过将字符串实例类型转换为 ThinString 并引用常量字符串来实现隐式就地转换。

    我们在《奇技淫巧学 V8 之六,字符串在 V8 内的表达》中提到:多数情况下可认为 ThinString 与 one-part ConsString(actual, empty_string) 在内存布局与算法逻辑上是等价的。

    故未启用 ThinString 类型支持时,根据原始字符串的不同表达 V8 会有不同的处理方案:

    1、原始字符串为存储类型表达(如:SeqString)时:

    由于缺少 ThinString 的支持(再加上处于不同的分代)无法实现就地常量化,故:

  • SeqString 实例 #0(a)并没有发生任何变化,仍然是非常量字符串。
  • 常量字符串必须从对象 obj 的 keys 中取出,也就是(新创建的)实例 #3 (b)。
  • 文章开头 benchmark 中的 internFunc 基于兼容性考量,使用了从对象 keys 中取出的常量化版本(b),如果在支持(开启) --thin_strings 的 V8 版本中运行,也可直接使用就地转换的版本(而不需要重新赋值)。

    用(JavaScript)伪代码来表达:

    // pseudocode
    var a = "hello" + "world";
    // ONE_BYTE_STRING_TYPE
    var obj = {};
    obj[a] = true;
    if (FLAG_thin_strings) {
        // in-place internalization
        return a;
        // THIN_ONE_BYTE_STRING_TYPE
    } else {
        return Object.keys(obj)[0];
        // ONE_BYTE_INTERNALIZED_STRING_TYPE
                            

    2、原始字符串为引用类型表达(如:ConsString)时:

    由于缺少 ThinString 的支持,V8 会利用 one-part ConsString 引用特性来实现隐式就地转换:

  • 在老生代中分配常量字符串 SeqString 实例 #3(b)。
  • 对 ConsString 实例 #0(a)中的 first 与 second 字段重新赋值:
  • first 引用常量字符串 SeqString 实例 #3(b)。
  • second 引用堆内 empty_string 实例。
  • 这样结构的 ConsString 也可被认为是常量化字符串。
  • 但毕竟 ConsString 是用来表达拼接后的字符串,故在新版本(V8>5.8)中引入了 ThinString 类型,专门用于处理类似场景。

    用(JavaScript)伪代码来表达:

    // pseudocode
    var a = "I am" + "superzheng";
    // CONS_ONE_BYTE_STRING_TYPE
    var obj = {};
    obj[a] = true;
    // in-place internalization
    if (FLAG_thin_strings) {
        return a;
        // THIN_ONE_BYTE_STRING_TYPE
    } else {
        return a;
        // CONS_ONE_BYTE_STRING_TYPE
                            

    总结一下:

  • 内容相同的常量字符串具有相同的引用(共享同一块老生代空间),在比较时直接比较引用(指针)是否相等即可,故拥有 O(1) 的比较性能。
  • 将字符串被设置为对象属性名时,会被尝试改造为常量化版本。
  • V8 通过将字符串实例类型转换为 ThinString 并引用常量字符串来实现隐式就地转换。
  • 当缺少 ThinString 支持并且原始字符串又为引用类型表达时,会使用 ConsString(actual, empty_string) 来实现隐式就地转换。
  • 至此,奇技淫巧学 V8 字符串(String)部分全部结束了,章节列表如下:

  • 奇技淫巧学 V8 之六,字符串在 V8 内的表达
  • 奇技淫巧学 V8 之七,字符串的扁平化
  • 奇技淫巧学 V8 之八,常量字符串
  • 奇技淫巧学 V8 对象(JSObject)部分章节:

  • 奇技淫巧学 V8 之一,对象访问模式优化
  • 奇技淫巧学 V8 之二,对象在 V8 内的表达
  • 奇技淫巧学 V8 之三,多态内联缓存 PICs
  • 奇技淫巧学 V8 之四,迁移对象至快速模式
  • 奇技淫巧学 V8 之五,对象属性的快速删除
  • super_zheng Node.js
    私信