Java - 优化将值作为位写入字节缓冲区
Java - optimize writing values as bits to bytebuffer
我目前正在编写一些网络代码（这是我的第一台服务器），并且有一个关于优化特定函数的快速问题，该函数将值写入位，然后将它们打包成一个字节。优化这个函数的原因是因为它在每个服务器滴答中被使用数千次来打包数据发送给多个客户端。
举个例子可能会更好地解释函数试图完成的任务：
值 3 可以用两位表示。
在二进制中，它看起来像 00000011。该函数会将此二进制值转换为 11000000。当再次调用该函数时，它会知道从第 3 个最高有效位（right/decimal 32 开始的第 3 个）开始，最多将 6 位写入当前字节。如果还有剩余位要写入，它将从一个新字节开始。
如果您有多个小于字节的值，这样做的目的是节省 space。
我当前的函数如下所示：
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;
}
由于我是新手，我认为可能有更有效的方法，也许使用位掩码或某种查找 table？任何想法或转向正确的方向都会很棒。干杯。
这样的事情怎么样？
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;
}
}
这里有一个使用递归的更好的解决方案（比我之前的解决方案），它非常适合这个问题。
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 语句较少，因此应该比原始解决方案更高效，更不用说它可能更容易理解了。
好的，我调整了您的原始算法以删除一些多余的数学运算，并且减少了大约 10%（在我的机器上从 0.016 毫秒减少到大约 0.014 毫秒）。我还将我的测试更改为 运行 每个算法 1000 次。
最后一个 for 循环似乎也有一些节省，因为相同的位被一遍又一遍地移动。如果您能以某种方式保留上一次转变的结果，那可能会有所帮助。但这会改变字节的顺序，因此需要更多考虑。
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)));
}
我目前正在编写一些网络代码（这是我的第一台服务器），并且有一个关于优化特定函数的快速问题，该函数将值写入位，然后将它们打包成一个字节。优化这个函数的原因是因为它在每个服务器滴答中被使用数千次来打包数据发送给多个客户端。
举个例子可能会更好地解释函数试图完成的任务：
值 3 可以用两位表示。
在二进制中，它看起来像 00000011。该函数会将此二进制值转换为 11000000。当再次调用该函数时，它会知道从第 3 个最高有效位（right/decimal 32 开始的第 3 个）开始，最多将 6 位写入当前字节。如果还有剩余位要写入，它将从一个新字节开始。
如果您有多个小于字节的值，这样做的目的是节省 space。
我当前的函数如下所示：
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;
}
由于我是新手，我认为可能有更有效的方法，也许使用位掩码或某种查找 table？任何想法或转向正确的方向都会很棒。干杯。
这样的事情怎么样？
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;
}
}
这里有一个使用递归的更好的解决方案（比我之前的解决方案），它非常适合这个问题。
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 语句较少，因此应该比原始解决方案更高效，更不用说它可能更容易理解了。
好的，我调整了您的原始算法以删除一些多余的数学运算，并且减少了大约 10%（在我的机器上从 0.016 毫秒减少到大约 0.014 毫秒）。我还将我的测试更改为 运行 每个算法 1000 次。
最后一个 for 循环似乎也有一些节省，因为相同的位被一遍又一遍地移动。如果您能以某种方式保留上一次转变的结果，那可能会有所帮助。但这会改变字节的顺序，因此需要更多考虑。
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)));
}