Java Nested Foreach SLOW When Casting

Question

I am writing an exchange system in Java, but I seem to have run into a crippling performance issue.

The following code is where execution becomes VERY slow:

    outer:
    for(ArrayList<Offer> listSell : sellOffers.values()) {
        for(Offer sellOffer : listSell) {
            ArrayList<Offer> listBuy = buyOffers.get(getStorageHash(sellOffer));
            if(listBuy == null)
                continue outer;
            for(int i = 0; i < listBuy.size(); i++) {
                Offer buyOffer = listBuy.get(i);
                //todo - handle exchange
            }
        }
    }

After looking deeper into this, I found that the following line seems to be the issue:

                Offer buyOffer = listBuy.get(i);

If I change this line to the following, it will no longer cripple execution time:

                Object buyOffer = listBuy.get(i);

Therefore, when casting on the object from listBuy there is a major delay in execution. Is there any work around for this? I'm stumped.

Thanks in advance!

Answer 1

You measure it wrong.

When you write Object buyOffer = listBuy.get(i); the inner loop has no side effects, and JIT compiler eliminates the loop completely.

With Offer buyOffer JIT is not allowed to remove the loop, because every list access now has a possible side effect of throwing ClassCastException.

Type check is a fast operation, I doubt that it is a bottleneck in your application. Most likely the algorithm itself is suboptimal since it has a cubic complexity.