Friday, December 11, 2015

程序优化 Optimization

http://blog.me115.com/2015/08/860

程序优化的5个方向

80/20法则：程序执行中，80%的时间消耗在20%的代码上。
优化前，我们首先得找到这20%的关键路径；
各种语言都有专门的工具来找到这20%的关键路径，比如C++经常用到的gprof；

参考《C++的性能优化实践》

在关键路径上对耗时的计算进行优化；
主要的优化方向为：
减少重复计算、预先计算、延后计算、降低计算代价、不计算；

减少重复计算

典型的例子如缓存，将之前相同的计算（查数据库，读写文件）存下来，等待下一次继续使用；
适用场景：计算结果有有效期，过段时间后需要再次计算；

预先计算

对于关键路径中比较耗时的计算，预先计算出来，节省每次计算的成本；

预先计算出对照表
关键路径中需要用到的映射关系对照表，将对照表预先计算，在关键路径中直接取用；
将计算提前到初始化期间
比如，内存分配耗时，将其提前到初始化的时间分配，建立内存池；
将计算提前到编译期间
比如：使用常量表达式，在编译期间将最终值计算出来，节省这部分的运行时开销；
相关技术：模版元编程；

适用场景：计算出来的值一直有效，无需再次计算；

延迟计算

将计算耗时延迟到后期，这样，对于异常情况或其它分支情况，在中途就转换，不用再计算；

有较多分支条件
将最耗时的计算延后，这样，可能很多场景在中途就转到其它分支上，不用计算；
判断条件中的技巧：a||b a&&b
如果判断条件比较耗时，将更耗时的放在后面计算；这样，对于a||b,当a成立时，b就不用再计算了；延迟计算的好处在于可能可以不用计算；

适用场景：分支条件场景；

降低计算代价

这是通常能想到的最直接的优化手段，如何能够直接降低计算的代价；

内存申请从堆上改为栈上
动态内存分配昂贵，将内存分配从堆上改为栈上；
降低灵活性，使用自定制版本的函数代替库函数；
使用更低级的指令或语言改写；
在C++中嵌入汇编语言；
使用SSE2等指令集；
使用更优的算法或数据结构；
操作STL容器时，STL中的算法一般比自己手写的算法要高效，尽量使用STL的算法来替换我们的手写算法；
参考：
《STL区间成员函数及区间算法总结》
《高效的使用STL》

适用场景：这类优化一般是以降低代码可读性为代价的（STL的除外），用于优化的最后阶段；

不计算

优化的终极方案，不计算；

业务发现
用不到的业务逻辑，废弃的业务逻辑，仍然存在关键路径中的还在执行的；痛快的删除它；
却掉临时对象开销
在我们的代码中，可能会有些临时对象是不知不觉的，而消除临时对象，将节省这部分开销；
参考：《消除临时对象》

以上是单线程关键路径的优化，接下来，我们聊聊扩展到多核，在多线程上的优化；

http://blog.me115.com/2015/08/863
面向GC的Java编程
http://coolshell.cn/articles/11541.html

过早优化是万恶之源。

但另一方面，什么才是“过早优化”？

If we could do things right for the first time, why not?

如果我们可以一次把事情做对，并且做好，在允许的范围内尽可能追求卓越，为什么不去做呢？

不要指望GC优化的这些技巧，可以对应用性能有成倍的提高，特别是对I/O密集型的应用，或是实际落在YoungGC上的优化，可能效果只是帮你减少那么一点YoungGC的频率。

大部分GC算法，都将堆内存做分代(Generation)处理，但是为什么要分代呢，又为什么不叫内存分区、分段，而要用面向时间、年龄的“代”来表示不同的内存区域？

GC分代的基本假设是：

绝大部分对象的生命周期都非常短暂，存活时间短。

而这些短命的对象，恰恰是GC算法需要首先关注的。所以在大部分的GC中，YoungGC（也称作MinorGC）占了绝大部分，对于负载不高的应用，可能跑了数个月都不会发生FullGC。

