Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java - optimize writing values as bits to bytebuffer

I am currently working on some networking code (this is my first server) and had a quick question about optimizing a specific function which writes values as bits and then packs them into a byte. The reason for optimizing this function is because it is used thousands of times each server tick for packing data to be sent to several clients.

An example may serve better in order to explain what the function tries to accomplish: The value 3 can be represented by two bits. In binary, it would look like 00000011. The function would turn this binary value into 11000000. When the function is called again, it would know to start from the 3rd most significant bit (3rd from the right/decimal 32) and write at most up to 6 bits into the current byte. If then there were remaining bits to write, it would start on a new byte.

The purpose of this is to save space if you have multiple values that can be less than byte.

My current function looks like this:

 private ByteBuffer out = ByteBuffer.allocate(1024);
 private int bitIndex = 0;
 /*
  * Value: The value to write
  * Amount: The number of bits to represent the value in.
  */
     public OutputBuffer writeBits(long value, int amount) {
    if (bitIndex != 0) {
        int remainingBits = 8 - bitIndex;
        int bytePos = out.position() - 1;
        byte current = out.get(bytePos);
        int shiftAmount = amount - remainingBits;
        int bitsWritten = amount < remainingBits ? amount : remainingBits;
        int clearShiftAmount = 8 - bitsWritten + 56;

        byte b;
        if (shiftAmount < 0) {
            b = (byte) (current | (value << remainingBits - amount));
        } else {
            //deal with negative values
            long temp = (value >> shiftAmount);
            temp =  (temp << clearShiftAmount);
            temp = (byte) (temp >>> clearShiftAmount);
            b = (byte) (current | temp);
        }
        out.put(bytePos,b);
        bitIndex = (bitIndex + bitsWritten) % 8;
        amount -= bitsWritten;
    }
    if (amount <= 0) {
        return this;
    }
    bitIndex = amount & 7;
    int newAmount = amount - bitIndex;
    //newValue should not equal 2047
    for (int i = 0; i != newAmount; i += 8) {
        writeByte((byte) ((value >> i)), false);
    }
    if (bitIndex > 0)
        writeByte((byte) (value << (8 - bitIndex)), false);
    return this;
}

As I'm new to this I think there may be more efficient ways, maybe using bit-masking or a lookup table of some sort? Any ideas or steering in the right direction would be great. Cheers.

like image 385
Eladian Avatar asked Feb 13 '18 08:02

Eladian


1 Answers

Ok, I tweaked your original algorithm to remove some of the redundant math, and I shaved about 10% off (went from 0.016 ms to about 0.014 ms on my machine). I also altered my test to run each algorithm 1000 times.

There also appears to be some savings to be had in that last for loop because the same bits are being shifted over and over. If you could somehow retain the results of the previous shift that might help. But that would alter the order of bytes going to out, so would require some more thought.

public void writeBits3(long value, int amount) {
    if (bitIndex != 0) {
        int remainingBits = 8 - bitIndex;
        int bytePos = out.position() - 1;
        byte current = out.get(bytePos);
        int shiftAmount = amount - remainingBits;

        int bitsWritten = 0;
        if (shiftAmount < 0) {
            bitsWritten = amount;
            out.put(bytePos, (byte) (current | (value << -shiftAmount)));
        } else {
            bitsWritten = remainingBits;
            out.put(bytePos, (byte) (current | (value >> shiftAmount)));
        }

        bitIndex += bitsWritten;
        amount -= bitsWritten;
        if (bitIndex >= 8) {
            bitIndex = 0;
        }
    }
    if (amount <= 0) {
        return;
    }
    bitIndex = amount & 7;
    int newAmount = amount - bitIndex;
    long newValue = (value >> bitIndex);
    for (; newAmount >= 8; newAmount -= 8) {
        out.put((byte) (newValue >> newAmount));
    }
    out.put((byte) (value << (8 - bitIndex)));
}
like image 103
Russ Jackson Avatar answered Sep 20 '22 14:09

Russ Jackson