On 2021-02-05 Brett Okken wrote:
> I worked this out last night. We need to double how much we copy each
> time by not advancing "back". This actually works even better than
> Arrays.fill for the single byte case also.
This clearly is a good idea in a Java implementation. :-)
I still worry about short copies. If the file is full of tiny
matches/repeats of 1-3 bytes or so, arraycopy can be slower. Such files
aren't typical at all but I don't want to add a corner case where the
performance drops too much.
I came up with the following. I haven't decided yet if I like it.
public void repeat(int dist, int len) throws IOException {
if (dist < 0 || dist >= full)
throw new CorruptedInputException();
int left = Math.min(limit - pos, len);
pendingLen = len - left;
pendingDist = dist;
int back = pos - dist - 1;
if (back < 0) {
// We won't get here if the dictionary isn't full.
assert full == bufSize;
// The distance wraps around to the end of the cyclic dictionary
// buffer. Here we will never copy more than dist + 1 bytes
// and so the copying won't repeat from its own output. Thus,
// we can always use arraycopy safely.
back += bufSize;
int copySize = Math.min(bufSize - back, left);
assert copySize <= dist + 1;
System.arraycopy(buf, back, buf, pos, copySize);
pos += copySize;
back = 0;
left -= copySize;
if (left == 0)
return;
}
assert back < pos;
assert left > 0;
do {
// Determine the number of bytes to copy on this loop iteration:
// copySize is set so that the source and destination ranges
// don't overlap. If "left" is large enough, the destination
// range will start right after the last byte of the source
// range. This way we don't need to advance "back" which
// allows the next iteration of this loop to copy (up to)
// twice the number of bytes.
int copySize = Math.min(left, pos - back);
// With tiny copy sizes arraycopy is slower than a byte-by-byte
// loop. With typical files the difference is tiny but with
// unusual files this can matter more.
if (copySize < 4) {
int i = 0;
do {
buf[pos + i] = buf[back + i];
} while (++i < copySize);
} else {
System.arraycopy(buf, back, buf, pos, copySize);
}
pos += copySize;
left -= copySize;
} while (left > 0);
if (full < pos)
full = pos;
}
--
Lasse Collin | IRC: Larhzu @ IRCnet & Freenode
