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

[Vicente-Arturo Romero-Zaldivar]

Hi Adam,

The bug has been solved and pushed into JDK 7 mainstream.

bug id: JDK-8015668: overload resolution: performance regression in JDK 7

the changeset is accessible here:

http://hg.openjdk.java.net/jdk7u/jdk7u40-dev/langtools/rev/06285eb8d755

Sorry for the late update.

Vicente.

On 01/08/13 20:34, Adam Domurad wrote:
> On 05/30/2013 12:31 PM, Maurizio Cimadamore wrote:
>> 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
>>>>>
>>>>
>>>
>>
>
> Any progress on this bug ? Any bug ID ?
>
> Thanks,
> -Adam