Benchmarking compression programs

Compression algorithms can be broadly categorized into three groups based on their typical performance and compression ratio:

• Low compression: lz4, snappy, Oodle Selkie.
• Medium compression: zlib, zstd, brotli, Oodle Kraken. These provide the sweet spot for many general-purpose tasks. These codecs typically need entropy encoding to achieve higher ratio than lz4.
• High: LZMA, bzip2, bzip3, bsc, zpaq, kanzi, Oodle Leviathan.

Low compression Codecs in this category prioritize speed above all else. The compression and compression speeds are comparable. They are designed to decompress so quickly that they don't introduce a noticeable delay when reading data from storage like solid-state drives. These codecs typically producing byte-aligned output and often skip the final step of entropy encoding, which, while crucial for high compression, is computationally intensive. They are excellent choices for applications where latency is critical, such as kernel features like zswap.

Medium compression This is the sweet spot for many tasks. They achieve better compression ratio by employing entropy encoding.

zstd has emerged as a clear leader, gaining popularity and effectively supplanting older codecs like the venerable zlib.

High Compression They are designed to squeeze every last bit of redundancy out of the data, often at the cost of significantly longer compression and decompression times, and large memory usage. They are perfect for archival purposes or data distribution where the files are compressed once and decompressed infrequently. Codecs typically implement strong transforms, even very specific ones like branch/call/jump filters for machine code.

High-compression codecs, such as LZMA and zpaq, typically employ powerful data transforms to increase redundancy. This can include general-purpose transforms like Burrows-Wheeler, but also highly specific ones like branch/call/jump filters for machine code. Many modern codecs in this category also use advanced entropy encoding techniques like the Range variant of Asymmetric Numeral Systems (rANS).

---

This categorization is loose. Many modern programs offer a wide range of compression levels that allow them to essentially span multiple categories. For example, a high-level zstd compression can achieve a ratio comparable to xz (a high-compression codec) by using more RAM and CPU. While zstd's compression speed or ratio is generally lower, its decompression speed is often much faster than that of XZ.

Benchmarking

I want to benchmark a few compression programs. To ensure fairness, each program is built with consistent compiler optimizations, such as -O3 -march=native. Below is a Ruby program that downloads and compiles multiple compression utilities, then benchmarks their compression and decompression performance on a specified input file, finally generates a HTML file with Chart.js plots. The program has several notable features:

• Adding new compressors is easy: just modify COMPRESSORS.
• Benchmark results are cached in files named cache_$basename_$digest.json, allowing reuse of previous runs for the same input file.
• Adding a new compression level does not invalidate existing benchmark results for other levels.

I've selected these programs:

• lz4
• zstd: By default it creates a worker thread to overlap the work with IO. You might want to specify --single-thread to disable this "cheating".
• brotli
• bzip3
• xz
• kanzi

I'd like to test lzham (not updated for a few years), but I'm having trouble getting it to compile due to a cstdio header issue.

#!/usr/bin/env ruby
# This program downloads and builds several compression utilities, then benchmarks their compression and decompression
# performance on a specific input file.
require 'benchmark'
require 'digest'
require 'etc'
require 'fileutils'
require 'json'
require 'net/http'
require 'tempfile'
require 'uri'

JOBS = Etc.nprocessors

