Request for comments, very slow compilation with super-overloaded methods

[Maurizio Cimadamore]

On 30/05/13 17:20, Adam Domurad wrote:
> On 05/30/2013 04:39 AM, Maurizio Cimadamore wrote:
>> Thanks for the report (and the patch) - we will file a bug on this. I 
>> believe the solution for this is to maintain a fixed-size heap of 
>> candidate; this stuff is mostly there for generating better overload 
>> diagnostics; but in the case you have 255 candidates, I doubt you 
>> want to see them all ;-)
>
> Thank you! Ah, yes that sounds reasonable. I suppose even if they 
> could quickly be determined to not be equal because of parameter 
> length, there would still exist some possibility with many same-name 
> same-argument-count methods.
>
> Out of curiousity though, I do wonder why a custom singly-linked list 
> is used everywhere. Can anyone explain this design choice ? I don't 
> see where they would help performance over standard eg ArrayList.
The linked list version used by javac is permanent and immutable. This 
means that all operations on the list will create a new list (bit like 
String) and, even more importantly, adding new nodes will keep old list 
around. ArrayList has two disadvantages: is mutable - meaning that you 
can end up with very weird behavior if some compiler component 
accidentally overwrites some list element; it is also, on average, 
always half empty - which is also suboptimal for the particular use case 
of the compiler (which is only working with very small lists).

The VM is actually very good at optimizing permanent immutable data 
structures, so this turns out to be a biggie win in JIT too.

All experiments we made internally to replace our 'good old' linked list 
implementation with some fancier data structures led to no gain 
(actually, in most case a performance regression was observed).

That said, there are things that we dislike about current implemenation:

*) calling relatively harmless operation such as 'length' has complexity 
O(n)
*) very bad append performances (O(n)) meaning that it's usually better 
to to prepends and to work with a 'reversed' list, which isn't very 
intuitive.

We would like to revisit this core data structure in the future, and we 
have some options on the table - ArrayList is not one of them ;-)

Thanks
Maurizio
>
> Thanks for filing the bug.
>
> Happy hacking,
> -Adam
>
>>
>> Maurizio
>>
>> On 29/05/13 20:09, Adam Domurad wrote:
>>> Hi, see attached sources.zip containing ArrayUtil.java & 
>>> MethodHandle.java, taken from Groovy sourcecode.
>>> They exhibit a case with which javac performs very badly.
>>>
>>> Try
>>>  javac ArrayUtil.java #Not too bad
>>>  javac MethodHandle.java # But this takes many minutes
>>>
>>> Note that MethodHandle references ArrayUtil, and this is 
>>> auto-generated code.
>>>
>>> ECJ compiles this source code in ~4 seconds.
>>>
>>> This problem is present in JDK8 and JDK7.
>>>
>>>      - The performance problem stems from 
>>> com.sun.tools.javac.comp.Resolve.InapplicableSymbolsError.Candidate#equals. 
>>> This is used during method resolution, and is performed O(n^2) times 
>>> for 'n' same-name methods. It references rather expensive methods 
>>> that iterate over and potentially copy (eg for erasure) both 
>>> argument lists, which can be up to 255 elements in this case.
>>>      - MethodHandle references a method from ArrayUtil that has 255 
>>> candidates; this is many orders of magnitude slower than it should be.
>>>
>>> I have attached a patch that does a hackish fix, by providing a fast 
>>> route for when method is obviously not a sub-signature of another.
>>> The patch is mainly there as a proof-of-concept (its rather slapped 
>>> on), hopefully someone knows a better way to fix these corner cases?
>>>
>>> I am rather dubious about argument lists pervasively being treated 
>>> as singly-linked lists. It makes certain operations quite costly, 
>>> even changing the complexity of them unfavourably.
>>>
>>> Happy hacking,
>>> -Adam
>>>
>>
>