基于这个前提，在编码过程中，我们应该尽可能地缩短对象的生命周期。在过去，分配对象是一个比较重的操作，所以有些程序员会尽可能地减少new对象的次数，尝试减小堆的分配开销，减少内存碎片。

但是，短命对象的创建在JVM中比我们想象的性能更好，所以，不要吝啬new关键字，大胆地去new吧。

当然前提是不做无谓的创建，对象创建的速率越高，那么GC也会越快被触发。

结论：

分配小对象的开销分享小，不要吝啬去创建。
GC最喜欢这种小而短命的对象。
让对象的生命周期尽可能短，例如在方法体内创建，使其能尽快地在YoungGC中被回收，不会晋升(romote)到年老代(Old Generation)。

二、对象分配的优化

基于大部分对象都是小而短命，并且不存在多线程的数据竞争。这些小对象的分配，会优先在线程私有的TLAB 中分配，TLAB中创建的对象，不存在锁甚至是CAS的开销。

TLAB占用的空间在Eden Generation。

当对象比较大，TLAB的空间不足以放下，而JVM又认为当前线程占用的TLAB剩余空间还足够时，就会直接在Eden Generation上分配，此时是存在并发竞争的，所以会有CAS的开销，但也还好。

当对象大到Eden Generation放不下时，JVM只能尝试去Old Generation分配，这种情况需要尽可能避免，因为一旦在Old Generation分配，这个对象就只能被Old Generation的GC或是FullGC回收了。

三、不可变对象的好处

GC算法在扫描存活对象时通常需要从ROOT节点开始，扫描所有存活对象的引用，构建出对象图。

不可变对象对GC的优化，主要体现在Old Generation中。

可以想象一下，如果存在Old Generation的对象引用了Young Generation的对象，那么在每次YoungGC的过程中，就必须考虑到这种情况。

Hotspot JVM为了提高YoungGC的性能，避免每次YoungGC都扫描Old Generation中的对象引用，采用了卡表(Card Table) 的方式。

简单来说，当Old Generation中的对象发生对Young Generation中的对象产生新的引用关系或释放引用时，都会在卡表中响应的标记上标记为脏(dirty)，而YoungGC时，只需要扫描这些dirty的项就可以了。

可变对象对其它对象的引用关系可能会频繁变化，并且有可能在运行过程中持有越来越多的引用，特别是容器。这些都会导致对应的卡表项被频繁标记为dirty。

而不可变对象的引用关系非常稳定，在扫描卡表时就不会扫到它们对应的项了。

注意，这里的不可变对象，不是指仅仅自身引用不可变的final对象，而是真正的Immutable Objects。

四、引用置为null的传说

早期的很多Java资料中都会提到在方法体中将一个变量置为null能够优化GC的性能，类似下面的代码：

List<String> list = new ArrayList<String>();

// some code

list = null; // help GC

事实上这种做法对GC的帮助微乎其微，有时候反而会导致代码混乱。

我记得几年前 @rednaxelafx 在HLL VM小组中详细论述过这个问题，原帖我没找到，结论基本就是：

在一个非常大的方法体内，对一个较大的对象，将其引用置为null，某种程度上可以帮助GC。
大部分情况下，这种行为都没有任何好处。

所以，还是早点放弃这种“优化”方式吧。

GC比我们想象的更聪明。

五、手动档的GC

在很多Java资料上都有下面两个奇技淫巧：

通过Thread.yield()让出CPU资源给其它线程。
通过System.gc()触发GC。

事实上JVM从不保证这两件事，而System.gc()在JVM启动参数中如果允许显式GC，则会触发FullGC，对于响应敏感的应用来说，几乎等同于自杀。

So，让我们牢记两点：

Never use Thread.yield()。
Never use System.gc()。除非你真的需要回收Native Memory。

第二点有个Native Memory的例外，如果你在以下场景：

使用了NIO或者NIO框架（Mina/Netty）
使用了DirectByteBuffer分配字节缓冲区
使用了MappedByteBuffer做内存映射

由于Native Memory只能通过FullGC（或是CMS GC）回收，所以除非你非常清楚这时真的有必要，否则不要轻易调用System.gc()，且行且珍惜。