COMPRESSORS = {
  'brotli' => {
    url: 'https://github.com/google/brotli/archive/refs/tags/v1.1.0.tar.gz',
    build_dir: 'brotli-1.1.0',
    build_commands: ['cmake -GNinja -S. -Bout -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=install -DBROTLI_DISABLE_TESTS=on -DCMAKE_C_FLAGS="-march=native"', 'ninja -C out install'],
    levels: [1, 3, 5, 9],
    compress: ->exe, level, i, o { "#{exe} -c '#{i}' > '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -c '#{i}' > '#{o}'" }
  },
  'bzip3' => {
    url: 'https://github.com/kspalaiologos/bzip3/releases/download/1.5.3/bzip3-1.5.3.tar.gz',
    build_dir: 'bzip3-1.5.3',
    build_commands: ['./configure --prefix=$PWD/install CFLAGS="-O3 -march=native"', "make -j #{JOBS} install"],
    levels: [1],
    compress: ->exe, level, i, o { "#{exe} -c '#{i}' > '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -c '#{i}' > '#{o}'" },
  },
  'kanzi' => {
    url: 'https://github.com/flanglet/kanzi-cpp/archive/refs/tags/2.4.0.tar.gz',
    build_dir: 'kanzi-cpp-2.4.0',
    build_commands: ['cmake -GNinja -Ssrc -Binstall/bin -DCMAKE_CXX_FLAGS="-march=native"', 'ninja -C install/bin kanzi'],
    levels: 1..9,
    compress: ->exe, level, i, o { "#{exe} -c -l #{level} -v 0 -f -i '#{i}' -o '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -v 0 -f -i '#{i}' -o '#{o}'" }
  },
  'lz4' => {
    url: 'https://github.com/lz4/lz4/releases/download/v1.10.0/lz4-1.10.0.tar.gz',
    build_dir: 'lz4-1.10.0',
    build_commands: ["make -j #{JOBS} CFLAGS='-O3 -march=native' PREFIX=$PWD/install install"],
    levels: 1..12,
    compress: ->exe, level, i, o { "#{exe} -#{level} -q -c '#{i}' > '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -q -c '#{i}' > '#{o}'" }
  },
  'xz' => {
    url: 'https://tukaani.org/xz/xz-5.8.1.tar.gz',
    build_dir: 'xz-5.8.1',
    build_commands: ['./configure --prefix=$PWD/install CFLAGS="-O3 -march=native"', "make -j #{JOBS} install"],
    levels: 1..6,
    compress: ->exe, level, i, o { "#{exe} -#{level} -c '#{i}' > '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -c '#{i}' > '#{o}'" }
  },
  'zstd' => {
    url: 'https://github.com/facebook/zstd/releases/download/v1.5.7/zstd-1.5.7.tar.gz',
    build_dir: 'zstd-1.5.7',
    build_commands: ['cmake -GNinja -Sbuild/cmake -Bout -DCMAKE_INSTALL_PREFIX=install -DCMAKE_C_FLAGS="-march=native"', 'ninja -C out install'],
    levels: [*(1..6), 9, 13, 16, 19],
    compress: ->exe, level, i, o { "#{exe} -#{level} -q -c '#{i}' > '#{o}'" },
    decompress: ->exe, i, o { "#{exe} -d -q -c '#{i}' > '#{o}'" }
  },
}

class CompressorBuilder
  def initialize(work_dir)
    @work_dir = File.expand_path(work_dir)
    FileUtils.mkdir_p(@work_dir)
  end

  def build_all
    COMPRESSORS.each do |name, config|
      bin_dir = File.join(@work_dir, config[:build_dir], 'install/bin')
      if begin !Dir.empty?(bin_dir) rescue false end
        puts "✓ #{name} already built"
      else
        download_and_extract(name, config)
        build_compressor(name, config)
      end

      if Dir.exist?(bin_dir)
        program = File.join(bin_dir, name)
        unless File.exist? program
          binaries = Dir.glob(File.join(bin_dir, '*')).select { |f| File.executable?(f) }
          raise "Compressor not found, available executables: #{binaries.map { |b| File.basename(b) }.join(', ')}"
        end
        puts "  Executable: #{program}"
        config[:program] = program
      end
    end
  end

  private

  def download_and_extract(name, config)
    filename = File.basename(config[:url])
    filepath = File.join(@work_dir, filename)

    unless File.exist?(filepath)
      puts "Downloading #{name}..."
      download_file(config[:url], filepath)
    end

    extract_path = File.join(@work_dir, config[:build_dir])
    unless Dir.exist?(extract_path)
      puts "Extracting #{filename}..."
      if filename.end_with? 'zip'
        system("unzip", filepath, "-d", @work_dir) or
          raise "Failed to extract #{filepath}"
      else
        system("tar", "-xf", filepath, "-C", @work_dir) or
          raise "Failed to extract #{filepath}"
      end
    end
  end

  def download_file(url, filepath)
    uri = URI(url)

    Net::HTTP.start(uri.host, uri.port, use_ssl: uri.scheme == 'https') do |http|
      request = Net::HTTP::Get.new(uri)

      # Follow redirects
      response = http.request(request)
      case response
      when Net::HTTPRedirection
        download_file(response['location'], filepath)
        return
      when Net::HTTPSuccess
        File.open(filepath, 'wb') { |f| f.write(response.body) }
      else
        raise "Failed to download #{url}: #{response.code} #{response.message}"
      end
    end
  end

  def build_compressor(name, config)
    build_path = File.join(@work_dir, config[:build_dir])
    unless Dir.exist?(build_path)
      raise "Build directory not found: #{build_path}"
    end

    puts "Building #{name}..."
    Dir.chdir(build_path) do
      config[:build_commands].each do |command|
        puts "Running: #{command}"
        success = system(command)
        unless success
          raise "Build command failed: #{command}"
        end
      end
    end
  end
