How slow is too slow? How does your code compare to gzip, speed-wise?

Very. An 880k file takes a few minutes to compress on a semi-modern Win11/64 laptop.

Define "semi-modern"; this could mean anything from an Athlon 64 X2 to a Coffee Lake i7.

What’s the purpose of this nit-picking? Every desktop CPU that runs Win11 is likely in the same performance range, by an order of magnitude.

A few minutes for less than 1MB is so slow that I agree it is embarrassingly slow 😉. I just tried gzip on a 4MB file, and it took 0.1 seconds. I would have a look at how it or other open-source compressors (zlib, lzop, zstd, lzip, ...) handle their window search.

I attached the code that compresses using lz77. It is for Digital Mars C and Win32. I believe my laptop is less than four years old. BTW, part of the slowdown I believe is due to my printing the current position in the file being compressed.

How big is your search space for pattern matching? IIRC things like PKZip only search a 32KB window for duplicate strings (since Deflate compression includes something similar to lz77 in it).

I believe the 'hash tables' refers to an algo where you do a single pass of the data, calculating a rolling checksum of strings of fixed length (eg. 4 bytes) and build a table of offsets where each table entry corresponds to a checksum/hash and contains the offset where the matching string was found. So then when you have a string coming into the compressor and you need to know if it is a duplicate of previous data, you hash the first 4 bytes and use that as an index into the table to get the offset. This is much faster than a brute-force search through the previous data. At that point you can verify whether the data actually matches (ie. not a hash collision) and whether the match is longer than the 4-byte minimum. Or maybe the string isn't a duplicate at all, in which case the table entry would be some pre-initialized 'empty' value.

So, if a match is found, start scanning from there, and, if only the first two or three bytes match, scan to there, right? Also, if a match is not found, don't compress with lz77, right?

BTW, I'm using a 60,000-byte window for pattern-matching.

I'm just about ready for the optimization. Are there any other recommendations to speed up lz77 block-searching? I have a method that helps a little but needs an 8k array of bits, where each bit determines whether an associated word was already used. For every lz77 scan, I first check the array to see if the word was already used. If not, don't scan and just return no match. For every byte compressed, set the bit in the array corresponding to the current word. What do you think?

By 'word' you mean 16 bits, right? It sounds like it would speed up the compression. The only thing missing from this approach is any kind of hint on where to scan.

Do you scan beginning with the oldest (lowest address) data? Maybe it would be faster to search in the other direction. (Particularly on CPUs with L1 cache, since more recent data is less likely to have already been ejected from the cache)

By 'word' I do mean 16 bits, and I do scan from the most recent byte first. The last time I tried this technique, it only helped a little. I'm going to apply this now on an 8-bit version. 😀

My idea didn't work. 🙁 And it cost me 8k on an 8-bit system, which is significant. Worse yet, it hurt the compression ratio. 🙁

I was trying a version of LZW, but the compression ratio was very poor. 🙁 I gained a lot of ground with it, but the ratio is still poor. I attached two code snippets of the technique:

I forgot to mention: I'm still trying to process the docs on hash tables. While I'm trying to figure them out, is there anything else I can do to optimize LZ77?

These files are a little dated. I attached more recent copies.