`
RednaxelaFX
  • 浏览: 3047767 次
  • 性别: Icon_minigender_1
  • 来自: 海外
社区版块
存档分类
最新评论

字符串的一般封装方式的内存布局 (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  
下文呢???

相关推荐

    professional Cpp

    #### 第18章:字符串本地化与正则表达式 - **字符集支持**:介绍C++对不同字符集的支持。 - **国际化与本地化**:如何使程序适应不同的语言环境。 - **正则表达式**:深入讲解正则表达式的使用方法。 #### 第19章:...

    毕向东 java、html、css、JavaScript讲解视频

    - **变量与数据类型**:支持字符串、数字、布尔值等多种数据类型。 - **函数**:用于组织一段可重用的代码块。 - **对象与数组**:JavaScript 中的核心数据结构。 - **事件处理**:监听并响应用户的动作,如点击按钮...

    Android 应用程序框架

    - **Resources**: 包含应用的非代码资源,如字符串、图片、布局等,支持国际化和动态配置。 **MVC的优点:** 1. 结构清晰:明确分离了数据、展示和控制,易于理解和维护。 2. 可重用性:视图和模型可以独立开发和...

    ffmpeg媒体播放器

    - `res`: 应用的资源文件,如布局、图片、字符串等。 - `assets`: 存放应用的原始数据文件,通常用于存放非资源文件,如配置文件或大文本数据。 - `gen`: 自动生成的Java源代码目录,通常由AIDL或R文件生成。 5....

    疯狂JAVA讲义源码(全)

    - DAO设计模式:应用数据访问对象(DAO)模式,分离业务逻辑与数据访问。 8. **Swing图形界面** - 创建组件:了解各种Swing组件,如JButton、JLabel、JTextArea等,以及布局管理器。 - 事件处理:学习监听器...

    前端笔试面试题目总结.docx编程资料

    #### 字符串与数组的常用方法 - **字符串方法**:`charAt()`、`indexOf()`、`slice()`、`split()`、`replace()` 等。 - **数组方法**:`push()`、`pop()`、`shift()`、`unshift()`、`concat()`、`slice()`、`splice...

    JSP 技术大全(PDG)

    1. **分离关注点**:将业务逻辑移到JavaBeans或Servlet,保持JSP页面简洁。 2. **使用EL和JSTL**:减少脚本元素,提高可读性和维护性。 3. **利用自定义标签库**:封装复杂逻辑,增强代码复用。 **七、JSP的优缺点*...

    在android中使用XML的技巧

    这是每个Android应用的核心配置文件,包含了应用的元数据,如应用的组件(Activity、Service等)、权限声明、依赖库等。 总之,XML在Android开发中扮演着重要角色,无论是数据交换、用户界面设计还是资源管理,都...

    Android源码解析

    - Java注解是代码元数据的一种形式,可以用于为工具或编译器提供额外的信息。 - **应用场景**:代码生成、验证、日志记录等。 - **Java动态代理** - 动态代理是在运行时动态创建代理对象的技术。 - **应用场景**...

    JavaScript+css+html

    比如,`&lt;head&gt;`部分用于设置页面元数据,`&lt;body&gt;`包含可见内容,如`&lt;h1&gt;`标题、`&lt;p&gt;`段落、`&lt;img&gt;`图像和`&lt;a&gt;`链接等。HTML5引入了许多新特性,如离线存储、拖放功能、媒体元素等,增强了网页的功能性和互动性。 ...

    VC++实例.pdf

    - **字符串类:** 提供了字符串操作的方法。 **10.5 日期和时间类** - **日期时间类:** 提供了日期和时间的操作。 #### 十一、异常处理和诊断 **11.1 处理 C++ 异常** - **异常处理:** 使用 try-catch 语句...

    java教程我们上课用的

    - **TLD**:描述标签库元数据的XML文件。 - **标签处理器**:处理标签逻辑的Java类。 - **4.3.6 JSTL标签库** - **Core**:提供常用标签如`c:if`, `c:forEach`等。 - **SQL**:用于执行SQL语句。 - **XML**:...

    goreit:GoreIT - 公司网站

    2. 面向对象:Ruby是纯面向对象的语言,所有数据类型都是对象,包括基本类型如整数、字符串和布尔值。 3. 动态性:Ruby支持动态类型,变量的类型在运行时确定,增强了代码的灵活性。 4. 自动内存管理:Ruby使用垃圾...

    DesignPatternsForQT( C++ 设计模式 )

    QT的`QString`和`QByteArray`类通过内部共享机制实现了字符串和字节数组的高效存储。 13. **责任链模式(Chain of Responsibility)**:避免将请求的发送者与接收者耦合在一起,让多个对象都有可能处理请求。QT的...

    cars:列出和预订汽车的应用程序

    2. **res**: 包含应用程序的资源文件,如XML布局文件、图片、字符串等。 3. **AndroidManifest.xml**: 应用程序的配置文件,定义了应用的组件、权限和其他元数据。 4. **build.gradle**: 项目构建配置,用于指定依赖...

    TP3_PG

    2. **资源管理**:包括UI元素(如布局、图标)和其他资源(字符串、颜色、尺寸),这些都可以在代码中通过R类引用。 3. **Activity和Fragment**:Activity是用户界面的基本单元,而Fragment可以在多个Activity之间...

    cs454-hw1:适用于 Android 的计算器应用程序

    2. **res** 目录 - 包含应用的资源,如布局文件(layout)、图像资源(drawable)、字符串资源(values)等。 3. **src** 目录 - 存放应用的Java源代码。主活动(MainActivity.java)会在这里,它负责处理用户交互和...

    LifeRale.h6dcfjjwzc.gam0Jk5

    很抱歉,根据您提供的信息,"LifeRale.h6dcfjjwzc.gam0Jk5"看起来像是一个特定的文件名或者可能是某种加密或混淆的字符串,并非一个标准的IT技术术语或知识点。同时,描述部分同样只重复了这个文件名,没有提供额外...

    elielvillegas.github.io

    - ES6及以上的新特性,如let/const、模板字符串、箭头函数、Promise等。 - 轻量级库或框架的应用,如jQuery,简化DOM操作和动画效果。 - 软件工程实践,如模块化(import/export)、封装和面向对象编程。 综上所述...

Global site tag (gtag.js) - Google Analytics