RFR 8230162: ScopeImpl.remove() has O(N) performance

[Ron Shapiro]

Here's the updated webrev that Brad mentioned in his last message:
http://cr.openjdk.java.net/~ronsh/8230162/webrev.01/

On Wed, Aug 28, 2019 at 2:40 AM Brad Corso <bcorso at google.com> wrote:

> I believe "Do you have any estimates of the increase in size in typical
>> usage, due to the extra field in Scope?" (Jon)
>
>
> I was seeing noticeably bad performance once the size of the Entry.sibling
> linked list reached ~10000, and the max I saw was ~30000 in a single scope.
> Given that an additional reference adds 32/64b, this could add up to
> 120/240Kb for the cases I saw.
>
> I'd add, is there a chance to get an improvement in Scope.remove speed
>> without making ScopeImpl.Entry bigger (assuming it gets bigger(?))? One
>> possibility that occurred to me is that we could try not to remove the
>> things from elems, but only mark them as removed. We would need to do
>> filtering (and possibly the actual removal) while reading from the Scope
>> (in getSymbols), so this is a different kind of trade-off.
>
>
>
> (Overall, I guess the question is whether we are trading problems with
>>
> Scope.remove speed in some cases for out-of-memory problems in other
>> cases.)
>
>
> Thanks, I've verified your suggestion also gives us the performance
> improvements, so this change is okay with me.
>
>
>
>
> On Tue, Aug 27, 2019 at 12:05 AM Jan Lahoda <jan.lahoda at oracle.com> wrote:
>
>> On 27. 08. 19 0:06, Brad Corso wrote:
>> > Sorry, what's the question?
>>
>> I believe "Do you have any estimates of the increase in size in typical
>> usage, due to the extra field in Scope?" (Jon)
>>
>> I'd add, is there a chance to get an improvement in Scope.remove speed
>> without making ScopeImpl.Entry bigger (assuming it gets bigger(?))? One
>> possibility that occurred to me is that we could try not to remove the
>> things from elems, but only mark them as removed. We would need to do
>> filtering (and possibly the actual removal) while reading from the Scope
>> (in getSymbols), so this is a different kind of trade-off.
>>
>> (Overall, I guess the question is whether we are trading problems with
>> Scope.remove speed in some cases for out-of-memory problems in other
>> cases.)
>>
>> Jan
>>
>> >
>> > On Mon, Aug 26, 2019 at 1:54 PM Ron Shapiro <ronshapiro at google.com
>> > <mailto:ronshapiro at google.com>> wrote:
>> >
>> >     Adding Brad back in to the thread since he would know best
>> >
>> >     בתאריך יום ב׳, 26 באוג׳ 2019, 19:40, מאת Jonathan Gibbons
>> >     ‏<jonathan.gibbons at oracle.com <mailto:jonathan.gibbons at oracle.com
>> >>:
>> >
>> >
>> >         On 8/26/19 9:12 AM, Ron Shapiro wrote:
>> >          >
>> >          > Note that the patch was prepared by my coworker, Brad (cc'd).
>> >         I wasn't
>> >          > sure what to do to make sure that he was attributed
>> correctly.
>> >
>> >
>> >         Mention this when you have a sponsor to push the changeset, so
>> >         that it
>> >         can be marked with "Contributed-By:"
>> >
>> >         -- Jon
>> >
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20190904/33bf8cca/attachment.html>