I'm working on a patch.
lzma decompressing speed increases:

baseline: 0.275722 sec
patched:  0.140405 sec
(Uncompressed data size 52.57 MB)


The new algorithm looks like this:

    #define INITIAL_BUFFER_SIZE (16*1024)

    static inline Py_ssize_t
    get_newsize(Py_ssize_t size)
    {
        const Py_ssize_t MB = 1024*1024;
        const Py_ssize_t GB = 1024*1024*1024;

        if (size <= 1*MB) {
            return size << 2;           // x4
        } else if (size <= 128*MB) {
            return size << 1;           // x2
        } else if (size <= 1*GB) {
            return size + (size >> 1);  // x1.5
        } else if (size <= 2*GB) {
            return size + (size >> 2);  // x1.25
        } else {
            return size + (size >> 3);  // x1.125
        }
    }