A deficiency in lucene code that affects memory footprint and GC

--_004_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_
Content-Type: multipart/alternative;
	boundary="_000_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_"

--_000_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_
Content-Type: text/plain; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable

Hi Lucene community,

At LinkedIn, we use lucene in some important search apps. We recently found=
 some problems with GC and memory footpring in one of them. We took a heap =
dump and analyzed it with JXRay (https://jxray.com). Unfortunately, we cann=
ot share the entire jxray analysis due to security restrictions, but we can=
 share one excerpt from it, see below. It comes from section 11 of jxray re=
port, =93Bad Primitive Arrays=94, which tells us how much memory is wasted =
due to empty or under-utilized primitive arrays. That section says that nea=
rly 4G of memory (25.6% of used heap) is wasted. And it turns out that most=
 of that is due to byte[] arrays managed by SegmentTermsEnumFrame class.

[cid:f9518e74-7eac-4549-ba08-28734c245bc6]

To clarify: from the above screenshot, e.g. 80% of all arrays pointed by su=
ffixBytes data field are just empty, i.e. contain only zeroes, which likely=
 means that they have never been used. Of the remaining arrays, 3% are =93t=
rail-0s=94, i.e. have more than a half of trailing zero elements, i.e. were=
 only partially utilized. So only 17% of these arrays have been utilized mo=
re or less fully. The same is true for all other byte[] arrays managed by S=
egmentTermsEnumFrame. Note that from other sections of the heap dump it=92s=
 clear that the majority of these objects are garbage, i.e. they have alrea=
dy been used and discarded. Thus, at least 80% of memory that was allocated=
 for these byte[] arrays has not been used and was wasted. From separate me=
mory allocation profiling, we estimated that these arrays are responsible f=
or ~2G/sec of memory allocation. If they were allocated lazily rather than =
eagerly, i.e. just before they would be really used, we could potentially r=
educe their memory allocation rate share from 2G/sec to (1 - 0.8)*2 =3D 0.4=
 G/sec.

A switch from eager to lazy allocation of some data structure is usually ea=
sy to implement. Let=92s take a quick look at the source code<https://fossi=
es.org/linux/www/lucene-10.3.2-src.tgz/lucene-10.3.2/lucene/backward-codecs=
/src/java/org/apache/lucene/backward_codecs/lucene90/blocktree/SegmentTerms=
EnumFrame.java>. The suffixBytes array usage has the following pattern:

// Eager construction with hardcoded size
byte[] suffixBytes =3D new byte[128];

=85  // Fast forward to the loadBlock() method
=85
if (suffixBytes.length < numSuffixBytes) {
  // If we need to read more than 128 bytes, increase the array=85
  // =85 or more precisely, throw away the old array and allocate another o=
ne
  suffixBytes =3D new byte[ArrayUtil.oversize(numSuffixBytes, 1)];
}

From this code, it=92s clear that two negative things can happen:

  1.
suffixBytes may not be used at all (the loadBlock() method may not be calle=
d or may return early). The memory used by the array will be completely was=
ted
  2.
If numSuffixBytes happens to be greater than 128, the current eagerly alloc=
ated array will be discarded. The memory used by it will be wasted.

And as our heap dump illustrates, these things likely happen very often. To=
 address this problem, it would be sufficient to change the code as follows=
:

// Avoid eager construction
byte[] suffixBytes;
=85
if (suffixByte =3D=3D null || suffixBytes.length < numSuffixBytes) {
  // If we need to read more than 128 bytes, increase the array=85
  // =85 or more precisely, throw away the old array and allocate another o=
ne
  suffixBytes =3D new byte[ArrayUtil.oversize(numSuffixBytes, 1)];
}

Note that reducing memory allocation rate results primarily in reduction of=
 CPU usage and/or improved latency. That=92s because each object allocation=
 requires work from the JVM - updating pointers and setting all object byte=
s to zero. And then GCing these objects is also CPU-intensive, and results =
in pausing app threads, which affects latency. However, once memory allocat=
ion rate is reduced, it may be possible to also reduce the JVM heap memory.=
 So the ultimate win is going to be in both CPU and memory.

Please let us know how we can proceed with this. The proposed change is tri=
vial, and thus maybe it can be done quickly by some established Lucene cont=
ributor. If not, I guess I can make it myself and then hope that it goes th=
rough review and release in reasonable time.

Misha


--_000_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_
Content-Type: text/html; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable

<html>
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3DWindows-1=
252">
<style type=3D"text/css" style=3D"display:none;"> P {margin-top:0;margin-bo=
ttom:0;} </style>
</head>
<body dir=3D"ltr">
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
Hi Lucene community,</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
At LinkedIn, we use lucene in some important search apps. We recently found=
 some problems with GC and memory footpring in one of them. We took a heap =
dump and analyzed it with JXRay (https://jxray.com). Unfortunately, we cann=
ot share the entire jxray analysis
 due to security restrictions, but we can share one excerpt from it, see be=
low. It comes from section 11 of jxray report, =93Bad Primitive Arrays=94, =
which tells us how much memory is wasted due to empty or under-utilized pri=
mitive arrays. That section says that
 nearly 4G of memory (25.6% of used heap) is wasted. And it turns out that =
most of that is due to byte[] arrays managed by SegmentTermsEnumFrame class=
.</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; display: inline-block; fon=
t-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetic=
a, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=3D"elementToPro=
of">
<img size=3D"98558" style=3D"width: 624px; height: 288px; max-width: 806px;=
 margin-top: 0px; margin-left: 0px;" height=3D"288" width=3D"624" data-outl=
ook-trace=3D"F:1|T:1" src=3D"cid:f9518e74-7eac-4549-ba08-28734c245bc6"></di=
v>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
To clarify: from the above screenshot, e.g. 80% of all arrays pointed by su=
ffixBytes data field are just empty, i.e. contain only zeroes, which likely=
 means that they have never been used. Of the remaining arrays, 3% are =93t=
rail-0s=94, i.e. have more than a half
 of trailing zero elements, i.e. were only partially utilized. So only 17% =
of these arrays have been utilized more or less fully. The same is true for=
 all other byte[] arrays managed by SegmentTermsEnumFrame. Note that from o=
ther sections of the heap dump it=92s
 clear that the majority of these objects are garbage, i.e. they have alrea=
dy been used and discarded. Thus, at least 80% of memory that was allocated=
 for these byte[] arrays has not been used and was wasted. From separate me=
mory allocation profiling, we estimated
 that these arrays are responsible for ~2G/sec of memory allocation. If the=
y were allocated lazily rather than eagerly, i.e. just before they would be=
 really used, we could potentially reduce their memory allocation rate shar=
e from 2G/sec to (1 - 0.8)*2 =3D 0.4
 G/sec.</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
A switch from eager to lazy allocation of some data structure is usually ea=
sy to implement. Let=92s take a quick look at the
<span style=3D"color: rgb(17, 85, 204);"><u><a style=3D"color: rgb(17, 85, =
204);" class=3D"OWAAutoLink" id=3D"OWA75609110-9a80-c057-6ba8-22d9efc3d8f3"=
 href=3D"https://fossies.org/linux/www/lucene-10.3.2-src.tgz/lucene-10.3.2/=
lucene/backward-codecs/src/java/org/apache/lucene/backward_codecs/lucene90/=
blocktree/SegmentTermsEnumFrame.java">source
 code</a></u></span>. The suffixBytes&nbsp;array usage has the following pa=
ttern:<br>
<br>
// Eager construction with hardcoded size</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
byte[] suffixBytes =3D new byte[128];<br>
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
=85&nbsp; // Fast forward to the loadBlock() method</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<span style=3D"font-weight: 700;">=85</span></div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<span style=3D"font-weight: 700;">if</span>&nbsp;(suffixBytes.length &lt; n=
umSuffixBytes) {</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp;&nbsp;// If we need to read more than 128 bytes, increase the array=
=85</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp;&nbsp;// =85 or more precisely, throw away the old array and allocate=
 another one</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp; suffixBytes =3D <span style=3D"font-weight: 700;">new byte</span>[Ar=
rayUtil.oversize(numSuffixBytes, 1)];</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
}</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
From this code, it=92s clear that two negative things can happen:</div>
<ol style=3D"margin-top: 0px; margin-bottom: 0px;" start=3D"1">
<li style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, C=
alibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); direct=
ion: ltr; list-style-type: decimal;">
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt;" role=3D"presentation" class=3D"elementToProof">
suffixBytes&nbsp;may not be used at all (the loadBlock()&nbsp;method may no=
t be called or may return early). The memory used by the array will be comp=
letely wasted</div>
</li><li style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontServi=
ce, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); d=
irection: ltr; list-style-type: decimal;">
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt;" role=3D"presentation" class=3D"elementToProof">
If numSuffixBytes&nbsp;happens to be greater than 128, the current eagerly =
allocated array will be discarded. The memory used by it will be wasted.</d=
iv>
</li></ol>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
And as our heap dump illustrates, these things likely happen very often. To=
 address this problem, it would be sufficient to change the code as follows=
