Hello World
Spiga

串与绳(1):.NET与Java里的String类型

2013-03-12 23:29 by 老赵, 8855 visits

话说“字符串”是我们平时最常用的数据类型之一,它表示一个字符序列。在大部分的语言中,字符串还是一个不可变(Immutable)的数据类型。“不可变”意味着要改变则只能生成新的字符串,无论是连接两个字符串,获取或是替换字符串的一部分,这对于内存和CPU都是不可避免的开销。在一般情况下,只要使用合理这些开销都不会构成大问题。不过对于某些类型的应用,例如我前段时间在工作中涉及到的编辑器(IDE那种),就会带来较多麻烦,于是便用到了一个名为Rope的数据结构。Rope其实是一种很简单,很符合直觉的树状数据结构,也常用于表达一个字符序列,不过更适合需要大量修改的场景。不过,我们还是先来回顾一下.NET与Java中的String类型吧。

.NET中的String类型

.NET中的字符串是个最简单的包含了一个“长度”与“首字母”的结构。

public class String {
    private int m_stringLength;
    private char m_firstChar;
}

严格来说,字符串是一个与运行时紧密结合的“特殊类型”,它的m_firstChar其实只是标记了第一个字符的地址。从源代码中可以看出,String类型的构造函数全是extern方法,它的辅助方法几乎都离不开unsafe代码,例如最简单的字符串连接操作:

internal extern static String FastAllocateString(int length);

internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount) {
    // memory copy...
}

private static unsafe void FillStringChecked(String dest, int destPos, String src) {
    if (src.Length > dest.Length - destPos) {
        throw new IndexOutOfRangeException();
    }

    fixed (char* pDest = &dest.m_firstChar)
    fixed (char* pSrc = &src.m_firstChar) {
        wstrcpy(pDest + destPos, pSrc, src.Length);
    }
}

public static String Concat(String str0, String str1) {
    // return String.Empty if both null or empty

    int str0Length = str0.Length;

    String result = FastAllocateString(str0Length + str1.Length);

    FillStringChecked(result, 0, str0);
    FillStringChecked(result, str0Length, str1);

    return result;
}

wstrcpy做的只是简单的内存复制工作,但它的实现却有将近300行代码。原因在于,假如要获得最好的性能,不同平台(x86/x64/IA64/ARM),当前地址是否对齐,每次复制多少字节等等,都是需要考虑的因素,因此这个方法用到了大量条件编译选项。事实上整个String类型都是这样,对于这种被大量使用的底层类库,.NET内部可谓进行了不遗余力的优化。

还有个例子便是取字符串的Substring方法:

private unsafe string InternalSubString(int startIndex, int length, bool fAlwaysCopy) {
    if (startIndex == 0 && length == this.Length && !fAlwaysCopy) {
        return this;
    }

    String result = FastAllocateString(length);

    fixed (char* dest = &result.m_firstChar)
    fixed (char* src = &this.m_firstChar) {
        wstrcpy(dest, src + startIndex, length);
    }

    return result;
}

从中可以看出,无论是字符串连接还是取部分字符串,CPU和内存的消耗都与目标字符串的长度线性相关。换句话说,字符串越长,代价越高,假如要反复大量地操作一个大型的字符串,则会对性能产生很大影响。

这些应该都是每个.NET程序员都了若指掌的基础。

Java中的String类型

严格来说,“Java”是一个标准,而没有限制特定的实现方式,我们这里分析的是使用最广泛的OpenJDK实现。例如在OpenJDK 7里String类型是这样定义的:

public final class String {
    /** The value is used for character storage. */
    private final char value[];

    /** The offset is the first index of the storage that is used. */
    private final int offset;

    /** The count is the number of characters in the String. */
    private final int count;
}

此外还有一个hash字段,这样单个字符串的哈希值只需计算一次即可。这里我们可以看出OpenJDK 7与.NET的不同,后者是直接包含字符序列的内容,而前者则是保留一个字符数组,并记录起始位置及其偏移量。这么做最大的好处是substring方法无需复制内存,而完全可以重用内部的字符数组:

// Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
    this.value = value;
    this.offset = offset;
    this.count = count;
}

public String substring(int beginIndex, int endIndex) {
    // throw IndexOutOfBoundsException if necessary

    return ((beginIndex == 0) && (endIndex == count)) ? this :
        new String(offset + beginIndex, endIndex - beginIndex, value);
}

String类包含有一个package访问级别的构造函数,用于共享字符数组以提高性能。此外还有一个公有的构造函数:

public String(char value[], int offset, int count) {
    // throw StringIndexOutOfBoundsException if necessary

    this.offset = 0;
    this.count = count;
    this.value = Arrays.copyOfRange(value, offset, offset + count);
}

公有的构造函数会重新复制一份字符数组,这样就杜绝了外部修改的可能性。

共享字符数组的优势显而易见,而劣势便是成为了Java程序中最常见的内存泄露原因之一。说起来我到十八摸以后写的第一个程序便遇到了这个问题:从服务器端得到一个长长的字符串形式的数据,经过一个内部解析类库获得一小个片段(可能只是记录个ID)并保存在内存中。不过后来发现内存的占用量上升的很快,且稳定后比预想地要高的多,通过Memory Profiling发现原来是这一小段字符串还持有原来完整的内容。知道了原因之后自然容易解决,用以下的构造函数重新生成一个新的字符串即可:

