[9] RFR(XS) 8059780: SPECjvm2008-MPEG performance regressions on x64 platforms

[John Rose]

On Nov 3, 2014, at 9:40 AM, Dean Long <dean.long at oracle.com> wrote:

> By the way, do we know why the lcm change caused  a regression?  Is reordering the worklist
> using pop() a design feature?

It's simple a data structure trick.  The worklist is logically unordered, but physically packed into an array.

If you remove an item from an array, preserving order, you have to move O(N) items to close up the gap.

If you don't care about order, you can remove an item with O(1) move, as shown in the restored code.

It is possible (though unlikely) that the performance regression was due to JIT compilation slowdown.

In the JIT we try hard to use O(1) algorithms instead of O(N) ones, O(N) instead of O(N^2), etc.  It's obvious once you state it, but it is non-trivial to avoid adding an exponent (turning O(1) into O(N), etc.).

Generally speaking, if there is a problem in the JIT due to optimization order (as there seems to have been on ARM) the solution is almost certainly not to add to the exponent of our algorithm, but to find some sort of targeted extraction of items from the worklist in the needed order.

— John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20141103/9958d8d2/attachment-0001.html>