end

class CompressorBenchmark
  def initialize(input_file, options)
    @input_file = input_file
    @results = {}
    @invalidate_cache = options[:invalidate_cache] || false

    unless File.exist?(@input_file)
      puts "Error: Input file '#{@input_file}' not found!"
      exit 1
    end

    puts "Input file: #{@input_file}"
    @input_size = File.size(@input_file)
    @input_hash = Digest::SHA256.file(@input_file).hexdigest[0..16]
    @cache_file = "cache_#{File.basename(@input_file)}_#{@input_hash}.json"
    puts "File size: #{@input_size} bytes"
    puts "Cache file: #{@cache_file}"

    if @invalidate_cache && File.exist?(@cache_file)
      File.delete(@cache_file)
      puts "Cache invalidated."
    end

    # Load cached results
    if File.exist?(@cache_file)
      begin
        cached_data = JSON.parse(File.read(@cache_file))
        @results = cached_data.transform_values do |compressor_data|
          compressor_data.map { |point| point.transform_keys(&:to_sym) }
        end
        puts "Loaded cached results for #{@results.keys.join(', ')}"
      rescue JSON::ParserError
        puts "Warning: Corrupted cache file, starting fresh"
        @results = {}
      end
    end
    puts
  end

  def save_cache
    File.open(@cache_file, 'w') do |f|
      f.write(JSON.pretty_generate(@results))
    end
  end

  def run_benchmark
    COMPRESSORS.each do |name, config|
      puts "Testing #{name}..."
      program = config[:program]
      compress_method = config[:compress]
      decompress_method = config[:decompress]
      executed = false
      @results[name] ||= []

      config[:levels].each do |level|
        if @results.key?(name) && @results[name].any? {|x| x[:level] == level}
          next
        end

        print "  Level #{level}... "
        executed = true
        compressed_size = nil
        compress_time = nil
        decompress_time = nil

        # Test compression
        Tempfile.create('compressed') do |compressed_file|
          compress_time = Benchmark.realtime do
            cmd = compress_method.call(program, level, @input_file, compressed_file.path)
            unless system(cmd, out: File::NULL, err: File::NULL)
              puts "Compression failed: #{cmd}"
              exit 2
            end
          end
          compressed_size = File.size(compressed_file.path)

          # Test decompression
          Tempfile.create('decompressed') do |decompressed_file|
            decompress_time = Benchmark.realtime do
              cmd = decompress_method.call(program, compressed_file.path, decompressed_file.path)
              unless system(cmd, out: File::NULL, err: File::NULL)
                puts "Decompression failed: #{cmd}"
                exit 2
              end
            end

            # Verify decompression
            decompressed_size = File.size(decompressed_file.path)
            if decompressed_size != @input_size
              puts "Decompression verification failed: size mismatch (#{decompressed_size} != #{@input_size})"
              exit 2
            end
          end
        end

        compress_speed = @input_size * 1e-6 / compress_time
        decompress_speed = @input_size * 1e-6 / decompress_time
        compression_ratio = @input_size.to_f / compressed_size

        @results[name] << {
          level: level,
          compress_speed: compress_speed,
          decompress_speed: decompress_speed,
          ratio: compression_ratio,
          compressed_size: compressed_size
        }

        puts "C: #{compress_time.round(3)}s (#{compress_speed.round(1)} MB/s), D: #{decompress_time.round(3)}s (#{decompress_speed.round(1)} MB/s), Size: #{compressed_size} bytes"
        # Save cache after each compressor to avoid losing work
        save_cache
      end

      puts "Skipping #{name} (using cached results)..." unless executed
      puts
    end
  end

  def generate_html_plot
    data_json = JSON.generate(@results)

    html_content = <<~HTML
      <!DOCTYPE html>
      <html>
      <head>
        <title>Compression Performance Analysis</title>
        <script src="https://cdn.jsdelivr.net/npm/chart.js"></script>
        <style>
          .container {
            max-width: 1400px;
            margin: 0 auto;
            background: white;
            padding: 30px;
            border-radius: 10px;
            box-shadow: 0 2px 10px rgba(0,0,0,0.1);
          }
          .chart-row {
            display: flex;
            gap: 20px;
            margin-bottom: 30px;
          }
          .chart-container {
            flex: 1;
            height: 400px;
            position: relative;
          }
          .stats-table {
            width: 100%;
            border-collapse: collapse;
            margin-top: 20px;
          }
          .stats-table th, .stats-table td {
            padding: 8px 12px;
            text-align: left;
            border-bottom: 1px solid #ddd;
            font-size: 0.9em;
          }
          .stats-table th {
            background-color: #34495e;
            color: white;
            font-weight: bold;
          }
          .stats-table tr:nth-child(even) {
            background-color: #f2f2f2;
          }
          .cache-info {
            background: #d5dbdb;
            padding: 15px;
            border-radius: 5px;
            margin-bottom: 20px;
            font-size: 0.9em;
          }
        </style>
      </head>
      <body>
        <div class="container">
          <h1>Compression & Decompression Performance Analysis</h1>

          <div class="cache-info">
            <strong>Input file:</strong> #{File.basename(@input_file)} (#{(@input_size/1024.0/1024.0).round(2)} MB)<br>
            <strong>File hash:</strong> #{@input_hash}<br>
            <strong>Cache file:</strong> #{@cache_file}<br>
            <strong>Compressors tested:</strong> #{@results.keys.join(', ')}
          </div>

          <div class="chart-row">
            <div class="chart-container">
              <canvas id="compressionChart"></canvas>
            </div>
            <div class="chart-container">
              <canvas id="decompressionChart"></canvas>
            </div>
          </div>

          <div class="chart-container" style="height: 500px;">
            <canvas id="combinedChart"></canvas>
          </div>

          <table class="stats-table">
            <thead>
              <tr>
                <th>Compressor</th>
                <th>Level</th>
                <th>Compress Speed (MB/s)</th>
                <th>Decompress Speed (MB/s)</th>
                <th>Compression Ratio</th>
                <th>Compressed Size (KB)</th>
              </tr>
            </thead>
            <tbody>
              #{@results.flat_map do |compressor, data|
                data.map do |point|
                  size_kb = (point[:compressed_size] / 1024.0).round(1)
                  "<tr><td style=\"color: var(--#{compressor}-color); font-weight: bold;\">#{compressor}</td><td>#{point[:level]}</td><td>#{point[:compress_speed].round(2)}</td><td>#{point[:decompress_speed].round(2)}</td><td>#{point[:ratio].round(2)}</td><td>#{size_kb}</td></tr>"
                end
              end.join("\n              ")}
            </tbody>
          </table>
        </div>

        <script>
          const rawData = #{data_json};

          function MurmurOAAT32(key) {
            let h = 3323198485n;
            for (let i = 0; i < key.length; i++) {
              h ^= BigInt(key.charCodeAt(i));
              h = (h * 0x5bd1e995n) & 0xFFFFFFFFn;
              h ^= h >> 15n;
            }
            return h;
          }

          // Generate dynamic colors and create CSS variables
          const compressorNames = Object.keys(rawData);
          const colors = {};
          compressorNames.forEach(name => {
            const rn = MurmurOAAT32(name);
            const sat = 40n + rn % 40n;
            const hue = (rn / 50n) % 360n;
            const color = `hsl(${hue}, ${sat}%, 50%)`;
            colors[name] = color;
            document.documentElement.style.setProperty(`--${name}-color`, color);
          });

          // Compression Speed vs Ratio
          const compressionDatasets = compressorNames.map(name => {
            const dataPoints = rawData[name].map(d => ({
              name: name,
              x: d.compress_speed,
              y: d.ratio,
              level: d.level
            }));
            return {
              label: name,
              data: dataPoints,
              backgroundColor: colors[name],
              borderColor: colors[name],
              pointRadius: 5,
              pointHoverRadius: 8,
              showLine: false
            };
          });

          // Decompression Speed vs Ratio
          const decompressionDatasets = compressorNames.map(name => {
            const dataPoints = rawData[name].map(d => ({
              name,
              x: d.decompress_speed,
              y: d.ratio,
              level: d.level
            }));
            return {
              label: name,
              data: dataPoints,
              backgroundColor: colors[name],
              borderColor: colors[name],
              pointRadius: 5,
              pointHoverRadius: 8,
              showLine: false
            };
          });

          // Combined Speed Comparison
          const combinedDatasets = compressorNames.map(name => ({
              label: name,
              data: rawData[name].map(d => ({
                name,
                x: d.compress_speed,
                y: d.decompress_speed,
                level: d.level,
                ratio: d.ratio
              })),
              backgroundColor: colors[name],
              borderColor: colors[name],
              pointRadius: 6,
              pointHoverRadius: 8,
              showLine: false,
              pointStyle: 'circle'
          }));

          const commonTooltipCallback = (context) => {
            const point = context.raw;
            return [
              `${point.name} ${point.level}`,
              `Speed: ${point.x?.toFixed(2) || 'N/A'} MB/s`,
              `Ratio: ${point.y?.toFixed(2) || 'N/A'}`,
              point.ratio ? `Ratio: ${point.ratio.toFixed(2)}x` : ''
            ].filter(Boolean);
          };

          // Create compression chart
          new Chart(document.getElementById('compressionChart'), {
            type: 'scatter',
            data: { datasets: compressionDatasets },
            options: {
              responsive: true,
              maintainAspectRatio: false,
              plugins: {
                title: { display: true, text: 'Compression Speed vs Ratio', font: { size: 16 } },
                legend: { display: true, position: 'top' },
                tooltip: { callbacks: { label: commonTooltipCallback } }
              },
              scales: {
                x: { title: { display: true, text: 'Compression Speed (MB/s)' } },
                y: { title: { display: true, text: 'Compression Ratio' } }
              }
            }
          });

          // Create decompression chart
          new Chart(document.getElementById('decompressionChart'), {
            type: 'scatter',
            data: { datasets: decompressionDatasets },
            options: {
              responsive: true,
              maintainAspectRatio: false,
              plugins: {
                title: { display: true, text: 'Decompression Speed vs Ratio', font: { size: 16 } },
                legend: { display: true, position: 'top' },
                tooltip: { callbacks: { label: commonTooltipCallback } }
              },
              scales: {
                x: { title: { display: true, text: 'Decompression Speed (MB/s)' } },
                y: { title: { display: true, text: 'Compression Ratio' } }
              }
            }
          });

          // Create combined speed comparison chart
          new Chart(document.getElementById('combinedChart'), {
            type: 'scatter',
            data: { datasets: combinedDatasets },
            options: {
              responsive: true,
              maintainAspectRatio: false,
              plugins: {
                title: { display: true, text: 'Compression vs Decompression Speed', font: { size: 16 } },
                legend: {
                  display: true,
                  position: 'top',
                  filter: function(legendItem) {
                    return !legendItem.text.includes('(levels)');
                  }
                },
                tooltip: {
                  callbacks: {
                    label: (context) => {
                      const point = context.raw;
                      return [
                        `${point.name} ${point.level}`,
                        `C: ${point.x.toFixed(2)} MB/s`,
                        `D: ${point.y.toFixed(2)} MB/s`,
                        `Ratio: ${point.ratio.toFixed(2)}x`
                      ];
                    }
                  }
                }
              },
              scales: {
                x: { title: { display: true, text: 'Compression Speed (MB/s)' } },
                y: { title: { display: true, text: 'Decompression Speed (MB/s)' } }
              }
            }
          });
        </script>
      </body>
      </html>
    HTML

    File.open('compression_comparison.html', 'w') { |f| f.write(html_content) }
    puts "Created compression_comparison.html"
  end
end

def show_usage
  puts "Usage: #{$0} [options] <input_file>"
  puts
  puts "Options:"
  puts "  -i                   Delete cached results and rerun all benchmarks"
  puts "  --help               Show this help message"
end

options = {}
input_file = nil

ARGV.each do |arg|
  case arg
  when '-i'
    options[:invalidate_cache] = true
  when '--help', '-h'
    show_usage
    exit 0
  when /^-/
    puts "Error: Unknown option '#{arg}'"
    show_usage
    exit 1
  else
    if input_file.nil?
      input_file = arg
    else
      puts "Error: Multiple input files specified"
      show_usage
      exit 1
    end
  end
end

if input_file.nil?
  puts "Error: No input file specified"
  show_usage
  exit 1
end

CompressorBuilder.new('compressor_builds').build_all

benchmark = CompressorBenchmark.new(input_file, options)
benchmark.run_benchmark
benchmark.generate_html_plot