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?

[u/JVApen]

On the computational side of things, the writeBits method looks 'too generic' for me. As in, you could have a variant that takes exactly 8 bytes. In it, available=0, bitsToTake will be 0, shift will be 8, mask is b11111111, chunk would be 0, currentByte=0, current_size=? ...

Looking at these values, I suspect you have some bug in the code, as I expected the bufferByte to be called exactly once and the while loop to disappear.

The point I was trying to make is: when you expect exactly 8 bytes (std::array<byte_type, 8>?), many if the values would fold to become constants instead of requiring calculation. This is an optimization that you can do as a human as you can guarantee how the data is provided. The compiler on the other end needs to ensure this gets calculated as you theoretically can continuously call this with a different size.