我正在用
Java编写一些特殊用途的数据结构,用于浏览器(用GWT编译成
JavaScript).
我正在尝试匹配一些内置JDK类的性能我注意到运行速度相当快,但是当我将我的代码跟踪与一些模拟的JDK代码进行比较时,我有很多对dynamicCast和canCastUnsafe的调用虽然JDK模拟类没有.它只是解释了性能上的差异……
任何GWT大师都知道如何避免这种情况？这相当于20％的开销:-(
细节：
下面是10,000个随机整数插入的配置文件输出(在Firebug中捕获),介于0到100,000之间,分为两个不同的数据结构：
Google的java.util.TreeMap(红黑树)的TreeMap实现：
Profile (4058.602ms,687545 calls) Function Calls Percent Own Time $insert_1 129809 41.87% 1699.367ms $compare_0 120290 16% 649.209ms $isRed 231166 13.33% 540.838ms compareto_0 120290 8.96% 363.531ms $put_2 10000 6.02% 244.493ms wrapArray 10000 3.46% 140.478ms createFromSeed 10000 2.91% 118.038ms $TreeMap$Node 10000 2.38% 96.706ms initDim 10000 1.92% 77.735ms initValues 10000 1.49% 60.319ms $rotateSingle 5990 0.73% 29.55ms TreeMap$Node 10000 0.47% 18.92ms
我的代码(AVL树)：
Profile (5397.686ms,898603 calls) Function Calls Percent Own Time $insert 120899 25.06% 1352.827ms $compare 120899 17.94% 968.17ms dynamicCast 120899 14.12% 762.307ms <-------- $balanceTree 120418 13.64% 736.096ms $setHeight 126764 8.93% 482.018ms compareto_0 120899 7.76% 418.716ms canCastUnsafe 120899 6.99% 377.518ms <-------- $put 10000 2.59% 139.936ms $AVLTreeMap$Node 9519 1.04% 56.403ms $moveLeft 2367 0.36% 19.602ms AVLTreeMap$State 9999 0.36% 19.429ms $moveRight 2378 0.34% 18.295ms AVLTreeMap$Node 9519 0.34% 18.252ms $swingRight 1605 0.26% 14.261ms $swingLeft 1539 0.26% 13.856ms
补充意见：
>我制作的另一个数据结构(SkipList)也存在同样的问题.
> dynamicCast正在比较函数中应用：
cmp = dynamicCast(right.key,4).compareto $(key);
>如果类没有实现Map,那么dynamicCast就会消失(即：只是从类中删除“implements Map”.无论是通过接口还是直接访问它都无关紧要.这导致同一行编译为：
cmp = right.key.compareto $(key);
这是SkipList的Java源代码的相关部分：
private int compare(Node a,Object o) {
if (comparator != null)
return comparator.compare((K) a.key,(K) o);
return ((Comparable<K>) a.key).compareto((K) o);
}
public V get(Object k) {
K key = (K) k;
Node<K,V> current = head;
for (int i = head.height - 1; i >= 0; i--) {
Node<K,V> right;
while ((right = current.right[i]) != null) {
int cmp = compare(right,key);
...
}
}
}
解决方法
不幸的是,我仍然不清楚原因,但根据我的经验,它似乎来自明确的演员,如：
((Comparable) obj).compareto(other)
生成的Javascript看起来像：
dynamicCast(obj,1).compareto(other);
其中1是生成的typeId,表示演员的目标. dynamicCast依次调用canCastUnsafe,如果为false,则抛出ClassCastException.它的值为debated,因为这已经在托管模式中捕获.
它可以用JSNI回避：
public static native int compare(Object a,Object b) /*-{
return a.@java.lang.Comparable::compareto(Ljava/lang/Object;)(b);
}-*/;