作者sbrhsieh (十年～)
看板java
标题Re: [翻译] Java 的 method call 要付出多少代价？
时间Wed Mar 20 02:16:54 2013
希望没有扯的太牵强。
或许有人还是偏爱递回的写法，无法割舍...
那讲到递回除了考虑效能，另外一点就是递回 depth 太深会炸掉 stack 的问题。
ㄟ... 这些部分有兴趣的人不妨看一下这一篇：
http://www.javaworld.com.tw/jute/post/view?bid=5&id=277737&tpg=1&ppg=1&sty=1&age=0#277737
虽然特地写成 Tail-Recursion 形式的 recursion 有时有点矫情，形式上也没有
其他较直观的 recursion 的形式来的美...
我有写了一个 Tail-Recursion 的 RecursiveSummarizer2 class:
package eu.plumbr.demo.inlining;
import tw.javaworld.optimizer.TailRecursionEliminated;
public class RecursiveSummarizer2 implements Summarizer {
@Override
public int sum(int[] array) {
return sumImpl(0, array, 0, array.length);
}
@TailRecursionEliminated
private int sumImpl(int acc, int[] data, int from, int to) {
if (from < to)
return sumImpl(acc + data[from], data, from + 1, to);
return acc;
}
}
并稍微修改原作者的 test case:
package eu.plumbr.demo.inlining;
public class Main {
static final int COUNT = 200; //
我改成 200，暖身久一点
public static void main(String[] args) {
Summarizer[] summarizers = new Summarizer[] {
new InlineSummarizer(), new IterativeSummarizer(),
new RecursiveSummarizer(),
new RecursiveSummarizer2(),
};
int[] array = initArray();
for (Summarizer s : summarizers) {
// Warm-up to discard runs where JIT optimizations were not
// yet completed. Check it out by switching on JIT log
// -XX:+PrintCompilation. You probably need to tweak the Main.COUNT
// on different architectures.
for (int j = 0; j < 5; j++) {
long start = System.nanoTime();
for (int i = 0; i < COUNT; i++)
s.sum(array);
long end = System.nanoTime();
logTime(s.getClass().getName(), start, end);
}
}
}
private static void logTime(String message, long start, long end) {
System.out.println(message + ":" + (end - start) / COUNT + " ns.");
}
private static int[] initArray() {
int[] array = new int[1024];
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
return array;
}
}
我有试过分别啓用与不啓用 TailRecursionEliminated 功能的情况，
我感觉暖身似乎可能还是不太够，因为跑个几次觉得输出的数值落差还不算小。
由於待加数值只有 1024 个，所以是不会有炸掉 thread stack 的情事，那
启用 TailRecursionEliminated 的情况就变成是把递回偷偷改成 iteration。
我贴上我跑几次中的结果之一
无啓用 TailRecursionEliminated 时：
eu.plumbr.demo.inlining.InlineSummarizer:31460 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1420 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1840 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1420 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:78895 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:32005 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:15470 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10285 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:6460 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:77360 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7915 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7990 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7695 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7760 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:24725 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5695 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5565 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5930 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5530 ns.
有啓用 TailRecursionEliminated 时：
eu.plumbr.demo.inlining.InlineSummarizer:29790 ns.
eu.plumbr.demo.inlining.InlineSummarizer:3255 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:84275 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:35055 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10835 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10555 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:6715 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:90520 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8115 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8045 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8040 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7980 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:23120 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5550 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5445 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5515 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5460 ns.
从这些数据来看，我认为似乎写成 Tail-Recursion 的形式，JVM 就有一部分
优化，导致 RecursiveSummarizer2 的数据更接近 IterativeSummarizer。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 1.172.191.203
※ 编辑: sbrhsieh 来自: 1.172.191.203 (03/20 02:25)