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)

        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

Reply via email to