RFR(M): 8231460: Performance issue (CodeHeap) with large free blocks

[Andrew Dinn]

On 04/11/2019 15:35, Schmidt, Lutz wrote:
> thank you for your thoughts. I do not agree to your conclusion, 
> though.
> 
> There are two bottlenecks in the CodeHeap management code. One is in
> CodeHeap::mark_segmap_as_used(), uncovered by
> OverflowCodeCacheTest.java.  The other is in 
> CodeHeap::add_to_freelist(), uncovered by StressCodeCacheTest.java.
> 
> Both bottlenecks are tackled by the recommended changeset.
  . . .
> CodeHeap::add_to_freelist() is still O(n*n), with n being the free 
> list length. But the kick-in point of the non-linearity could be 
> significantly shifted towards larger n. The time reduction from 
> approx. 8 seconds to 160 milliseconds supports this statement.

Ah sorry, I was not clear from your original post that the proposed
change had significantly improved the time spent in free list management
in the second test by significantly cutting down the free list size. As
you say, a reduction factor of 1/K in list size will give a 1/K*K
reduction in execution time. Since this test is a lot nearer to reality
than the overflow test I think the current result is perhaps enough to
justify its value.

> I agree it would be helpful to have a "real-world" example showing 
> some improvement. Providing such evidence is hard, though. I could 
> instrument the code and print some values form time to time. It's 
> certain this additional output will mess up success/failure decisions
> in our test environment. Not sure everybody likes that. But I will
> give it a try and take the hits. This will be a multi-day effort.

Well, that would be nice to have but not if it stops other work. The one
thing about the Stress test that I fear may be 'unreal' is the
potentially over-high probability of generating long(ish) runs of
adjacent free segments. That might be giving an artificial win that we
will not in fact see. However, given the current numbers I'd be happy to
risk that and let this patch go in as is.

> On a general note, I am always uncomfortable knowing of a O(n*n) 
> effort, in particular when it could be removed or at least tamed 
> considerably. Experience tells (at least to me) that, at some point 
> in time, n will be large enough to hurt.

Well, yes, although salesman do travel /and/ make money ... ;-)

> I'll be back.

Sure, thanks for following up. This is all very interesting.

regards,


Andrew Dinn
-----------
Senior Principal Software Engineer
Red Hat UK Ltd
Registered in England and Wales under Company Registration No. 03798903
Directors: Michael Cunningham, Michael ("Mike") O'Neill