Results 1 to 6 of 6

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

  1. #1
    Member
    Join Date
    Jan 2020
    Location
    Fl
    Posts
    59
    Thanks
    1
    Thanked 3 Times in 3 Posts

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

    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.

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,135
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    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.

  3. Thanks:

    lz77 (16th December 2020)

  4. #3
    Member
    Join Date
    Jan 2020
    Location
    Fl
    Posts
    59
    Thanks
    1
    Thanked 3 Times in 3 Posts
    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

  5. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,135
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    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.

  6. #5
    Member
    Join Date
    Jun 2015
    Location
    Switzerland
    Posts
    976
    Thanks
    266
    Thanked 350 Times in 221 Posts
    Quote Originally Posted by Trench View Post
    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.

  7. Thanks:

    Shelwien (15th December 2020)

  8. #6
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    Quote Originally Posted by Shelwien View Post
    COS - ~50ns
    xchg reg,memory ?

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

Similar Threads

  1. Replies: 13
    Last Post: 16th February 2018, 17:21
  2. De-compressing unknown file (CTF riddle)
    By cr33p in forum Data Compression
    Replies: 14
    Last Post: 20th September 2017, 14:32
  3. Memory Usage vs. Memory Requirements for (De)Compression?
    By comp1 in forum The Off-Topic Lounge
    Replies: 7
    Last Post: 1st June 2015, 05:53
  4. CPU to GPU memory bottleneck
    By boxerab in forum Data Compression
    Replies: 6
    Last Post: 12th June 2014, 20:41
  5. compressing a really small 1k .COM file
    By Rugxulo in forum Data Compression
    Replies: 3
    Last Post: 28th November 2009, 01:32

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •