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

[Adam Domurad]

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