字符串的一般封装方式的内存布局 (1): 元数据与字符串内容，整体还是分离？

（Disclaimer：未经许可请勿转载。如需转载请先与我联系。
作者：RednaxelaFX -> rednaxelafx.iteye.com）

字符串的一般封装方式的内存布局系列：
(0): 拿在手上的是什么

1、元数据，字符串内容：整体还是分离？

接上一篇，这次来看看字符串元数据，以及它与字符串内容是整体还是分离式。

字符串常见的元数据都是可选的，例如：
* 指向字符串内容的指针/引用
  如果是整体式就不需要这种信息，而分离式会需要一个指针指向字符串实际内容。
* 字符串长度
  可能是字符个数（如ASCII编码的std::string），code unit个数（如Java、.NET、JavaScript这些要把字符串表现为sequence of UTF-16 code units的），字符串的实际字节数（如BSTR）。各有用途，各有优缺点。
  如果字符串要求以'\0'结尾而且字符串内不允许包含'\0'，那么字符串长度就是可选元数据；否则是必要的。
* 偏移量
  假如某个string类型可以表示别的string的子串并且共享buffer，就可能会记录偏移量。偏移量可以是下标，也可以是指针，取决于系统只允许执行对象头部的指针，还是也允许指向对象内部的指针。
* 字符串哈希值
  纯粹是一种缓存性质的优化，提高string作为哈希容器的键时的性能。
* 字符串编码
  这只存在于允许使用多种编码存放字符内容的字符串实现中，例如Ruby 1.9或更高版本的String类。只能使用固定编码的字符串类型不需要这个信息，因为已经隐含在类型里了，如Java与.NET的内建字符串实现。

既然上述元数据都是可选的，那就可以都不要，做成最“裸”的方式。陈硕大大写的一个可以用在面试题中的C++字符串实现就是这样：只封装了一个char*成员。

假如某个字符串类型带有上述可选元数据，那就有“整体式”和“分离式”的区别。
顾名思义，前者就是元数据与字符串内容粘在一起作为一个整体；后者则是至少有部分元数据与字符串内容分离开，一个“字符串实例”由多个对象组合构成。

“整体式”，例如说32位x86上.NET 4.0的System.String的内存布局是这样的：
"foobar"

28字节:
       System.String (C#视角) / StringObject (C++视角)
    (-4) [ m_SyncBlockValue               ] \ ObjHeader: sync block index
--> (+0) [ m_pMethTab                     ] / Object: MethodTable pointer
    (+4) [ m_stringLength  = 0x00000006   ] // length, in code unit count
    (+8) [ m_firstChar     = 0x0066 ('f') ] // string contents starts here
   (+10) [                   0x006F ('o') ]
   (+12) [                   0x006F ('o') ]
   (+14) [                   0x0062 ('b') ]
   (+16) [                   0x0061 ('a') ]
   (+18) [                   0x0072 ('r') ]
   (+20) [                   0x0000       ] (null-terminate)
   (+22) [ (padding)         0x0000       ]

其中m_SyncBlockValue与m_pMethTab是.NET对象都有的元数据，可以看作对象头先不管；m_stringLength是字符串元数据，而从m_firstChar开始后面就是字符串的实际内容，最后以'\0'结尾，外加由4字节对齐要求而带来的2字节padding。
可以很明显的看到System.String的元数据就这样与实际字符串内容打包成一个整体放在同一个对象内。

“分离式”与之相对。看看64位Oracle JDK7u40/OpenJDK 7u的java.lang.String例子（假定开了压缩指针）：
"foobar"

24字节:
java.lang.String (Java视角) / oopDesc (C++视角)
--> (+0) [ _mark                ]      32字节:
    (+8) [ _metadata            ]      char[] (Java视角) / typeArrayOopDesc (C++视角)
   (+12) [ value                ]   --> (+0) [ _mark                  ]
   (+16) [ hash    = 0x00000000 ]       (+8) [ _metadata              ]
   (+20) [ (padding) 0x00000000 ]      (+12) [ _length = 0x00000006   ]
                                       (+16) [           0x0066 ('f') ]
                                       (+18) [           0x006F ('o') ]
                                       (+20) [           0x006F ('o') ]
                                       (+22) [           0x0062 ('b') ]
                                       (+24) [           0x0061 ('a') ]
                                       (+26) [           0x0072 ('r') ]
                                       (+28) [ (padding) 0x00000000   ]

（在我以前做的一个演示稿里有画得更漂亮的图，请参考）
这里，字符串的元数据部分与实际内容明显被拆分为两块：
* 元数据就两个字段，一个是指向实际内容的value字段，另一个是缓存哈希值的hash字段。都存在固定长度的java.lang.String实例中；
* 实际字符串内存存在另外一个char[]对象里。这个数组对象包含了字符串长度的元数据。

上一篇提到的Ruby 1.8.7的Symbol就更加分离了。不过那也算是个特例。

显然，整体式比分离式更紧凑，占用内存更少且数据局部性高。那为啥要用分离式？
至少有以下几个可能性：

1) 分离式比整体式需要更少的“特殊类型”。

