Speed Efficiency of Decompression Algorithm

Question

I've rewritten a piece of Javascript in Python 3.7 that decompresses a file compressed in a specific format. The project that I got this from is available here.

The code I've come up with is as close an analog as I could interpret (I'm not the best at Javascript).

def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = b''

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output += chunk

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat
                output += repeat_chunk

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output += chunk
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return output

where data is a byte string read in from a file opened in binary mode. My code and the original code both produce the same output, but where the original code takes only a few seconds to execute, mine takes ~10 minutes on the same file. Testing with multiple files yields similar benchmarks. My specific efficiency question is: What can I do to increase the speed of execution of this script on the same system while maintaining output accuracy?

I'm open to the idea of multithreading/multiprocessing though I don't think it's possible due to the nature of this compression type.

Example file, though it's very small and runs quickly on both implementations. It must be fed to decompress_lz2 as bytes.

Answer 1

I can't test it at the moment, but I suspect that the culprit is

output += chunk

in a couple of places. This line potentially has O(n^2) complexity because of copying output to a new place in memory that has room to append chunk to it. It would be more efficient to append chunk to a list and then use b''.join() at the end to concatenate all the chunks.

def decompress_lz2(data):
    global loop_count
    lb_len = 0
    lb_dist = 0
    escape = 0x16

    off_input = 0

    output = []               # <-- make output a list

    while off_input < len(data):
        loop_count += 1
        if lb_len:
            off_output = len(output) - lb_dist

            repeat = max(0, off_output + lb_len - len(output))

            chunk = output[off_output:off_output + lb_len - repeat]
            output.append(chunk)  # <-- changed '+=' to '.append()'

            if repeat:
                repeat_chunk = bytes([chunk[-1]]) * repeat

                output.append(repeat_chunk)  # <-- changed '+=' to '.append()'

            lb_len = 0

        if escape:
            chunk = data[off_input:off_input + escape]
            output.append(chunk)  # <-- changed '+=' to '.append()'
            off_input += escape
            escape = 0

        flag = data[min(off_input, len(data) - 1)]
        off_input += 1

        lb_len = flag >> 5

        if lb_len:
            if lb_len == 7:
                while True:
                    next_ = data[off_input]
                    off_input += 1
                    lb_len += next_
                    if next_ != 0xff:
                        break

            lb_len += 2

            lb_dist = (flag & 0x1F) << 8
            lb_dist += (1 + data[off_input])
            off_input += 1

            if lb_dist == 0x2000:
                lb_dist += (data[off_input] << 8)
                off_input += 1
                lb_dist += data[off_input]
                off_input += 1

        else:
            escape = flag + 1

    return b''.join(output)  # <-- concatenate the chunks