Not Fast Enough
After improving LZ77, I ported my improvement to my implementation of the Deflate algorithm. Deflate uses a 32K sliding window and a 258 maximum phrase size, which corresponds to my worst case LZ77 compression test. The Linux program gzip uses the deflate algorithm and can compress my test file in less than 1 second. My improved algorithm still takes 233 seconds. That’s certainly not good enough.
My compression algorithms do not work directly with byte arrays. They are accessing the data through a resizable DataBuffer class. I wonder if the overhead of going through the class interface is causing the problem.
Update:
After pondering the whys of this problem, it occurs to me that DataBuffer is the culprit. My DoCompression() method of the LZ77Compressor class is called with a pointer to a destination DataBuffer called workspace. If NULL, then the compression function is only measuring how many bytes the compressor will compress down to. If set, then the results are written to the workspace.
When I compare the DoCompression() function with and without a NULL pointer, then the function call that takes a valid pointer, which will cause writes to the destination DataBuffer, takes twice as long. Gee, a second DataBuffer gets involved, with a second set of I/O operations, and the time to execute takes twice as long. Hmmmmm……
Update #2:
I rewrote my LZ77Compressor::DoCompression() function to operate on raw byte arrays instead of going through the DataBuffer class. When I did that, the 15+5 compression shrank from 233 sec. to 17 sec. I am definitely going to have to rethink my design.