一些基于类的面向对象语言实现，例如Oracle/Sun JDK 6所实现的Java，数组是唯一可变长度的对象类型（注1）。换句话说，只有其它对象只要确定其类型就可以知道对象大小；而数组光确定了类型还不够，需要在数组实例里保存长度信息，结合类型和长度确定对象大小。

在这样的实现里，其它本来语义是可变长度的类型可以依赖数组来实现，就像上面例子中的java.lang.String，它自身的对象大小是固定的，可变长度的部分交由char[]来实现。java.util.ArrayList、HashMap等亦然。
不依赖数组也还可以借助链式结构来实现可变长类型，例如java.util.LinkedList所实现的链表。

用定长对象包装变长的数组，这种组合方式已经能满足许多编程语言对变长对象的实现需求。而且因为它把“可变长度”限定在数组这一种特殊类型里，某些人也认为这样的设计比较“干净。也可以说这样便于偷懒。

即便如C++一样灵活的语言，如果我们只用内建的new运算符来创建对象（不重载new、不用placement new、不定制allocator），那也只有数组是可变长度的，而类的实例大小都跟sizeof运算符在编译期得到的结果一样（注2）。用C++的这个子集来写程序的话，实现变长数据结构也常用数组（或者std::vector<T>，而它里面也依赖了动态分配出来的数组）。
在这个子集外，C++允许定制分配行为，给对象分配出实际比sizeof的值更大的内存空间，这样就可以自制特殊的可变长数据结构。某些人也认为这样的设计比较“不干净”。我是无所谓…

上面展示的CLRv4所实现的System.String类型则必须是数组之外的又一个特殊类型，在VM里必须有专门的支持，跟数组的支持代码类似但又不完全一样所以得多写一份特殊实现。要偷懒就不会选这条路，但要高性能的话反正对string也得做特化实现，做成特殊类型又何妨（看向JVM…）

Java这边也有研究把java.lang.String做成特殊类型的，收益不错。可以参考下面一系列论文：
Automatic Object Inlining in a Java Virtual Machine
Optimized Strings for the Java HotSpot VM
Compact and Efficient Strings for Java
从Oracle JDK7开始反正java.lang.String也抛弃了子串共享，说不定哪天就能用上论文里说的特化实现。JDK9？呵呵。

注1：Oracle JDK7或以上版本里的HotSpot VM里，java.lang.Class实例也变成可变长的类型了。所以上面文字特地限定了版本。
注2：即便C++14草案里的runtime-sized array也不能作为对象实例的成员。

2) 分离式有更高的灵活度

整体式方案通常不会用到“指向字符串内容的指针”这种元数据，而是要求字符串内容必须从字符串对象的某个固定偏移量开始。这样紧凑归紧凑，要做些灵活的变化就困难了。
（注意是“通常”不是“绝对”喔。）

分离式则通常会有“指向字符串内容的指针”的元数据，便于灵活实现一些功能：
* 让外界自由指定字符串实际内容的来源，无论是全局数据区、栈上、堆上。vzch大大的vl::ObjectString<T>就允许这种可能性
* 让多个字符串实例共享一个buffer。这包括子串共享的场景
等等。

评论

4 楼 cajon 2014-08-18  

dogstar 写道

RednaxelaFX 写道

dogstar 写道

下文呢???

抱歉抱歉，搬家忙乱还没来得及把下文整理好

美国生活还好吧.哈哈

去美国了？不错啊！

3 楼 dogstar 2013-12-25  

RednaxelaFX 写道

dogstar 写道

下文呢???

抱歉抱歉，搬家忙乱还没来得及把下文整理好

美国生活还好吧.哈哈

2 楼 RednaxelaFX 2013-12-06  

dogstar 写道

下文呢???

抱歉抱歉，搬家忙乱还没来得及把下文整理好

1 楼 dogstar 2013-12-06  

下文呢???