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

[Ron Shapiro]

Hi, can someone sponsor/submit (I think that's right terminology) this
patch? I don't want it to get lost.

Here is the latest webrev for reference:
http://cr.openjdk.java.net/~ronsh/8230162/webrev.01/

On Mon, Sep 30, 2019 at 7:16 PM Brad Corso <bcorso at google.com> wrote:

> Friendly ping.
>
> On Wed, Sep 18, 2019 at 9:55 AM Brad Corso <bcorso at google.com> wrote:
>
>> Hi Jan,
>>
>> I'm okay with either version so I'll leave that decision up to you.
>>
>> Let me know if there's anything else you need from me.
>>
>> Thanks!
>> Brad
>>
>> On Wed, Sep 18, 2019 at 12:38 AM Jan Lahoda <jan.lahoda at oracle.com>
>> wrote:
>>
>>> I've added logging to count how many Entries are created, and there's a
>>> little above 500000 instances created for java.base and a little less
>>> for java.desktop. So if the Entry would be 8 bytes bigger, it would be
>>> about 4MB, which does not sound terrible. So maybe we should go with
>>> version .00.
>>>
>>> Jan
>>>
>>> On 18. 09. 19 3:10, Brad Corso wrote:
>>> > Hi Jan, are you okay moving forward with
>>> > http://cr.openjdk.java.net/~ronsh/8230162/webrev.01/?
>>> >
>>> > On Wed, Sep 4, 2019 at 5:15 AM Ron Shapiro <ronshapiro at google.com
>>> > <mailto:ronshapiro at google.com>> wrote:
>>> >
>>> >     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
>>> >     <mailto: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 <mailto: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>
>>> >              > <mailto: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>
>>> >             <mailto: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/20191008/bc3c00a4/attachment.html>