public String(String original) {
    int size = original.count;
    char[] originalValue = original.value;
    char[] v;
    if (originalValue.length > size) {
        // The array representing the String is bigger than the new
        // String itself.  Perhaps this constructor is being called
        // in order to trim the baggage, so make a copy of the array.
        int off = original.offset;
        v = Arrays.copyOfRange(originalValue, off, off+size);
    } else {
        // The array representing the String is the same
        // size as the String, so no point in making a copy.
        v = originalValue;
    }
    this.offset = 0;
    this.count = size;
    this.value = v;
}

有意思的是,在未来的OpenJDK 8里,String类的这方面表现已经改变了

public final class String  {
    /** The value is used for character storage. */
    private final char value[];
}

OpenJDK 8放弃了保留了近二十年的设计,让String对象使用各自独立的字符数组,就跟.NET一贯以来的做法一样。这样,它的相关方法如substring也有了相应改变:

public String substring(int beginIndex, int endIndex) {
    // throw StringIndexOutOfBoundsException if necessary

    int subLen = endIndex - beginIndex;
    if (subLen < 0) {
        throw new StringIndexOutOfBoundsException(subLen);
    }
    return ((beginIndex == 0) && (endIndex == value.length)) ? this
            : new String(value, beginIndex, subLen);
}

这里直接调用的已经是之前列举过的,会复制字符数组内容的公有构造函数了。所以说,“Java”只是一个标准,可以有各种实现。从外部表现看来,OpenJDK 8的String类相对于之前没有任何变化。

总结

可以看出,无论是在.NET还是Java中,字符串操作往往都涉及大量的内存复制,而Rope数据结构便是为了规避这一点而设计出来的。正如文章开头所讲的那样,Rope是一种树状的数据结构,同样用于表现一个字符序列。Rope很简单,也很符合直觉,一篇简单的论文即可说清,Wikipedia上也有部分描述。下篇文章里我会简单描述Rope这个数据结构,包括它的特点和常见操作的基本算法等等。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

12 条回复

  1. old
    114.223.69.*
    链接

    old 2013-03-12 23:59:16

    对Rope感兴趣~~~

  2. qzhouayi
    183.63.102.*
    链接

    qzhouayi 2013-03-13 08:51:58

    据我所知,Rope似乎是一种函数式的数据结构

  3. 老赵
    admin
    链接

    老赵 2013-03-13 17:18:19

    @qzhouayi

    可以算是吧,毕竟是种不可变的数据结构。

  4. RednaxelaFX
    61.173.12.*
    链接

    RednaxelaFX 2013-03-14 11:42:38

    老赵应该提一下新的OpenJDK 7里也是去掉了offset和count的。代码应该参考这里

    另外虽然subString的时候变成要复制char[]而不共享内容,但如果有俩String的内容完全相同的话仍然可以共享底下的char[],这点上还是跟.NET有显著差别。哪边好就见仁见智了…

  5. 老赵
    admin
    链接

    老赵 2013-03-14 14:44:57

    @RednaxelaFX

    R大辛苦了……

    不过在OpenJDK 8里面,假如用到那个公开的String构造函数,那么总归会复制字符串的啊。最多substring方法会返回自身罢了,但这点跟.NET还是一样的。

    当然String(String original)这个构造函数的确是不一样的。

  6. 链接

    银河 2013-03-15 08:27:06

    这里我们可以看出OpenJDK 7与.NET的不同,后者是直接包含字符序列的内容,而前者则是保留一个字符数组,并记录启示位置及其偏移量。

    正文这段话中的 启示位置 应该是 起始位置 。

  7. eflylab
    106.187.55.*
    链接

    eflylab 2013-03-15 17:19:14

    说起来我到十八摸以后写的第一个程序便遇到了这个问题...

    老赵在十八模同时兼任DotNET和JAVA二种程序员身份么?

  8. kakaliush
    58.246.240.*
    链接

    kakaliush 2013-03-15 22:42:12

    先mark.再仔细看。

  9. 老赵
    admin
    链接

    老赵 2013-03-16 12:50:08

    @eflylab

    C#最多,Java其次,还兼任bash、cmd、JavaScript脚本的编写工作,此外还有技术支持。总之所有项目里需要的技术都会涉及……

  10. haosdent
    125.88.24.*
    链接

    haosdent 2013-05-13 11:18:02

    老赵为啥再之一上加了条横线呢。

  11. qzhouayi
    116.19.128.*
    链接

    qzhouayi 2014-02-16 17:26:45

    这个系列要太监了吗?

  12. 幻の上帝
    115.238.142.*
    链接

    幻の上帝 2014-06-10 09:13:50

    @qzhouayi

    你大概记错了。Rope应该是boehm提出的部分代替传统string的数据结构。

    早期一个著名实现是SGI STL里的。Boehm GC里也有用。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我