另外为了防止某些框架中的System.gc调用（例如NIO框架、Java RMI），建议在启动参数中加上-XX:+DisableExplicitGC来禁用显式GC。

这个参数有个巨大的坑，如果你禁用了System.gc()，那么上面的3种场景下的内存就无法回收，可能造成OOM，如果你使用了CMS GC，那么可以用这个参数替代：-XX:+ExplicitGCInvokesConcurrent。

关于System.gc()，可以参考 @bluedavy 的几篇文章：

六、指定容器初始化大小

Java容器的一个特点就是可以动态扩展，所以通常我们都不会去考虑初始大小的设置，不够了反正会自动扩容呗。

但是扩容不意味着没有代价，甚至是很高的代价。

例如一些基于数组的数据结构，例如StringBuilder、StringBuffer、ArrayList、HashMap等等，在扩容的时候都需要做ArrayCopy，对于不断增长的结构来说，经过若干次扩容，会存在大量无用的老数组，而回收这些数组的压力，全都会加在GC身上。

这些容器的构造函数中通常都有一个可以指定大小的参数，如果对于某些大小可以预估的容器，建议加上这个参数。

可是因为容器的扩容并不是等到容器满了才扩容，而是有一定的比例，例如HashMap的扩容阈值和负载因子(loadFactor)相关。

Google Guava框架对于容器的初始容量提供了非常便捷的工具方法，例如：

Lists.newArrayListWithCapacity(initialArraySize);

Lists.newArrayListWithExpectedSize(estimatedSize);

Sets.newHashSetWithExpectedSize(expectedSize);

Maps.newHashMapWithExpectedSize(expectedSize);

这样我们只要传入预估的大小即可，容量的计算就交给Guava来做吧。

反例：如果采用默认无参构造函数，创建一个ArrayList，不断增加元素直到OOM，那么在此过程中会导致：

多次数组扩容，重新分配更大空间的数组
多次数组拷贝
内存碎片

七、对象池

为了减少对象分配开销，提高性能，可能有人会采取对象池的方式来缓存对象集合，作为复用的手段。

但是对象池中的对象由于在运行期长期存活，大部分会晋升到Old Generation，因此无法通过YoungGC回收。

并且通常……没有什么效果。

对于对象本身：

如果对象很小，那么分配的开销本来就小，对象池只会增加代码复杂度。
如果对象比较大，那么晋升到Old Generation后，对GC的压力就更大了。

从线程安全的角度考虑，通常池都是会被并发访问的，那么你就需要处理好同步的问题，这又是一个大坑，并且同步带来的开销，未必比你重新创建一个对象小。

对于对象池，唯一合适的场景就是当池中的每个对象的创建开销很大时，缓存复用才有意义，例如每次new都会创建一个连接，或是依赖一次RPC。

比如说：

线程池
数据库连接池
TCP连接池

即使你真的需要实现一个对象池，也请使用成熟的开源框架，例如Apache Commons Pool。

另外，使用JDK的ThreadPoolExecutor作为线程池，不要重复造轮子，除非当你看过AQS的源码后认为你可以写得比Doug Lea更好。

八、对象作用域

尽可能缩小对象的作用域，即生命周期。

如果可以在方法内声明的局部变量，就不要声明为实例变量。
除非你的对象是单例的或不变的，否则尽可能少地声明static变量。

九、各类引用

java.lang.ref.Reference有几个子类，用于处理和GC相关的引用。JVM的引用类型简单来说有几种：

Strong Reference，最常见的引用
Weak Reference，当没有指向它的强引用时会被GC回收
Soft Reference，只当临近OOM时才会被GC回收
Phantom Reference，主要用于识别对象被GC的时机，通常用于做一些清理工作

当你需要实现一个缓存时，可以考虑优先使用WeakHashMap，而不是HashMap，当然，更好的选择是使用框架，例如Guava Cache。

最后，再次提醒，以上的这些未必可以对代码有多少性能上的提升，但是熟悉这些方法，是为了帮助我们写出更卓越的代码，和GC更好地合作。