public abstract class BitArray {
byte[] bytes = new byte[2048];
int bitGet;
public BitArray() {
}
public void readNextBlock(int initialBitGet,int count) {
// substitute for reading from an input stream
for (int i=(initialBitGet>>3); i<=count; ++i) {
bytes[i] = (byte) i;
}
prepareBitGet(initialBitGet,count);
}
public abstract void prepareBitGet(int initialBitGet,int count);
public abstract int getBits(int count);
static class Version0 extends BitArray {
public void prepareBitGet(int initialBitGet,int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
// intentionally gives meaningless result
bitGet += len;
return 0;
}
}
static class Version1 extends BitArray {
public void prepareBitGet(int initialBitGet,int count) {
bitGet = initialBitGet - 1;
}
public int getBits(int len) {
int byteIndex = bitGet;
bitGet = byteIndex + len;
int shift = 23 - (byteIndex & 7) - len;
int mask = (1 << len) - 1;
byteIndex >>= 3;
return (((bytes[byteIndex] << 16) |
((bytes[++byteIndex] & 0xFF) << 8) |
(bytes[++byteIndex] & 0xFF)) >> shift) & mask;
}
}
static class Version2 extends BitArray {
static final int[] mask = { 0x0,0x1,0x3,0x7,0xF,0x1F,0x3F,0x7F,0xFF,0x1FF,0x3FF,0x7FF,0xFFF,0x1FFF,0x3FFF,0x7FFF,0xFFFF };
public void prepareBitGet(int initialBitGet,int count) {
bitGet = initialBitGet;
}
public int getBits(int len) {
int offset = bitGet;
bitGet = offset + len;
int byteIndex = offset >> 3; // originally used /8
int bitIndex = offset & 7; // originally used %8
if ((bitIndex + len) > 16) {
return ((bytes[byteIndex] << 16 |
(bytes[byteIndex + 1] & 0xFF) << 8 |
(bytes[byteIndex + 2] & 0xFF)) >> (24 - bitIndex - len)) & mask[len];
} else if ((offset + len) > 8) {
return ((bytes[byteIndex] << 8 |
(bytes[byteIndex + 1] & 0xFF)) >> (16 - bitIndex - len)) & mask[len];
} else {
return (bytes[byteIndex] >> (8 - offset - len)) & mask[len];
}
}
}
static class Version3 extends BitArray {
int[] ints = new int[2048];
public void prepareBitGet(int initialBitGet,int count) {
bitGet = initialBitGet;
int put_i = (initialBitGet >> 3) - 1;
int get_i = put_i;
int buf;
buf = ((bytes[++get_i] & 0xFF) << 16) |
((bytes[++get_i] & 0xFF) << 8) |
(bytes[++get_i] & 0xFF);
do {
buf = (buf << 8) | (bytes[++get_i] & 0xFF);
ints[++put_i] = buf;
} while (get_i < count);
}
public int getBits(int len) {
int bit_idx = bitGet;
bitGet = bit_idx + len;
int shift = 32 - (bit_idx & 7) - len;
int mask = (1 << len) - 1;
int int_idx = bit_idx >> 3;
return (ints[int_idx] >> shift) & mask;
}
}
static class Version4 extends BitArray {
int[] ints = new int[1024];
public void prepareBitGet(int initialBitGet,int count) {
bitGet = initialBitGet;
int g = initialBitGet >> 3;
int p = (initialBitGet >> 4) - 1;
final byte[] b = bytes;
int t = (b[g] << 8) | (b[++g] & 0xFF);
final int[] i = ints;
do {
i[++p] = (t = (t << 16) | ((b[++g] & 0xFF) <<8) | (b[++g] & 0xFF));
} while (g < count);
}
public int getBits(final int len) {
final int i;
bitGet = (i = bitGet) + len;
return (ints[i >> 4] >> (32 - len - (i & 15))) & ((1 << len) - 1);
}
}
public void benchmark(String label) {
int checksum = 0;
readNextBlock(32,1927);
long time = System.nanoTime();
for (int pass=1<<18; pass>0; --pass) {
prepareBitGet(32,1927);
for (int i=2047; i>=0; --i) {
checksum += getBits(i & 15);
}
}
time = System.nanoTime() - time;
System.out.println(label+" took "+Math.round(time/1E6D)+" ms,checksum="+checksum);
try { // avoid having the console interfere with our next measurement
Thread.sleep(369);
} catch (InterruptedException e) {}
}
public static void main(String[] argv) {
BitArray test;
// for the sake of getting a little less influence from the OS for stable measurement
Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
while (true) {
test = new Version0();
test.benchmark("no implementaion");
test = new Version1();
test.benchmark("Durandal's (original)");
test = new Version2();
test.benchmark("blitzpasta's (adapted)");
test = new Version3();
test.benchmark("MSN's (posted)");
test = new Version4();
test.benchmark("MSN's (half-buffer modification)");
System.out.println("--- next pass ---");
}
}
}
这是有效的,但我正在寻找一个更有效的解决方案(性能明智).字节数组保证相对较小,在几个字节之间,最大为1800字节.在读取方法的每次调用之间,数组读取完全一次(完全).没有必要在getBits()中进行任何错误检查,例如超出数组等.
看来我上面的初步问题还不够清楚. N位的“位序列”形成N位的整数,我需要以最小的开销提取这些整数.我没有使用字符串,因为值被用作查找索引或直接馈入一些计算.所以基本上,上面显示的框架是一个真正的类,getBits()签名显示了其余代码如何与它进行交互.
将示例代码扩展到微基准,包括blitzpasta的解决方案(固定的丢失字节屏蔽).在我的旧的AMD盒子里,结果是〜11400ms vs〜38000ms. FYI：它的划分和模拟操作,杀死了性能.如果用>> 3和％8替换为&8,& 7,这两个解决方案彼此非常接近(jdk1.7.0ea104).
似乎有关于如何和什么工作有点混乱.示例代码的第一个原始帖子包括一个read()方法来指示字节缓冲区的填充位置和时间.当代码变成微架时,这丢失了.我重新介绍了它,使之更清楚一点.
这个想法是通过添加需要实现getBits()和prepareBitGet()的BitArray的另一个子类来击败所有现有的版本,后者可能为空.不要改变基准测试,使您的解决方案有优势,所有现有解决方案都可以完成同样的操作,从而使其成为一个完美的优化！ (真！！)
我添加了一个版本0,它只会增加bitGet状态.总是返回0,以了解基准开销有多大.它只在那里进行比较.
此外,添加了对MSN的想法的适应(Version3).为了保持所有竞争对手的公平和可比性,字节数组填充现在是基准的一部分,以及准备步骤(见上文).最初MSN的解决方案并没有那么好,在准备int []缓冲区时有很多开销.我自由地优化了一步,这变成了一个激烈的竞争对手:)
你也可能会发现我已经把你的代码去掉了一些.您的getBit()可能会被缩减为3列,可能会削减一到两个百分点.我故意这样做,以保持代码的可读性,因为其他版本不尽可能缩小(再次为可读性).
结论(上面的代码示例更新包括基于所有适用的贡献的版本).在我老的AMD盒子(Sun JRE 1.6.0_21)上,他们出来了：
V0没有实现了5384毫秒
V1 Durandal(原创)花了10283毫秒
V2 blitzpasta(适应)花了12212 ms
V3 MSN(发布)花了11030毫秒
V4 MSN(半缓冲区修改)耗时9700 ms
注意：在这个基准测试中,平均每个调用getBits()获取7.5位,每个位只读一次.由于V3 / V4必须支付较高的初始化成本,所以它们倾向于以较短的获取时间来显示更好的运行时行为(因此更接近平均获取大小的最大值为16).尽管如此,V4在所有情况下仍然保持领先于所有其他方案.
在实际应用中,必须考虑缓存争用,因为V3 / v4所需的额外空间可能会将高速缓存未命中增加到V0将是更好的选择.如果阵列不止一次地被遍历,V4应该是有利的,因为它比其他的获取速度更快,并且昂贵的初始化在第一次通过后被分摊.
解决方法
byte[] bytes = new byte[2048];
int bitGet;
unsigned int dwords[] = new unsigned int[2046];
public BitArray() {
for (int i=0; i<bytes.length; ++i) {
bytes[i] = (byte) i;
}
for (int i= 0; i<dwords.length; ++i) {
dwords[i]=
(bytes[i ] << 24) |
(bytes[i + 1] << 16) |
(bytes[i + 2] << 8) |
(bytes[i + 3]);
}
}
int getBits(int len)
{
int offset= bitGet;
int offset_index= offset>>4;
int offset_offset= offset & 15;
return (dwords[offset_index] >> offset_offset) & ((1 << len) - 1);
}
你可以避免分支(以你的内存占用四倍的代价).而且正好比(1< len) - 1更快地查找面具？
