Eclipse 的字符串分区共享优化机制

内容摘要
在 Java/C# 这样基于引用语义处理字符串的语言中，作为不可变对象存在的字符串，如果内容相同，则可以通过某种机制实现重用。
文章正文
在 Java/C# 这样基于引用语义处理字符串的语言中，作为不可变对象存在的字符串，如果内容相同，则可以通过某种机制实现重用。
因为对这类语言来说，指向内存中两块内存位置不同内容相同的字符串，与同时指向一个字符串并没有任何区别。
特别是对大量使用字符串的 XML 文件解析类似场合，这样的优化能够很大程度上降低程序的内存占用，
如 SAX 解析引擎标准中就专门定义了一个 http://xml.org/sax/features/string-interning 特性用于字符串重用。
在语言层面，Java/C# 中都直接提供了 String.Intern 的支持。而对 Java 来说，实现上的非常类似。
由 String.intern 方法，将当前字符串以内容为键，对象引用为值，放入一个全局性的哈希表中。
代码:
//
// java/lang/String.java
//

public final class String
{
　//...
　public native String intern(); // 使用 JNI 函数实现以保障效率
}

//
// hotspot/src/share/vm/prims/jvm.cpp
//

JVM_ENTRY(jstring, JVM_InternString(JNIEnv *env, jstring str))
JVMWrapper("JVM_InternString");
if (str == NULL) return NULL;
　oop string = JNIHandles::resolve_non_null(str); // 将引用解析为内部句柄
　oop result = StringTable::intern(string, CHECK_0); // 进行实际的字符串 intern 操作
　return (jstring) JNIHandles::make_local(env, result); // 获取内部句柄的引用
　JVM_END
　//
　// hotspot/src/share/vm/memory/symbolTable.cpp
　//
　oop StringTable::intern(oop string, TRAPS)
　{
　　if (string == NULL) return NULL;
　　ResourceMark rm(THREAD); // 保护线程资源区域
　　int length;
　　Handle h_string (THREAD, string);
　　jchar* chars = java_lang_String::as_unicode_string(string, length); // 获取实际字符串内容
　　oop result = intern(h_string, chars, length, CHECK_0); // 完成字符串 intern 操作
　　return result;
　}
　oop StringTable::intern(Handle string_or_null, jchar* name, int len, TRAPS)
　{
　　int hashValue = hash_string(name, len); // 首先根据字符串内容计算哈希值
　　stringTableBucket* bucket = bucketFor(hashValue); // 根据哈希值获取目标容器
　　oop string = bucket->lookup(name, len); // 然后检测字符串是否已经存在
　　// Found
　　if (string != NULL) return string;
　　// Otherwise, add to symbol to table
　　return basic_add(string_or_null, name, len, hashValue, CHECK_0); // 将字符串放入哈希表
　}

　　对全局字符串表中的字符串，是没有办法显式手动清除的。只能在不使用此字符串后，由垃圾回收线程在进行不可达对象标记时进行分析，并最终调用 StringTable::unlink 方法去遍历清除。
　　代码：
 
//
// hotspot/src/share/vm/memory/genMarkSweep.cpp
//

void GenMarkSweep::mark_sweep_phase1(...)
{
　//...
　StringTable::unlink();
}

//
// hotspot/src/share/vm/memory/symbolTable.cpp
//

void StringTable::unlink() {
　// Readers of the string table are unlocked, so we should only be
　// removing entries at a safepoint.
　assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint")
　for (stringTableBucket* bucket = firstBucket(); bucket <= lastBucket(); bucket++) {
　　for (stringTableEntry** p = bucket->entry_addr(); *p != NULL;) {
　　　stringTableEntry* entry = *p;
　　　assert(entry->literal_string() != NULL, "just checking");
　　　if (entry->literal_string()->is_gc_marked()) { // 字符串对象是否可达
　　　　// Is this one of calls those necessary only for verification? (DLD)
　　　　entry->oops_do(&MarkSweep::follow_root_closure);
　　　　p = entry->next_addr();
　　　} else { // 如不可达则将其内存块回收到内存池中
　　　　*p = entry->next();
　　　　entry->set_next(free_list);
　　　　free_list = entry;
　　　}
　　}
　}
}

