<div dir="ltr">
<div dir="ltr"><div>Hi,</div><div><br></div><div>I'm having a hard time
understanding the priority redistribution code for OldObjectSample. Some
months ago, there was a thread about it at <a href="https://mail.openjdk.org/pipermail/hotspot-jfr-dev/2023-June/005066.html" target="_blank">https://mail.openjdk.org/pipermail/hotspot-jfr-dev/2023-June/005066.html</a>,
but it didn't conclude one way or the other whether this code looked
correct. I'm hoping to understand the intent, and maybe also discuss
whether the current implementation follows that intent. I'll be
describing my understanding in order to surface any misunderstandings,
so apologies for the incoming wall of text. Please correct me if I'm
getting things wrong.<br></div><div><br></div><div># The intent</div><div><br></div><div>If
we think of allocations as a "timeline", where each sampled object
extends the timeline by adding more bytes to the right side of the line,
my understanding is that the goal of this code is to ensure that the
samples we keep around in the priority list are as evenly distributed
across this timeline as possible. We'd presumably like a good
distribution whether objects are garbage collected or not.</div><div><br></div><div>
Going by the earlier mailing list comment at
<a href="https://mail.openjdk.org/pipermail/hotspot-jfr-dev/2024-January/005847.html" target="_blank">https://mail.openjdk.org/pipermail/hotspot-jfr-dev/2024-January/005847.html</a>,
it seems like the intent was that the sample spans should cover the
entire allocation timeline when summed. <br></div><div><br></div>I think
the invariant that's being aimed for is that a sample always covers the
span of bytes allocated since the older neighboring sample was taken.
When a node is removed, the span of the removed node should be given to
the younger neighbor, which ensures the neighbor will cover the span
left missing by the node being removed. When a node is removed that has
no younger neighbor, the span should be given to the next sample added
to the queue, which ensures the new sample will cover the span to the
older neighbor.<br></div><div dir="ltr"><br></div><div dir="ltr">The
total spans of the nodes in the queue will then nearly sum to the total
allocated bytes, and any missing bit (due to removal of the youngest
sample/rejection of incoming samples because their spans are too small)
will be covered by the next sample added to the queue.<br></div><div dir="ltr"><br></div><div dir="ltr">
I
think
the idea is that by continually adjusting sample spans as neighbors are
GC'ed or otherwise removed, and by keeping the samples with the largest
spans,
we'll end up with samples that are well distributed across the timeline.
</div><div dir="ltr"><br><div># The current implementation</div><div><br></div><div>When
an object is added, the sampler calculates a new span by counting how
many bytes have been sampled so far (including the sample potentially
being added), and subtracting the spans of the items already in the
queue. <a href="https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L252" target="_blank">https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L252</a>.</div><div><br></div><div>This
calculated span is used only for deciding whether to add the new sample
to the queue. If added, the sample gets a span equal to the byte size
of the object being allocated. <a href="https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L281" target="_blank">https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L281</a></div><div><br></div><div>When
a sample is dropped due to GC, the span it covers is handed to the
`prev`
sample in the list.
As far as I can tell, the list is ordered youngest-sample-first, so this
adds the span to the younger neighbor sample. If there is no younger
neighbor, the span is discarded. <a href="https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L309" target="_blank">https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L309</a></div><div><br></div><div>When a sample is dropped in favor of a new sample with a larger span, the old sample's span is discarded. <a href="https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L261" target="_blank">https://github.com/openjdk/jdk/blob/32c7681cf310c87669c502c4a8b62a7fecc93360/src/hotspot/share/jfr/leakprofiler/sampling/objectSampler.cpp#L261</a></div><div><br></div><div># The bits I think might not fit the intent</div><div><br></div><div>
<div>*
The span stored in each sample is not the calculated span, it's just
the object's byte size (`allocated`). That means as soon as any object
falls out of the queue, the spans in the queue no longer sum to cover
the allocation timeline. This causes all future samples to be added to
be unduly prioritized for adding to the queue, because they are given an
artificially high span. In effect, future samples are weighted as if
they cover both the interval between themselves and the older neighbor
sample, plus all "missing spans" from nodes that have been discarded
since the program started. <br></div><div><br></div><div>
<div>
<div>Just to demonstrate that there might be a problem, I tried limiting the sampler queue size to 3, and calling the
`ObjectSampler::add` method 10 times in a row with a dummy object and a fixed byte size of 10.</div><div><br></div><div>The
result is that the 1st, 2nd and 10th allocations are kept. This is
because after the first 3 inserts to fill the queue, the 4th sample is
discarded because the calculated span is 40 - 30 = 10. The 5th item will
calculate the span 50 - 30 = 20, and so replace the smallest sample (in
span terms), which will be the youngest since all samples have a
stored span of 10. This will repeat for the 6th-10th items (the calculated span increasing by 10 per item), always
replacing
the most recently inserted sample.</div></div>
</div><div><br></div><div>I think the span stored in a sample should be
the span calculated when comparing to existing samples, and not the
object's byte size. <br></div><div><br></div><div>* When a sample
is removed from the queue because a sample with a larger span is being
added, the span of the removed node is not handed to
the younger neighbor, this only happens when a sample is removed due to
GC. This means that the span will be given to the next sample added to
the queue. When the sample being removed
is the youngest sample, this is fine, but when it's a sample that has a
younger neighbor, the span should probably be given to that neighbor
rather
than the newcomer. Handing it to the newcomer gives the new sample a
high
weight it doesn't deserve. It ends up covering not just the span to the
older neighbor, but also the span of the removed node, which doesn't seem to be what
we want?<br></div><div><br></div><div>I think when a sample is removed
because it's being evicted in favor of a new sample, its span should be
given to the younger neighbor. If there is no younger neighbor, the span
should instead be given to the sample being added.</div></div></div>
</div>