GWT: How to avoiding calls to dynamicCast and canCastUnsafe in generated JavaScript code?

Question

I'm writing some special purpose data structures in Java, intended for use in the browser, (compiled to JavaScript with GWT).

I'm trying to match the performance of some of the built-in JDK classes I'm noticing things run reasonably fast, but when I compare my code trace to some of the emulated JDK code, mine has lots of calls to dynamicCast and canCastUnsafe, while the JDK emulated classes do not. And it just about accounts for the difference in performance too...

Any GWT gurus out there know how to avoid this? It's amounting to a 20% overhead :-(

Details:

Here's the profile output (captured in Firebug) for 10,000 insertions of random integers, between 0 and 100,000 into two different data structures:

Google's TreeMap implementation for java.util.TreeMap (a red-black tree):

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

My Code (An AVL tree):

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

Additional observations:

• Same problem for another data structure I made (SkipList).

• dynamicCast is being applied in the compare function:

  cmp = dynamicCast(right.key, 4).compareTo$(key);

• dynamicCast goes away if the class does not implement Map (ie: just removing " implements Map" from the class. Doesn't matter if it's accessed through the interface or directly. This results in the same line compiling to:

  cmp = right.key.compareTo$(key);

This is the relevant section of Java source from SkipList:

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);

            ...
        }
    }
}

Answer 1

Does the use of java 1.5 generics and wildcards could avoid this ?

Answer 2

Dunno if you've seen this thread in the GWT Contributor's forum...

Basically, it starts with the same problem you've identified, proposes some new compiler flags, and goes on to show how to use some JSNI to get around the casts.

Edit In the GWT trunk there's a new compiler flag. See the wiki...

Answer 3

Unfortunately I'm still not exactly clear on the cause, but from my experience, it seems from explicit casts, like:

((Comparable) obj).compareTo(other)

The Javascript generated looks like:

dynamicCast(obj, 1).compareTo(other);

Where 1 is a generated typeId representing the target of the cast. dynamicCast in turn calls canCastUnsafe and if false, it throws a ClassCastException. The value of this has been debated, since this would already be caught in hosted mode.

It can be sidestepped with JSNI:

public static native int compare(Object a, Object b) /*-{
    return [email protected]::compareTo(Ljava/lang/Object;)(b); 
}-*/;