　　通过上面的代码，我们可以直观了解到，对 JVM (Sun JDK 1.4.2) 来说，String.intern 提供的是全局性的基于哈希表的共享支持。这样的实现虽然简单，并能够在最大限度上进行字符串共享;但同时也存在共享粒度太大，优化效果无法度量，大量字符串可能导致全局字符串表性能降低等问题。
　　为此 Eclipse 舍弃了 JVM 一级的字符串共享优化机制，而通过提供细粒度、完全可控、可测量的字符串分区共享优化机制，一定程度上缓解此问题。Eclipse 核心的 IStringPoolParticipant 接口由使用者显式实现，在其 shareStrings 方法中提交需要共享的字符串。
　　代码:
//
// org.eclipse.core.runtime.IStringPoolParticipant
//

public interface IStringPoolParticipant {
　/**
　* Instructs this participant to share its strings in the provided
　* pool.
　*/
　public void shareStrings(StringPool pool);
}

　　例如 MarkerInfo 类型实现了 IStringPoolParticipant 接口，在其 shareStrings 方法中，提交自己需要共享的字符串 type，并通知其下级节点进行相应的提交。

　　代码:
 
//
// org.eclipse.core.internal.resources.MarkerInfo
//

public class MarkerInfo implements ..., IStringPoolParticipant
{
　public void shareStrings(StringPool set) {
　　type = set.add(type);
　　Map map = attributes;
　　if (map instanceof IStringPoolParticipant)
　　((IStringPoolParticipant) map).shareStrings(set);
　}
}

　　这样一来，只要一个对象树各级节点选择性实现 IStringPoolParticipant 接口，就可以一次性将所有需要共享的字符串，通过递归提交到一个字符串缓冲池中进行复用优化。如 Workspace 就是这样一个字符串共享根入口，其 open 方法在完成工作区打开操作后，将需要进行字符串共享优化的缓存管理对象，加入到全局字符串缓冲区分区优化列表中。

　　代码:
 
//
// org.eclipse.core.internal.resources
//

public class Workspace ...
{
　protected SaveManager saveManager;
　public IStatus open(IProgressMonitor monitor) throws CoreException
　{
　　// 打开工作空间
　　// 最终注册一个新的字符串缓冲池分区
　　InternalPlatform.getDefault().addStringPoolParticipant(saveManager, getRoot());
　　return Status.OK_STATUS;
　}
}

 

    对需要优化的类型 SaveManager 来说，只需要实现 IStringPoolParticipant 接口，并在被调用的时候提交自己与子元素的需优化字符串即可。其子元素甚至都不需要实现 IStringPoolParticipant 接口，只需将提交行为一级一级传递下去即可，如:

　　代码:

 
//
// org.eclipse.core.internal.resources.SaveManager
//

public class SaveManager implements ..., IStringPoolParticipant
{
　protected ElementTree lastSnap;
　public void shareStrings(StringPool pool)
　{
　　lastSnap.shareStrings(pool);
　}
}

//
// org.eclipse.core.internal.watson.ElementTree
//
public class ElementTree
{
　protected DeltaDataTree tree;
　public void shareStrings(StringPool set) {
　　tree.storeStrings(set);
　}
}

