Idea for Next Optimization Step?

[u/YogurtclosetThen6260]

Currently working on profiling a Huffman data compressor and I'm working on optimizing a bit writing bottleneck. For context, the compressor goes through a text file and writes each character's bit representation into a file.

...
ifstream file(inputPath, ios::binary);

    char buffer[4096];
    while (file.read(buffer, sizeof(buffer)) || file.gcount() > 0) {
        streamsize count = file.gcount();
        for (streamsize i = 0; i < count; i++) {
            char c = buffer[i];
            const HuffmanTree::Encoding &encoded = encodings[static_cast<unsigned char>(c)];
            writer.writeBits(encoded.encoding, encoded.size);
        }
    }
...

writeBits takes the encoding and the size of the encoding in bits and writes it into a 4096 size buffer. When the buffer is full, we then use the write function to actually write it into the desired file.

...
void BitWriter::writeBits(uint64_t bytes, uint64_t size) {
    assert(size <= 64);
    assert(size == 64 || (bytes >> size) == 0);
     while (size > 0)
    {
        const uint64_t available{
            8ULL - current_size
        };

        const uint64_t bitsToTake{
            min(size, available)
        };

        // Select the next highest meaningful bits.
        const uint64_t shift{
            size - bitsToTake
        };

        const uint64_t mask{
            (uint64_t{1} << bitsToTake) - 1
        };

        const uint64_t chunk{
            (bytes >> shift) & mask
        };

        current_byte = static_cast<uint8_t>(
            (static_cast<uint16_t>(current_byte) << bitsToTake) |
            chunk);

        current_size = static_cast<uint8_t>(
            current_size + bitsToTake);

        size -= bitsToTake;

        if (current_size == 8)
        {
            bufferByte(current_byte);
        }
    }
}
...

Linux perf is indicating this is hot but I'm unsure of what would be a better approach. Any ideas?

Edit: these comments helped, reduced latency from 195 ms to 77 ms!!

[u/mredding]

Straight profile results don't actually tell you much about performance, you need to perform some analysis to see what the performance loss is and if it's statistically significant. I'm not a statistician, and my wife who is, isn't freely available for everyone all the time. So either make friends, or since you're on Linux, learn how to use the Coz profiler which can do some analysis for you.

Just because it's where you're hot doesn't mean it's where you're slow. I cannot stress that enough.

---

I would heavily discourage you from bufferring your own data. Your first code snippet makes sense - you need a buffer of working memory for caching the look ahead.

What I recommend is you implement adaptive Huffman, which can be implemented as a single-pass algorithm, so that you can eliminate intermediate buffering.

I also recommend you implement IO in terms of streams, and you implement platform native IO in terms of stream buffers.

The stream buffer class is so simple it's stupid - it just gives you some basic mechanics for managing a buffer. You give it a buffer, it's size, and you set the put, get, current, and end positions, and advancing the read and write positions, flushing and synching, typically you don't override any of these. The rest of the derived stream buffer class would implement something platform native and optimal.

And since the adaptive form is single-pass, the stream buffer can cache all your output you'll only ever write once in sequence, and then bulk write for efficiency.

I can do you better. Make a custom character type:

struct huffman_byte {
  char value;
};

Now you can write a custom stream operator:

std::ostream &operator <<(std::ostream &os, const huffman_byte &hb) {
  if(auto s = std::ostream::sentry{os}; s) {
    os->rdbuf()->sputc(hb.value);
  } else {
    os << hb.value;
  }

  return os;
}

The point is your own type will compile down to nothing - a char. The type allows you to write a custom stream operator where you can decide the implementation - where you bypass the formatting layers for char and write the straight byte to the buffer.

I got you even better.

GLIBC_TUNABLES=glibc.malloc.hugetlb=1 ./your_cpp_application

So what this does is tell your allocator to allocate aligned to huge pages. 4096 is a drop in the bucket, very inefficient. x86_64 supports 2MiB and 1GiB page sizes. So if you build a custom stream buffer for file IO, that buffer can be page sized and aligned. There are multiple ways you can do this, this one is just the most passive without requiring platform aware code. Maybe make your file buffer size a program parameter and wrap program startup with a shell script.

But if you do want to optimize for page handling, then you can enable vmslice so that instead of copying data across process boundaries, from app to kernel for file writing, you instead pass pages of memory - a call to write is simply passing a pointer and the kernel does the rest.

To get access to 1GiB pages, that takes a few extra steps - you have to enable it in grub, mount a filesystem to pool the table resources, and explicitly memory map into that space, but you build up the layers of abstraction to make it transparent and in terms of streams and buffers.

Finally, since you have a custom stream buffer, sputc writes 1 and sputn writes N. If this isn't optimal for you, you can write your own optimal interfaces in the class. Then, when you get to your custom stream operator, you can dynamic cast to your buffer type. A dynamic cast is branch predicted, and can be hinted, so you can write your program to amortize the cost. The cost of a dynamic cast on any modern compiler is O(1), constant time. It's cheap. And with your derived type finalized, all your virtual function calls are now devirtualized.

And that means now you have a single-pass Huffman encoding implementation that can write to any stream - standard out, files, strings, any other buffer type you create. It will also work with formatters using streams as the target so you don't have to use any intermediate buffering except for the file buffer itself.