What takes the most CPU and Memory when compressing a file?

[Trench]

When a file is compressed it has different stages which slows it down. What would be the part that makes it slow down the most for cpu and for memory. It does not have to use both at the same time.

Does looking for what to compress take up time, the size, the conversation. the formula or a specific part in it, the searching, the dictionary size, etc?

I assume every file compression is different but a general example.

[Shelwien]

The slowest things to compute are transcendental functions - in compression that's most frequently log/exp.
Division is relatively slow too.

Memory is slow in general - any unpredictable access outside of cache could be slower than some matrix multiplication.
You can make it even slower by accessing multiple addrs with same page offset (addr mod 4096) - caches have problems with that.

[Trench]

In your guess roughly how slow is transcendental functions compared to division as a whole in a file compression?
And how slow are they compared to the rest when compressing?
Thanks

[Shelwien]

As a rough estimation:
ADD/SUB - 0.1ns
MUL - 1-2ns
DIV - 5-7ns
COS - ~50ns
However the specific timings really depend on specific CPU and desired precision.
In compression, these slow functions (even just division) are usually replaced with a precalculated table for a limited set of inputs.

[Jyrki Alakuijala]

When a file is compressed it has different stages which slows it down.

For very fast compressors: converting symbols to bytes or bits, just shuffling memory

For fast compressors: building entropy codes -- having to scan through each block twice (first to build an entropy code, then to use it)

For LZ77ish medium speed compressors: searching the matches

For slow LZ77ish compressors: figuring out and computing optimal contexts, computing block splitting

I consider that searching the matches is likely the most critical pain-point in modern lossless compression.

[lz77]

COS - ~50ns

xchg reg,memory ?

Calculating number of additionally matched bytes is innermost loop in fast lz77.