Java - 优化将值作为位写入ByteBuffer的方法

Question

我目前正在开发一些网络编程代码（这是我的第一个服务器），并且有一个关于优化特定函数的快速问题，该函数将值作为位写入，然后将它们打包成一个字节。优化此函数的原因是因为它在每个服务器滴答声中被使用数千次，用于打包要发送给多个客户端的数据。

一个示例可能更好地解释函数试图实现的内容：值3可以由两个位表示。在二进制中，它看起来像 00000011。该函数将把这个二进制值转换成11000000。当再次调用该函数时，它会知道从第三个最高位（从右边算起第三个/十进制32）开始，并在当前字节中写入至多6位。如果还有剩余的位要写入，则会在新字节上开始。

这样做的目的是为了节省空间，如果您有多个值可以少于一个字节。

我的当前函数如下：

 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;
}

作为一个新手，我认为可能有更有效的方法，比如使用位掩码或某种查找表？有任何想法或引导方向都会很好。谢谢。

- Eladian

---

那么在接收端，当你看到比特串 111110011 时，你如何知道前两个比特是 3 而不是实际上前三个比特被发送为 7？ - Jim Garrison

你考虑过使用 java.util.BitSet 吗？它可以完成你想要的一切，而无需复杂的编码或自己管理缓冲区。请阅读 Javadoc。 - Jim Garrison

@JimGarrison 在 BitSet 上没有可用的方法来设置特定值（例如，值为5需要 biset.set(0)，bitset.set(2)），此外，它还必须被反转等。我认为这会更加复杂？ - Eladian

哦，好吧，这只是一个想法。我回到了Javadoc，现在意识到那个类有多么不够强大。它可以使用相当多的功能，例如原语之间的逻辑操作和集合的任意子字符串。算了。 - Jim Garrison

是的，一个单一的值可以被分割成两个不同的字节。4,2,4 = 1个字节和2个位的余数。这2个位被打包到第二个字节的最高有效位上，所以如果它们是0b11，下一个字节将是11000000。在下一次写入时，我们将取最后一个字节，并根据剩余的位数将位打包到其中。 - Eladian

Answer 1

好的，我调整了您原始的算法以去除一些冗余的数学计算，并将其优化了约10％（在我的机器上从0.016毫秒降至约0.014毫秒）。我还修改了我的测试，使每个算法运行1000次。

同时，在最后一个for循环中似乎也可以节省一些时间，因为相同的位一遍又一遍地被移动。如果您能够以某种方式保留先前移位的结果，那可能会有所帮助。但这将改变传输到out的字节顺序，因此需要更多思考。

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)));
}

- Russ Jackson

---

应该会运行得更快 :) 我在想，如果将 bitIndex 取模 8 并且去掉 if 语句，是否会更快。 - Eladian

顺便说一下，我会再等一段时间看看是否有其他的贡献，但如果没有，我将接受这个答案。 - Eladian

我按照你的建议更改了bitIndex检查，但结果并不明确。大多数情况下略微快一些，但有时却不是这样。我调整了测试，将100个长整型数据推送到算法中，并对每种算法重复执行1000万次。 - Russ Jackson

Answer 2

这里有一个比我之前提供的更好的解决方案，使用递归，非常适合此问题。

private static final long[] mask = { 0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff };

private ByteBuffer out = ByteBuffer.allocate(1024);
private int position = 0;
private int dataBits = 0;
private byte remainder = 0;

/**
 * value: The value to write
 * amount: The number of bits to represent the value in.
 */
public void writeBits(long value, int amount) {
    if (amount <= Long.SIZE) {
        if (amount > 0) {
            // left align the bits in value
            writeBitsLeft(value << (Long.SIZE - amount), amount);
        } else {
            // flush what's left
            out.put(position++, remainder);
        }
    } else {
        // the data provided is invalid
        throw new IllegalArgumentException("the amount of bits to write is out of range");
    }
}

/**
 * write amount bits from the given value
 * 
 * @param value represents bits aligned to the left of a long
 * @param amount bits left to be written from value
 */
private void writeBitsLeft(long value, int amount) {
    if (amount > 0) {
        // how many bits are left to be filled in the current byte?
        int room = Byte.SIZE - dataBits;

        // how many bits are we going to add to the current byte?
        int taken = Math.min(amount, room);

        // rotate those number of bits into the rightmost position
        long temp = Long.rotateLeft(value, taken);

        // add count taken to the count of bits in the current byte
        dataBits += taken;

        // add in that number of data bits
        remainder &= temp & mask[taken];

        // have we filled the byte yet?
        if (Byte.SIZE == dataBits) {
            out.put(position++, remainder);

            // reset the current byte
            remainder = 0;
            dataBits = 0;

            // process any bits left over
            writeBitsLeft(temp, amount - taken);
        }
    } 
} // writeBitsLeft()

这种解决方案的数学运算、移位操作和if语句都更少，因此应该比原始解决方案更有效，更不用说它可能更容易理解。

- Russ Jackson

---

好的，我写了一个单元测试来衡量你的解决方案（V0）和我的两个解决方案（V1和V2），而你的解决方案毫无疑问是最优秀的。 - Russ Jackson

优化后的 V2 = 408393 优化后的 V1 = 342537 优化后的 V0 = 313885 - Russ Jackson

嗯，奇怪，你是说这个单元测试比我发布的解决方案慢吗？这绝对看起来更优雅、易读，但可能由于额外的方法调用而更慢。感谢您发布的解决方案，但我正在寻找比发布的解决方案更快的单元测试方法 :) - Eladian

我修改了我的测试，运行每个算法100次并平均结果。 V0（你的）和V1（我的）一直处于势均力敌的状态 - 有时一个更快，有时另一个更快，但差别不大。我的V2（递归）始终是最慢的，差距很大。 - Russ Jackson

我找到了这个。如果将长整型转换为基数127，则符号位可用于指示流中给定数字是否有更多字节。https://en.wikipedia.org/wiki/Variable-length_quantity - Russ Jackson

Answer 3

这个怎么样？

private ByteBuffer out = ByteBuffer.allocate(1024);
private int position = 0;
private int dataBits = 0;
private long data = 0;

/**
 * value: The value to write
 * amount: The number of bits to represent the value in.
 */
public void writeBits(long value, int amount) {
    if (amount <= 0) {
        // need to flush what's left
        if (dataBits > 0) {
            dataBits = Byte.SIZE;
        }
    } else {
        int totalBits = dataBits + amount;

        // need to handle overflow?
        if (totalBits > Long.SIZE) {
            // the new data is to big for the room that remains;  by how much?
            int excess = totalBits - Long.SIZE;

            // drop off the excess and write what's left
            writeBits(value >> excess, amount - excess);

            // now we can continue processing just the rightmost excess bits
            amount = excess;
        }

        // push the bits we're interested in all the way to the left of the long
        long temp = value << (Long.SIZE - amount);

        // make room for any existing (leftover) data bits, filling with zeros to the left (important)
        temp = temp >> dataBits;

        // append the new data to the existing
        data |= temp;

        // account for new bits of data
        dataBits += amount;
    }

    while (dataBits >= Byte.SIZE) {
        // shift one byte left, rotating the byte that falls off into the rightmost byte
        data = Long.rotateLeft(data, Byte.SIZE);

        // add the rightmost byte to the buffer
        out.put(position++, (byte)(data & 0xff));

        // drop off the rightmost byte
        data &= 0xffffffffffffff00L;

        // setup for next byte
        dataBits -= Byte.SIZE;
    }
}

- Russ Jackson