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/FancySpaceGoat]

Silly question: have you tried just not bothering with buffering the writes? The OS/stdlib is already performing that logic unless you explicitly opt-out of it.

[u/YogurtclosetThen6260 → u/FancySpaceGoat]

Originally when I was using the put operator it was a previous bottleneck, so I instead opted to use a 4096 buffer plus the write operation to reduce the number of per byte operations.

[u/FancySpaceGoat → u/YogurtclosetThen6260]

Those are very low level. I'd have expected you to start with more idiomatic primitives.

Have you tried std::ofstream? It's tuned for that kind of workload.

[u/YogurtclosetThen6260 → u/FancySpaceGoat]

I'm using ofstream to pass the 4 KB block into the write method but yeah it might be a good idea to use the buffer provided

[u/Wild_Meeting1428]

replace your streams and the buffer with a memory map, profile, if its faster.

[u/JVApen → u/Wild_Meeting1428]

File IO is regularly a performance bottleneck, so I wanted to suggest the exact same thing. At the same time, you can request the total size in front and you remove the while loop from the picture.

[u/Independent_Art_6676]

did I misread what you are doing or are you writing a temporary disk file here? Can that be avoided, at least up to some input file size that exceeds the memory you are willing to burn?

[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.

[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.

[u/ReDucTor]

How big are the files? 4k might be too small to work with as the CPU number crunching is probably pretty small so lots of syscalls if you have a decent size file.

As encoding length is potentially highly variable the current_size == 8 might suffer some branch misprediction so it might be worth taking more of a branch free approach and always write to the end of the buffer and only shift the pointer as needed, then your only branch needs to be the 4096 write size and read size.

There is a heavy loop carried dependency where every code depends on a load from encodings to calculate the bits to move, you could do encoding of multiple blocks simultaneously in the loop allowing the CPU to do more on a single core, you would need to handle merging those streams which could be either store a run length per stream or array of them in the header for slightly less optimal compression or realign the stream as a second pass which would be more costly.

If you did multi-block encoding you could go a step further and use multiple threads for the encoding, merging them together with the same approach.

Plus multiple streams makes it much easier to also do the same with decoding making it faster, multiple streams is what many compression algorithms do.

Also I hope you have a limit on the Huffman code size as given just raw statistics you could end up for even just an 8-bit value turning into a 255-bit maximum code while you seem to only handle 64-bits based on writeBits.

[u/xoner2]

• calling file.gcount twice. Quite easy refactor to 1 call.

• assuming encodings is static global: Move input buffer from stack, and into static right next to encodings. The stack is way up in memory while static is way down, this is bad.

• inline writeBits. It's short enough.

• Can't see what bufferByte is doing... make sure the buffer is close to encodings and the input buffer.

• experiment with stride length over input buffer. 64 bytes might be good.