:</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
// Avoid eager construction</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
byte[] suffixBytes;</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<span style=3D"font-weight: 700;">=85</span></div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
<span style=3D"font-weight: 700;">if</span>&nbsp;(suffixByte =3D=3D null ||=
&nbsp;suffixBytes.length &lt; numSuffixBytes) {</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp;&nbsp;// If we need to read more than 128 bytes, increase the array=
=85</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp;&nbsp;// =85 or more precisely, throw away the old array and allocate=
 another one</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
&nbsp; suffixBytes =3D <span style=3D"font-weight: 700;">new byte</span>[Ar=
rayUtil.oversize(numSuffixBytes, 1)];</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
}</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"direction: ltr; line-height: 1.38; margin-top: 0pt; margin-bo=
ttom: 0pt; font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Cal=
ibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class=
=3D"elementToProof">
Note that reducing memory allocation rate results primarily in reduction of=
 CPU usage and/or improved latency. That=92s because each object allocation=
 requires work from the JVM - updating pointers and setting all object byte=
s to zero. And then GCing these objects
 is also CPU-intensive, and results in pausing app threads, which affects l=
atency. However, once memory allocation rate is reduced, it may be possible=
 to also reduce the JVM heap memory. So the ultimate win is going to be in =
both CPU and memory.</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" clas=
s=3D"elementToProof">
Please let us know how we can proceed with this. The proposed change is tri=
vial, and thus maybe it can be done quickly by some established Lucene cont=
ributor. If not, I guess I can make it myself and then hope that it goes th=
rough review and release in reasonable
 time.</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" clas=
s=3D"elementToProof">
<br>
</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" clas=
s=3D"elementToProof">
Misha</div>
<div style=3D"font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, =
Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" clas=
s=3D"elementToProof">
<br>
</div>
</body>
</html>

--_000_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_--

--_004_CH9PR21MB5856015FBFCE6AE8E9F39D05C296ACH9PR21MB5856namp_--