//
// org.eclipse.core.internal.dtree.DeltaDataTree
//
public class DeltaDataTree extends AbstractDataTree
{
　private AbstractDataTreeNode rootNode;
　private DeltaDataTree parent;
　public void storeStrings(StringPool set) {
　　//copy field to protect against concurrent changes
　　AbstractDataTreeNode root = rootNode;
　　DeltaDataTree dad = parent;
　　if (root != null)
　　　root.storeStrings(set);
　　if (dad != null)
　　　dad.storeStrings(set);
　}
}
//
// org.eclipse.core.internal.dtree.AbstractDataTreeNode
//
public abstract class AbstractDataTreeNode
{
　protected AbstractDataTreeNode children[];
　protected String name;
　public void storeStrings(StringPool set) {
　　name = set.add(name);
　　//copy children pointer in case of concurrent modification
　　AbstractDataTreeNode[] nodes = children;
　　if (nodes != null)
　　　for (int i = nodes.length; --i >= 0;)
　　　　nodes[i].storeStrings(set);
　}
}

　　所有的需优化字符串，都会通过 StringPool.add 方法提交到统一的字符串缓冲池中。而这个缓冲池的左右，与 JVM 级的字符串表略有不同，它只是在进行字符串缓冲分区优化时，起到一个阶段性的整理作用，本身并不作为字符串引用的入口存在。因此在实现上它只是简单的对 HashMap 进行包装，并粗略计算优化能带来的额外空间，以提供优化效果的度量标准。

　　代码:
 
//
// org.eclipse.core.runtime.StringPool
//

public final class StringPool {
　private int savings;
　private final HashMap map = new HashMap();
　public StringPool() {
　　super();
　}
　public String add(String string) {
　　if (string == null)
　　　return string;
　　Object result = map.get(string);
　　if (result != null) {
　　　if (result != string)
　　　　savings += 44 + 2 * string.length();
　　　return (String) result;
　　}
　　map.put(string, string);
　　return string;
　}
　// 获取优化能节省多少空间的大致估算值
　public int getSavedStringCount() {
　　return savings;
　}
}

　　不过这里的估算值在某些情况下可能并不准确，例如缓冲池中包括字符串 S1，此时提交一个与之内容相同但物理位置不同的字符串 S2，则如果 S2 被提交多次，会导致错误的高估优化效果。当然如果需要得到精确值，也可以对其进行重构，通过一个 Set 跟踪每个字符串优化的过程，获得精确优化度量，但需要损失一定效率。

　　在了解了需优化字符串的提交流程，以及字符串提交后的优化流程后，我们接着看看 Eclipse 核心是如何将这两者整合到一起的。

　　前面提到 Workspace.open 方法会调用 InternalPlatform.addStringPoolParticipant 方法，将一个字符串缓冲池分区的根节点，添加到全局性的优化任务队列中。

　　代码:
 
//
// org.eclipse.core.internal.runtime.InternalPlatform
//

public final class InternalPlatform {
　private StringPoolJob stringPoolJob;
　public void addStringPoolParticipant(IStringPoolParticipant participant, ISchedulingRule rule) {
　if (stringPoolJob == null)
　　stringPoolJob = new StringPoolJob(); // Singleton 模式
　　stringPoolJob.addStringPoolParticipant(participant, rule);
　}
}

//
// org.eclipse.core.internal.runtime.StringPoolJob
//

public class StringPoolJob extends Job
{
　private static final long INITIAL_DELAY = 10000;//five seconds
　private Map participants = Collections.synchronizedMap(new HashMap(10));
　public void addStringPoolParticipant(IStringPoolParticipant participant, ISchedulingRule rule) {
　participants.put(participant, rule);
　if (sleep())
　　wakeUp(INITIAL_DELAY);
　}
　public void removeStringPoolParticipant(IStringPoolParticipant participant) {
　　participants.remove(participant);
　}
}

　　此任务将在合适的时候，为每个注册的分区进行共享优化。

　　StringPoolJob 类型是分区任务的代码所在，其底层实现是通过 Eclipse 的任务调度机制。关于 Eclipse 的任务调度，有兴趣的朋友可以参考 Michael Valenta (IBM) 的 On the Job: The Eclipse Jobs API 一文。

