探索 StringTable 提升 YGC 性能
很久很久以前看过笨神的一篇文章 JVM 源码分析之 String.intern()导致的 YGC 不断变长，其原因是 YGC 过程需要对 StringTable 做扫描，而 String.intern()就是在 StringTable 中保存这个对象的引用，如果 String.intern()添加越来越多不同的对象，那么 StringTable 就越大，扫描 StringTable 的时间就越长，从而导致 YGC 耗时越长；那么如何确定 YGC 耗时越来越长是 StringTable 变大引起的呢？
介绍一个参数-XX:+PrintStringTableStatistics，看名字就知道这个参数的作用了：打印出 StringTable 的统计信息；再详细一点描述：在JVM进程退出时，打印出 StringTable 的统计信息到标准日志输出目录中。
JDK 版本要求：JDK 7u6 +
验证问题
验证代码如下：
import java.util.UUID;
/**
* @author afei
* @version 1.0.0
* @since 2017 年 08 月 16 日
*/
public class StringInternTest {
public static void main(String[] args) throws Exception {
for (int i=0; i<Integer.MAX_VALUE; i++){
UUID.randomUUID().toString().intern();
if (i>=100000 && i%100000==0){
System.out.println(“i=”+i);
}
}
}
}
执行命令：java -verbose:gc -XX:+PrintGC -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSInitiatingOccupancyOnly -XX:+PrintStringTableStatistics -Xmx1g -Xms1g -Xmn64m StringInternTest
从 gc 日志可以看出 YGC 时间越来越长：
[GC (Allocation Failure) 52480K->5691K(1042048K), 0.0109821 secs]
i=100000
[GC (Allocation Failure) 65261K->19731K(1042048K), 0.0233471 secs]
i=200000
[GC (Allocation Failure) 72211K->26796K(1042048K), 0.0266068 secs]
i=300000
[GC (Allocation Failure) 79276K->33860K(1042048K), 0.0262006 secs]
[GC (Allocation Failure) 86340K->40924K(1042048K), 0.0295842 secs]
… …
[GC (Allocation Failure) 192868K->147456K(1042048K), 0.0661785 secs]
i=1400000
[GC (Allocation Failure) 199936K->154521K(1042048K), 0.0685919 secs]
[GC (Allocation Failure) 207001K->161585K(1042048K), 0.0707886 secs]
i=1500000
[GC (Allocation Failure) 214065K->168649K(1042048K), 0.0744149 secs]
[GC (Allocation Failure) 221129K->175714K(1042048K), 0.0766862 secs]
i=1600000
[GC (Allocation Failure) 228194K->182778K(1042048K), 0.0802783 secs]
250w 个 String 对象
当 i=2500000，即往 StringTable 添加了 250w 个引用时，kill 调这个进程，能够看到PrintStringTableStatistics这个参数作用下输出的 StringTable 相关信息（输出信息中还有 SymbolTable ，这篇文章不做讨论）：
StringTable statistics:
Number of buckets : 60013 = 480104 bytes, avg 8.000
Number of entries : 2568786 = 61650864 bytes, avg 24.000
Number of literals : 2568786 = 287662080 bytes, avg 111.984
Total footprint : = 349793048 bytes
Average bucket size : 42.804
Variance of bucket size : 43.104
Std. dev. of bucket size: 6.565
Maximum bucket size : 82
且这时候的 YGC 时间达到了 0.12s：
i=2500000
[GC (Allocation Failure) 320041K->274625K(1042048K), 0.1268211 secs]
[GC (Allocation Failure) 327105K->281693K(1042048K), 0.1236515 secs]
500w 个 String 对象
当 i=5000000，即往 StringTable 添加了 500w 个引用时，kill 调这个进程，输出结果如下：
StringTable statistics:
Number of buckets : 60013 = 480104 bytes, avg 8.000
Number of entries : 5082093 = 121970232 bytes, avg 24.000
Number of literals : 5082093 = 569152512 bytes, avg 111.992
Total footprint : = 691602848 bytes
Average bucket size : 84.683
Variance of bucket size : 85.084
Std. dev. of bucket size: 9.224
Maximum bucket size : 123
YGC 时间达到了 0.24s：
i=5000000
[GC (Allocation Failure) 595600K->550184K(1042048K), 0.2425553 secs]
PrintStringTableStatistics 结果解读
从 PrintStringTableStatistics 输出信息可以看出 StringTable 的 bucket 数量默认为 60013 ，且每个 bucket 占用 8 个字节（说明：如果是 32 位系统，那么每个 bucket 占用 4 个字节）；Number of entries 即 Hashtable 的 entry 数量为 2568786，因为我们 String.intern( )了 250w 个不同的 String 对象；Average bucket size表示表示 bucket 中 LinkedList 的平均 size，Maximum bucket size 表示 bucket 中 LinkedList 最大的 size，Average bucket size 越大，说明 Hashtable 碰撞越严重，由于 bucket 数量固定为 60013，随着 StringTable 添加的引用越来越多，碰撞越来越严重，YGC 时间越来越长。
250w 个 String 对象&-XX:StringTableSize=2500000
执行命令：java -verbose:gc -XX:+PrintGC -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSInitiatingOccupancyOnly -XX:+PrintStringTableStatistics -Xmx1g -Xms1g -Xmn64m -XX:StringTableSize=2500000 StringInternTest
当 i=2500000，kill 调这个进程，输出结果如下：
StringTable statistics:
Number of buckets : 2500000 = 20000000 bytes, avg 8.000
Number of entries : 2573556 = 61765344 bytes, avg 24.000
Number of literals : 2573556 = 288196288 bytes, avg 111.984
Total footprint : = 369961632 bytes
Average bucket size : 1.029
Variance of bucket size : 1.028
Std. dev. of bucket size: 1.014
Maximum bucket size : 10
YGC 时间从 0.12s 下降到了 0.09s：
i=2500000
[GC (Allocation Failure) 320216K->274800K(1042048K), 0.0890073 secs]
[GC (Allocation Failure) 327280K->281865K(1042048K), 0.0926348 secs]
500w 个 String 对象&-XX:StringTableSize=5000000
执行命令：java -verbose:gc -XX:+PrintGC -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:CMSInitiatingOccupancyFraction=75 -XX:+UseCMSInitiatingOccupancyOnly -XX:+PrintStringTableStatistics -Xmx1g -Xms1g -Xmn64m -XX:StringTableSize=5000000 StringInternTest
当 i=5000000，即往 StringTable 添加了 500w 个引用时，kill 调这个进程，输出结果如下：
StringTable statistics:
Number of buckets : 5000000 = 40000000 bytes, avg 8.000
Number of entries : 5151776 = 123642624 bytes, avg 24.000
Number of literals : 5151776 = 576957008 bytes, avg 111.992
Total footprint : = 740599632 bytes
Average bucket size : 1.030
Variance of bucket size : 1.030
Std. dev. of bucket size: 1.015
Maximum bucket size : 9
YGC 时间从 0.24s 降到了 0.17s：
i=5000000
[GC (Allocation Failure) 595645K->550229K(1042048K), 0.1685862 secs]
[GC (Allocation Failure) 602709K->557293K(1042048K), 0.1706642 secs]
PrintStringTableStatistics&StringTableSize 结果解读
设置 StringTableSize 一个合适的值，即 bucket 数量为期望的数量后，碰撞的概率明显降低，由Average bucket size和Maximum bucket size的值明显小于未配置 StringTableSize 参数时的值可知，且 YGC 时间也明显降低。另外, 最好通过 BTrace 分析是哪里频繁调用 String.intern(), 确实 String.intern()没有滥用的前提下, 再增大 StringTableSize 的值。
| 统计 | 250w | 500w | 250w&Size=250w | 500w&Size=500w |
| elapse(ms) | 120 | 240 | 90 | 170 |
引申问题
既然 StringTable 是 Hashtable 数据结构，那为什么不能自己通过 rehash 扩大 bucket 数量来提高性能呢？JVM 中 StringTable 的 rehash 有点不一样, JVM中 StringTable 的 rehash 不会扩大 bucket 数量，而是在 bucket 不变的前提下，通过一个新的 seed 尝试摊平每个 bucket 中 LinkedList 的长度（想想也是，如果 StringTable 能通过 rehash 扩大 bucket 数量，那还要 StringTableSize 干嘛），rehash 大概是一个如下图所示的过程，rehash 前后 bucket 数量不变，这是重点：
假设 reash 前数据分布（23,4,8,2,1,5）：
StringTable rehash 前.png
reash 后可能数据分布（6,8,8,9,5,7）：
StringTable rehash 后.png
对应的源码在 hashtable.cpp 中–第一行代码就是初始化一个新的_seed用于后面的 hash 值计算：
// Create a new table and using alternate hash code, populate the new table
// with the existing elements. This can be used to change the hash code
// and could in the future change the size of the table.
template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) {
// Initialize the global seed for hashing.
_seed = AltHashing::compute_seed();
assert(seed() != 0, “shouldn’t be zero”);
int saved_entry_count = this->number_of_entries();
// Iterate through the table and create a new entry for the new table
for (int i = 0; i < new_table->table_size(); ++i) {
for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) {
HashtableEntry<T, F>* next = p->next();
T string = p->literal();
// Use alternate hashing algorithm on the symbol in the first table
unsigned int hashValue = string->new_hash(seed());
// Get a new index relative to the new table (can also change size)
int index = new_table->hash_to_index(hashValue);
p->set_hash(hashValue);
// Keep the shared bit in the Hashtable entry to indicate that this entry
// can’t be deleted. The shared bit is the LSB in the _next field so
// walking the hashtable past these entries requires
// BasicHashtableEntry::make_ptr() call.
bool keep_shared = p->is_shared();
this->unlink_entry(p);
new_table->add_entry(index, p);
if (keep_shared) {
p->set_shared();
}
p = next;
}
}
// give the new table the free list as well
new_table->copy_freelist(this);
assert(new_table->number_of_entries() == saved_entry_count, “lost entry on dictionary copy?”);
// Destroy memory used by the buckets in the hashtable. The memory
// for the elements has been used in a new table and is not
// destroyed. The memory reuse will benefit resizing the SystemDictionary
// to avoid a memory allocation spike at safepoint.
BasicHashtable<F>::free_buckets();
}
结论
YGC 耗时的问题确实比较难排查，遍历 StringTable 只是其中一部分，通过 PrintStringTableStatistics 参数可以了解我们应用的 StringTable 相关统计信息，且可以通过设置合理的 StringTableSize 值降低碰撞从而减少 YGC 时间。另一方面，增大 StringTableSize 的值有什么影响呢？需要多消耗一点内存，因为每一个 bucket 需要 8 个 byte（64 位系统）。与它带来的 YGC 性能提升相比，这点内存消耗还是非常值得的。然而 StringTable 的统计信息需要在 JVM 退出时才输出，不得不说是一个遗憾，哎！
思考
通过设置 StringTableSize 为一个合理的值后，YGC 时扫描的 StringTable 里的 entry 是一样大的。假设 StringTable 里有 20 个 entry，没有设置 StringTableSize，那么可能 hash 数组只有 5 个长度，平均每个数组里的冲突链表有 4 个长度。而设置 StringTableSize 为 20 后，hash 数组有 20 个长度，且几乎没有 hash 冲突。设置前后差别仅此而已，但是为什么 YGC 速度快了不少？思考一下，下文解密！
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接：探索 StringTable 提升 YGC 性能
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接：探索 StringTable 提升 YGC 性能
