- 浏览: 3013776 次
- 性别:
- 来自: 海外
文章分类
- 全部博客 (430)
- Programming Languages (23)
- Compiler (20)
- Virtual Machine (57)
- Garbage Collection (4)
- HotSpot VM (26)
- Mono (2)
- SSCLI Rotor (1)
- Harmony (0)
- DLR (19)
- Ruby (28)
- C# (38)
- F# (3)
- Haskell (0)
- Scheme (1)
- Regular Expression (5)
- Python (4)
- ECMAScript (2)
- JavaScript (18)
- ActionScript (7)
- Squirrel (2)
- C (6)
- C++ (10)
- D (2)
- .NET (13)
- Java (86)
- Scala (1)
- Groovy (3)
- Optimization (6)
- Data Structure and Algorithm (3)
- Books (4)
- WPF (1)
- Game Engines (7)
- 吉里吉里 (12)
- UML (1)
- Reverse Engineering (11)
- NSIS (4)
- Utilities (3)
- Design Patterns (1)
- Visual Studio (9)
- Windows 7 (3)
- x86 Assembler (1)
- Android (2)
- School Assignment / Test (6)
- Anti-virus (1)
- REST (1)
- Profiling (1)
- misc (39)
- NetOA (12)
- rant (6)
- anime (5)
- Links (12)
- CLR (7)
- GC (1)
- OpenJDK (2)
- JVM (4)
- KVM (0)
- Rhino (1)
- LINQ (2)
- JScript (0)
- Nashorn (0)
- Dalvik (1)
- DTrace (0)
- LLVM (0)
- MSIL (0)
最新评论
-
mldxs:
虽然很多还是看不懂,写的很好!
虚拟机随谈(一):解释器,树遍历解释器,基于栈与基于寄存器,大杂烩 -
HanyuKing:
Java的多维数组 -
funnyone:
Java 8的default method与method resolution -
ljs_nogard:
Xamarin workbook - .Net Core 中不 ...
LINQ的恶搞…… -
txm119161336:
allocatestlye1 顺序为 // Fields o ...
最近做的两次Java/JVM分享的概要
字符串的一般封装方式的内存布局 (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"
其中m_SyncBlockValue与m_pMethTab是.NET对象都有的元数据,可以看作对象头先不管;m_stringLength是字符串元数据,而从m_firstChar开始后面就是字符串的实际内容,最后以'\0'结尾,外加由4字节对齐要求而带来的2字节padding。
可以很明显的看到System.String的元数据就这样与实际字符串内容打包成一个整体放在同一个对象内。
“分离式”与之相对。看看64位Oracle JDK7u40/OpenJDK 7u的java.lang.String例子(假定开了压缩指针):
"foobar"
(在我以前做的一个演示稿里有画得更漂亮的图,请参考)
这里,字符串的元数据部分与实际内容明显被拆分为两块:
* 元数据就两个字段,一个是指向实际内容的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。这包括子串共享的场景
等等。
抱歉抱歉,搬家忙乱还没来得及把下文整理好
美国生活还好吧.哈哈
去美国了?不错啊!
抱歉抱歉,搬家忙乱还没来得及把下文整理好
美国生活还好吧.哈哈
抱歉抱歉,搬家忙乱还没来得及把下文整理好
作者: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
下文呢???
发表评论
-
The Prehistory of Java, HotSpot and Train
2014-06-02 08:18 0http://cs.gmu.edu/cne/itcore/vi ... -
MSJVM and Sun 1.0.x/1.1.x
2014-05-20 18:50 0当年的survey paper: http://www.sym ... -
Sun JDK1.4.2_28有TieredCompilation
2014-05-12 08:48 0原来以前Sun的JDK 1.4.2 update 28就已经有 ... -
IBM JVM notes (2014 ver)
2014-05-11 07:16 0Sovereign JIT http://publib.bou ... -
class data sharing by Apple
2014-03-28 05:17 0class data sharing is implement ... -
Java 8与静态工具类
2014-03-19 08:43 16125以前要在Java里实现所谓“静态工具类”(static uti ... -
Java 8的default method与method resolution
2014-03-19 02:23 10324先看看下面这个代码例子, interface IFoo { ... -
HotSpot Server VM与Server Class Machine
2014-02-18 13:21 0HotSpot VM历来有Client VM与Server V ... -
Java 8的lambda表达式在OpenJDK8中的实现
2014-02-04 12:08 0三月份JDK8就要发布首发了,现在JDK8 release c ... -
GC stack map与deopt stack map的异同
2014-01-08 09:56 0两者之间不并存在包含关系。它们有交集,但也各自有特别的地方。 ... -
HotSpot Server Compiler与data-flow analysis
2014-01-07 17:41 0http://en.wikipedia.org/wiki/Da ... -
基于LLVM实现VM的JIT的一些痛点
2014-01-07 17:25 0同事Philip Reames Sanjoy Das http ... -
tailcall notes
2013-12-27 07:42 0http://blogs.msdn.com/b/clrcode ... -
《自制编程语言》的一些笔记
2013-11-24 00:20 0http://kmaebashi.com/programmer ... -
字符串的一般封装方式的内存布局 (0): 拿在手上的是什么
2013-11-04 18:22 21363(Disclaimer:未经许可请 ... -
字符串的一般封装方式的内存布局
2013-11-01 12:55 0(Disclaimer:未经许可请 ... -
关于string,内存布局,C++ std::string,CoW
2013-10-30 20:45 0(Disclaimer:未经许可请 ... -
对C语义的for循环的基本代码生成模式
2013-10-19 23:12 21729之前有同学在做龙书(第二版)题目,做到8.4的练习,跟我对答案 ... -
Function.prototype.bind
2013-09-24 18:07 0polyfill http://stackoverflow. ... -
Java的instanceof是如何实现的
2013-09-22 16:57 0Java语言规范,Java SE 7版 http://docs ...
相关推荐
自己封装的一些简单函数呵呵呵,主要是关于字符串的,自己用的!
字符串比较、求串的长度、判断串是否为空、将串置空、字符串赋值(包括两个字符串类复制,一个字符串赋值到CmyString对象)、求字符串中的一个字符或改变字符串中的一个字符(采用重载[]),完成串的赋值与合并...
字符串比较、求串的长度、判断串是否为空、将串置空、字符串赋值(包括两个字符串类复制,一个字符串赋值到CmyString对象)、求字符串中的一个字符或改变字符串中的一个字符(采用重载[]),完成串的赋值与合并...
1:输出字符串长度 2:输出字符串中第一个出现字母a的位置 3:在字符串的第3个字符后面插入字符串“hello”,输出新字符串. 4:将字符串“hello”替换为“me”,输出新的字符串 5:以字符"m"为分隔符,将字符串分离,...
完成了字符串的封装,基本实现了字符串库函数处理的功能。
#c语言#的问题:输出格式输出提取出来的数字字符串,每个连续数字字符串占一行(相关搜索:字符串长度|输入字符串 #c语言#的问题:输出格式输出提取出来的数字字符串,每个连续数字字符串占一行(相关搜索:字符串...
算法训练 比较字符串 时间限制:1.0s 内存限制:512.0MB 编程实现两个字符串s1和s2的字典序比较。若它们不相等,则指出其第一个不同字
主要是获取关于字符串内部带有刮号()的字符内容,所以就简单的封装了下相关方法,该方法适合匹配以下几个符号:() 、[] 、<> 、《》、 “”、 ‘’、〔〕、{}、「」、〖〗等相关带有闭合的符号。 该函数strIn()...
Delphi 7.0 提取字符串中指定子字符串后的字符串,这个平时在字符处理时候使用几率也挺高的,获取指定字符串后面的字符串,比如获取扩展名等也可以用此方法,本例中要用到After函数,测试时,当单击按钮时,执行以下...
详解C++中十六进制字符串转数字(数值) 主要有两个方法,其实都是对现有函数的使用: 方法1: sscanf() 函数名: sscanf 功 能: 从字符串格式化输入 用 法: int sscanf(char *string, char *format[,...
通过键盘输入一串小写字母(a~z)组成的字符串,将字符串中连续出席的重复字母进行压缩,并输出压缩后的字符串。 压缩字段的格式为"字符重复的次数+字符"。例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。 要求实现...
主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页,当前为第3页。 字符串循环左移 4/88 给定...
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
代码在Android Studio编写,java可以通用,其他语言也可以参考。主要用途是分离一个长的字符串来单独显示
C++字符串完全指南—第二部分字符串的封装类.docx
string常用截取字符串方法有很多,但是配合使用以下两种,基本都能满足要求: find(string strSub, npos); ...例1:直接查找字符串中是否具有某个字符串(返回”2″) std::string strPath = E:\\
字符串提取(获取两个字符串中间的字符串) http://blog.csdn.net/isaced/archive/2011/01/24/6161259.aspx
C#字符串删除指定字符串|C#字符串删除子字符串
字符串类的封装,以前做的课程设计作业
1138:将字符串中的小写字母转换成大写字母 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 54809 通过数: 25241 【题目描述】 给定一个字符串,将其中所有的小写字母转换成大写字母。 【输入】 输入一行,包含一...