　　这里需要了解的是 Job 在 Eclipse 里，被作为一个异步后台任务进行调度，在时间或资源就绪的情况下，通过调用其 Job.run 方法执行。可以说 Job 非常类似一个线程，只不过是基于条件进行调度，可通过后台线程池进行优化罢了。而这里任务被调度的条件，一方面是任务自身的调度时间因素，另一方面是通过 ISchedulingRule 接口提供的任务资源依赖关系。如果一个任务与当前正在运行的任务传统，则将被挂起直到冲突被缓解。而 ISchedulingRule 接口本身可以通过 composite 模式进行组合，描述复杂的任务依赖关系。

　　在具体完成任务的 StringPoolJob.run 方法中，将对所有字符串缓冲分区的调度条件进行合并，以便在条件允许的情况下，调用 StringPoolJob.shareStrings 方法完成实际工作。

　　代码:
 
//
// org.eclipse.core.internal.runtime.StringPoolJob
//

public class StringPoolJob extends Job
{
　private static final long RESCHEDULE_DELAY = 300000;//five minutes
　protected IStatus run(IProgressMonitor monitor)
　{
　　//copy current participants to handle concurrent additions and removals to map
　　Map.Entry[] entries = (Map.Entry[]) participants.entrySet().toArray(new Map.Entry[0]);
　　ISchedulingRule[] rules = new ISchedulingRule[entries.length];
　　IStringPoolParticipant[] toRun = new IStringPoolParticipant[entries.length];
　　for (int i = 0; i < toRun.length; i++) {
　　　toRun[i] = (IStringPoolParticipant) entries[i].getKey();
　　　rules[i] = (ISchedulingRule) entries[i].getValue();
　　}
　　// 将所有字符串缓冲分区的调度条件进行合并
　　final ISchedulingRule rule = MultiRule.combine(rules);
　　// 在调度条件允许的情况下调用 shareStrings 方法执行优化
　　try {
　　　Platform.getJobManager().beginRule(rule, monitor); // 阻塞直至调度条件允许
　　　shareStrings(toRun, monitor);
　　} finally {
　　　Platform.getJobManager().endRule(rule);
　　}
　　// 重新调度任务自己，以便进行下一次优化
　　long scheduleDelay = Math.max(RESCHEDULE_DELAY, lastDuration*100);
　　schedule(scheduleDelay);
　　return Status.OK_STATUS;
　}
}


　　StringPoolJob.shareStrings 方法只是简单的遍历所有分区，调用其根节点的 IStringPoolParticipant.shareStrings 方法，进行前面所述的优化工作，并最终返回分区的优化效果。而缓冲池本身，只是作为一个优化工具，完成后直接被放弃。

　　代码:
 
private int shareStrings(IStringPoolParticipant[] toRun, IProgressMonitor monitor) {
　final StringPool pool = new StringPool();
　for (int i = 0; i < toRun.length; i++) {
　　if (monitor.isCanceled()) // 操作是否被取消
　　　break;
　　final IStringPoolParticipant current = toRun[i];
　　Platform.run(new ISafeRunnable() { // 安全执行
　　　public void handleException(Throwable exception) {
　　　　//exceptions are already logged, so nothing to do
　　　}
　　　public void run() {
　　　　current.shareStrings(pool); // 进行字符串重用优化
　　　}
　　});
　}
　return pool.getSavedStringCount(); // 返回优化效果
}
}

　　通过上面的分析我们可以看到，Eclipse 实现的基于字符串缓冲分区的优化机制，相对于 JVM 的 String.intern() 来说:

　　1.控制的粒度更细，可以指定要对哪些对象进行优化;

　　2.优化效果可度量，可以大概估算出优化能节省的空间;

　　3.不存在性能瓶颈，不存在集中的字符串缓冲池，因此不会因为大量字符串导致性能波动;

　　4.不会长期占内存，缓冲池只在优化执行时存在，完成后中间结果被抛弃;

　　5.优化策略可选择，通过定义调度条件，可选择性执行不同的优化策略.
代码注释
上一篇JavaScript 调用C#变量实例下一篇JavaScript 的保留关键字

作者：喵哥笔记

IDC笔记

学的不仅是技术，更是梦想！