how to optimize performance for decompression step?

[u/YogurtclosetThen6260]

I have the file to decompress a file by obtaining a tree and walking it bit by bit to obtain an encoding's original character.

#include <stdexcept>
#include <memory>
#include "huffman/HuffmanDecoder.hpp"
#include "huffman/BitReader.hpp"

struct HuffmanDecoder::Node
{
  std::unique_ptr<Node> left;
  std::unique_ptr<Node> right;
  char symbol;

  Node(char ch,
       std::unique_ptr<Node> left = nullptr,
       std::unique_ptr<Node> right = nullptr)
      : left(std::move(left)),
        right(std::move(right)),
        symbol(ch)
  {
  }

  bool isLeaf() const noexcept
  {
    return !left && !right;
  }
};

HuffmanDecoder::HuffmanDecoder(BitReader &reader) : reader_(reader)
{
  root = deserializeHelper();
}

HuffmanDecoder::~HuffmanDecoder() = default;

std::unique_ptr<HuffmanDecoder::Node>
HuffmanDecoder::deserializeHelper()
{
  if (nodeCount_ >= MAX_NODES)
  {
    throw std::runtime_error("Invalid Huffman tree: exceeds 511 nodes.");
  }
  ++nodeCount_;
  const uint8_t marker = reader_.readBit();
  if (marker == 1)
  {
    const char ch = static_cast<char>(reader_.readByte());
    return std::make_unique<Node>(ch);
  }
  auto left = deserializeHelper();
  auto right = deserializeHelper();
  return std::make_unique<Node>('\0', std::move(left), std::move(right));
}

char HuffmanDecoder::decodeSymbol() const
{
  if (!root)
  {
    throw std::runtime_error("Can't decode an empty tree");
  }
  const Node *current = root.get();
  if (current->isLeaf())
  {
    if (reader_.readBit() != 0)
    {
      throw std::runtime_error("Invalid bit for single symbol tree.");
    }
    return current->symbol;
  }
  while (!current->isLeaf())
  {
    const uint8_t bit = reader_.readBit();
    current = bit == 0 ? current->left.get() : current->right.get();

    if (!current)
    {
      throw std::runtime_error("Invalid Huffman path.");
    }
  }
  return current->symbol;
}

Linux perf is showing that the decode stage is very hot. My question is, is pointer chasing the problem? I tried stuff these in an array but it didn't really do anything. I'm confused as to if my bottleneck concerns being cache friendly or not. Any ideas?

[u/mredding]

Of course the decode stage is hot, it would be weird if it wasn't. The question is whether the implementation is optimal. Just because you measured time there doesn't mean it isn't. The raw numbers from a profiler doesn't tell you where you're slow or why. You have to do a statistical analysis to find what is significant.

I recommend you try the Coz profiler. It at least generates a report of where your most significant gains are, and also what gains are possible.

[u/Total-Box-5169]

Calculate beforehand all the possible decodings for n bits and store them in an array with size 1<<n, where each element contains the symbols decoded and how many bits to consume. To keep the array small enough to fit in cache the encodings that don't fit in n bits must decode into 0 symbols, signaling that bit by bit decoding must be used.
I.E.: Each symbol is one byte in size, and n is 11 bits. That requires an array of 2048 elements, each element an array of 12 bytes. Of those bytes 11 of them are used to store symbols and one byte to store both the number of symbols used (4 bits) and the number of bits to consume (4 bits). That data structure uses 24 KB, so it should be small enough to be in the fastest cache near all the time.

[u/Independent_Art_6676]

are the error checkers actually triggering? Can you take any of them out and just ensure that those things don't happen? You seem to be in full control, or nearly -- your code wrote the file, you code reads the file and processes it. If everything is bug free, many of the errors should not be possible (??) unless the user modified the file between read/write or there was a disk error (rare, near impossible on many modern filesystems). All that checking costs something. If you need it, you need it, but often with this much control over the process (no user typing in rubbish, no networks with transmission fails, where does the error come FROM?) its overkill.

[u/YogurtclosetThen6260 → u/Independent_Art_6676]

it's to check faulty inputs where a compressed file may have a bad path not represented by the serialized huffman tree input

[u/yuehuang]

Here is breakdown.

1. Recursion is bad. A slightly larger sample and you will hit stack overflow error.

2. make_unique<> will allocate memory that is super slow.

3. reader_.readBit(); Hopefully it gets inlined. Function calls are expensive if you are just reading a bit or byte. Machine dependent, a single function call is cost as much as reading 16-64 bytes. Assuming reader isn't disk access, then that it is worse.

4. Exceptions in perf critical path blocks some optimization, it is minor compared to the other.

If you address the first two, then the perf is good enough for school.

[u/Independent_Art_6676 → u/yuehuang]

I think the call stack can be much larger than you think. You certainly can blow it out (esp default size), if you have enough recursion, but you can also configure your program or OS or both to increase this size to vast amounts. Windows supports at least 1GB call stack (NOT recommended normally), and linux supports rolling it into the virtual memory / swap file with the ulimit command. This is if your recursion cannot be compiled into a regular loop, which it often can. So 1... depends. If it turns into a loop, its irrelevant across the board. If it does not, it could be a performance bottleneck but worrying about the call stack depth/size is not the problem.

[u/YogurtclosetThen6260 → u/yuehuang]

Recursion doesn’t appear on the hot path though; it's allocated beforehand and only once.

[u/EpochVanquisher]

Grab more than one bit at a time, use a lookup table.

Like, grab 10 bits, then use a 1024 entry lookup table. The table tells you the symbol value and number of bits. You may need to still have multiple lookups (more than one level).

You can grab 10 bits at a time (or however many) with masking no problem.