> With a file with two-byte repeat ("ababababababab"...) it's 50 % slower
> than the baseline. Calling arraycopy in a loop, copying two bytes at a
> time, is not efficient. I didn't try look how big the copy needs to be
> to make the overhead of arraycopy smaller than the benefit but clearly
> it needs to be bigger than two bytes.

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.

I still need to run through 1.8 and 15 to make sure this holds up, but
this implementation is better for all files on jdk 11:

        int back = pos - dist - 1;
        if (dist >= pos)
            back += bufSize;

        buf[pos++] = buf[back++];
        //then handle in bulk if there is work remaining
        while (left > 0) {
            if (back == bufSize)
                back = 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) {
                //if the delta between pos and back is smaller than how much
                //there is to copy, then we can safely repeat it all the way
                //for what is left
                do {
                    System.arraycopy(buf, back, buf, pos, tmp);
                    pos += tmp;
                    left -= tmp;
                    tmp <<= 1;
                } while (left > tmp);
            } else {
                System.arraycopy(buf, back, buf, pos, toCopy);
                pos += toCopy;
                back += toCopy;
                left -= toCopy;

        if (full < pos)
            full = pos;

Reply via email to