基准测试
　　为了测试 distance() 方法的性能，需要做基准测试。Java中微基准测试很难保证准确，但幸好OpenJDK提供了JMH（Java Microbenchmark Harness），它可以帮我们解决大部分难题。如果感兴趣的话，推荐大家阅读文档和实例；它会很吸引你。以下是基准测试：
　　@State(Scope.Benchmark)
　　public class MyBenchmark {
　　private Levenshtein lev = new Levenshtein<>(StringAsList::new);
　　@Benchmark
　　@BenchmarkMode(Mode.AverageTime)
　　@OutputTimeUnit(TimeUnit.NANOSECONDS)
　　public int timeLevenshtein() {
　　return lev.distance("autoboxing is fast"， "autoboxing is slow");
　　}
　　}
　　（返回方法的结果，这样JMH可以做一些操作让系统认为返回值会被使用到，防止冗余代码消除影响了结果。）
　　以下是结果：
$ java -jar target/benchmarks.jar -f 1 -wi 8 -i 8
# JMH 1.10.2 (released 3 days ago)
# VM invoker: /usr/lib/jvm/java-8-openjdk/jre/bin/java
# VM options:
# Warmup: 8 iterations， 1 s each
# Measurement: 8 iterations， 1 s each
# Timeout: 10 min per iteration
# Threads: 1 thread， will synchronize iterations
# Benchmark mode: Average time， time/op
# Benchmark: com.tavianator.boxperf.MyBenchmark.timeLevenshtein
# Run progress: 0.00% complete， ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration 1: 1517.495 ns/op
# Warmup Iteration 2: 1503.096 ns/op
# Warmup Iteration 3: 1402.069 ns/op
# Warmup Iteration 4: 1480.584 ns/op
# Warmup Iteration 5: 1385.345 ns/op
# Warmup Iteration 6: 1474.657 ns/op
# Warmup Iteration 7: 1436.749 ns/op
# Warmup Iteration 8: 1463.526 ns/op
Iteration 1: 1446.033 ns/op
Iteration 2: 1420.199 ns/op
Iteration 3: 1383.017 ns/op
Iteration 4: 1443.775 ns/op
Iteration 5: 1393.142 ns/op
Iteration 6: 1393.313 ns/op
Iteration 7: 1459.974 ns/op
Iteration 8: 1456.233 ns/op
Result "timeLevenshtein":
1424.461 ±(99.9%) 59.574 ns/op [Average]
(min， avg， max) = (1383.017， 1424.461， 1459.974)， stdev = 31.158
CI (99.9%): [1364.887， 1484.034] (assumes normal distribution)
# Run complete. Total time: 00:00:16
Benchmark Mode Cnt Score Error Units
MyBenchmark.timeLevenshtein avgt 8 1424.461 ± 59.574 ns/op
　　分析
　　为了查看代码热路径（hot path）上的结果，JMH集成了Linux工具perf，可以查看热代码块的JIT编译结果。（要想查看汇编代码，需要安装hsdis插件。我在AUR上提供了下载，Arch用户可以直接获取。）在JMH命令行添加 -prof perfasm 命令，可以看到结果：
　　$ java -jar target/benchmarks.jar -f 1 -wi 8 -i 8 -prof perfasm
　　...
　　cmp $0x7f，%eax
　　jg 0x00007fde989a6148 ;*if_icmpgt
　　; - java.lang.Character::valueOf@3 (line 4570)
　　; - com.tavianator.boxperf.StringAsList::get@8 (line 14)
　　; - com.tavianator.boxperf.StringAsList::get@2; (line 5)
　　; - com.tavianator.boxperf.Levenshtein::distance@121 (line 32)
　　cmp $0x80，%eax
　　jae 0x00007fde989a6103 ;*aaload
　　; - java.lang.Character::valueOf @ 10 (line 4571)
　　; - com.tavianator.boxperf.StringAsList::get@8 (line 14)
　　; - com.tavianator.boxperf.StringAsList::get @ 2 (line 5)
　　; - com.tavianator.boxperf.Levenshtein::distance@121 (line 32)
　　...
　　输出内容很多，但上面的一点内容说明装箱没有被优化。为什么要和0x7f/0×80的内容做比较呢？原因在于Character.valueOf()的取值来源：
　　private static class CharacterCache {
　　private CharacterCache(){}
　　static final Character cache[] = new Character[127 + 1];
　　static {
　　for (int i = 0; i < cache.length; i++)
　　cache[i] = new Character((char)i);
　　}
　　}
　　public static Character valueOf(char c) {
　　if (c return CharacterCache.cache[(int)c];
　　}
　　return new Character(c);
　　}
　　可以看出，Java语法标准规定前127个char的Character对象放在缓冲池中，Character.valueOf()的结果在其中时，直接返回缓冲池的对象。这样做的目的是减少内存分配和垃圾回收，但在我看来这是过早的优化。而且它妨碍了其他优化。JVM无法确定 Character.valueOf(c).charValue() == c，因为它不知道缓冲池的内容。所以JVM从缓冲池中取了一个Character对象并读取它的值，结果得到的是和 c 一样的内容。
　　解决方法
　　解决方法很简单：
　　@ @ -11，7 +11，7 @ @ public class StringAsList extends AbstractList {
　　@Override
　　public Character get(int index) {
　　- return str.charAt(index); // Autoboxing!
　　+ return new Character(str.charAt(index));
　　}
　　@Override
　　用显式的装箱代替自动装箱，避免了调用Character.valueOf()，这样JVM很容易理解代码：
　　private final char value;
　　public Character(char value) {
　　this.value = value;
　　}
　　public char charValue() {
　　return value;
　　}
　　虽然代码中加了一个内存分配，但JVM能理解代码的意义，会直接从String中获取char字符。性能提升很明显：
　　$ java -jar target/benchmarks.jar -f 1 -wi 8 -i 8
　　...
　　# Run complete. Total time: 00:00:16
　　Benchmark Mode Cnt Score Error Units
　　MyBenchmark.timeLevenshtein avgt 8 1221.151 ± 58.878 ns/op
　　速度提升了14%。用 -prof perfasm 命令可以显示，改进以后是直接从String中拿到char值并在寄存器中比较的：
　　movzwl 0x10(%rsi，%rdx，2)，%r11d ;*caload
　　; - java.lang.String::charAt@27 (line 648)
　　; - com.tavianator.boxperf.StringAsList::get@9 (line 14)
　　; - com.tavianator.boxperf.StringAsList::get @ 2 (line 5)
　　; - com.tavianator.boxperf.Levenshtein::distance@121 (line 32)
　　cmp %r11d，%r10d
　　je 0x00007faa8d404792 ;*if_icmpne
　　; - java.lang.Character::equals@18 (line 4621)
　　; - com.tavianator.boxperf.Levenshtein::distance@137 (line 33)
　　总结
　　装箱是HotSpot的一个弱项，希望它能做到越来越好。它应该多利用装箱类型的语义，消除装箱操作，这样以上的解决办法没有必要了。
　　以上的基准测试代码都可以在GitHub上访问。