[xz-devel] Re: java LZDecoder small improvement

[Brett Okken]

I have played with this quite a bit and have come up with a slightly
modified change which does not regress for the smallest of the sample
objects and shows a nice improvement for the 2 larger files.

Here is baseline benchmark on 1.8:
jdk 11 64 bit 1.8 BASELINE
Benchmark                                     (file)  Mode  Cnt
Score   Error  Units
XZDecompressionBenchmark.decompress  ihe_ovly_pr.dcm  avgt    3
0.751 ± 0.145  ms/op
XZDecompressionBenchmark.decompress       image1.dcm  avgt    3
427.542 ± 7.724  ms/op
XZDecompressionBenchmark.decompress        large.xml  avgt    3
286.265 ± 2.841  ms/op


And here are the results after modifications:
Benchmark                                     (file)  Mode  Cnt
Score    Error  Units
XZDecompressionBenchmark.decompress  ihe_ovly_pr.dcm  avgt    3
0.751 ±  0.022  ms/op
XZDecompressionBenchmark.decompress       image1.dcm  avgt    3
396.706 ± 13.298  ms/op
XZDecompressionBenchmark.decompress        large.xml  avgt    3
245.282 ±  3.709  ms/op



diff --git a/src/org/tukaani/xz/lz/LZDecoder.java
b/src/org/tukaani/xz/lz/LZDecoder.java
index 85b2ca1..da0ec98 100644
--- a/src/org/tukaani/xz/lz/LZDecoder.java
+++ b/src/org/tukaani/xz/lz/LZDecoder.java
@@ -12,6 +12,7 @@ package org.tukaani.xz.lz;

 import java.io.DataInputStream;
 import java.io.IOException;
+
 import org.tukaani.xz.ArrayCache;
 import org.tukaani.xz.CorruptedInputException;

@@ -94,13 +95,29 @@ public final class LZDecoder {
         int back = pos - dist - 1;
         if (dist >= pos)
             back += bufSize;
-
-        do {
-            buf[pos++] = buf[back++];
+        //many times there is only exactly 1 byte to copy
+        //optimize for that use case
+        buf[pos++] = buf[back++];
+        --left;
+        //then handle in bulk if there is work remaining
+        while (left > 0) {
             if (back == bufSize)
                 back = 0;
-        } while (--left > 0);
-
+            //it is possible for the "repeat" to include content which is going
+            //to be generated here so we have to limit ourselves to how much
+            //data is already in the buffer (i.e. pos - back). It is also
+            //possible that "back" can actually be forward in the buffer from
+            //position, in which case that comparison does not matter
+            int toCopy = Math.min(left, bufSize - back);
+            int tmp = pos - back;
+            if (tmp < toCopy && tmp > 0) {
+                toCopy = tmp;
+            }
+            System.arraycopy(buf, back, buf, pos, toCopy);
+            pos += toCopy;
+            back += toCopy;
+            left -= toCopy;
+        }
         if (full < pos)
             full = pos;
     }