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

[Jan Lahoda]

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
>              >
>