lucene中的PackedInts源码解读(3)-PACKED格式
程序员文章站
2022-03-23 14:27:53
...
继续回到最开始的获得mutable的代码那里去
public static Mutable getMutable(int valueCount, int bitsPerValue, PackedInts.Format format) {
assert valueCount >= 0;
switch (format) {
case PACKED_SINGLE_BLOCK:
return Packed64SingleBlock.create(valueCount, bitsPerValue);//这个已经说完了，
case PACKED://这篇文章说明这个
switch (bitsPerValue) {
case 8:
return new Direct8(valueCount);
case 16:
return new Direct16(valueCount);
case 32:
return new Direct32(valueCount);
case 64:
return new Direct64(valueCount);
case 24:
if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
return new Packed8ThreeBlocks(valueCount);
}
break;
case 48:
if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
return new Packed16ThreeBlocks(valueCount);
}
break;
}
return new Packed64(valueCount, bitsPerValue);//如果没有上面的bitPerValue的，则使用这个。
default:
throw new AssertionError();
}
}
之前说完了Packed64SingleBlock的原理，他多少是浪费空间的，虽然很小。这次要说的PACKED格式的Mutable是完全不浪费空间的，其中Direct8、Direct16、Direct32、Direct64都是一个block保存一个数字，比如Direct8，他里面就是使用了byte[]，一个block就是一个byte，所以这样不会造成一点的浪费。同理，Direct16是使用了short[]，Direct32是使用了int[]，Direct64是使用了long[]。他们要比原来的Packed64SingleBlock的思路更简单，而且在保存和查找的时候代码也更简单。我们那Direct32的代码做例子吧。看看他的保存（即set）方法和读取（即get）方法。
public int set(int index, long[] arr, int off, int len) {
assert len > 0 : "len must be > 0 (got " + len + ")";
assert index >= 0 && index < valueCount;
assert off + len <= arr.length;
final int sets = Math.min(valueCount - index, len);
for (int i = index, o = off, end = index + sets; i < end; ++i, ++o) {
values[i] = (int) arr[o];//直接用原来的值即可，不过要变为int。
}
return sets;
}
public int get(int index, long[] arr, int off, int len) {
assert len > 0 : "len must be > 0 (got " + len + ")";
assert index >= 0 && index < valueCount;
assert off + len <= arr.length;
final int gets = Math.min(valueCount - index, len);
for (int i = index, o = off, end = index + gets; i < end; ++i, ++o) {
arr[o] = values[i] & 0xFFFFFFFFL;//直接读取，不过要变为一个int
}
return gets;
}
这样就很简单的看完了Directx系列，再看一下Packed8ThreeBlocks和Packed16ThreeBlocks，这俩的思路也很简单，Packed8ThreeBlocks处理bitPerValue是24的情况，他内部使用了一个byte[]，所以使用3个byte来保存一个数字，而他创建的byte[]的最大程度是int.max_value，所以最多存储的数字的数量是Integer.max_value/3个，所以就有了上面的if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) 的判断，Packed16ThreeBlocks的思路类似，这里直接略过。
上面的Directx系列和Packed8ThreeBlocks、Packed16ThreeBlocks系列都是存储的8的整数倍大小的bitPerValue，如果不是8的整数倍呢，就要使用上面的Packed64了。它使用long[]来保存数字，但是他不会浪费空间，（类似Packed64SingleBlock，但是他是连续的，即一个数字可能会保存在两个block，即两个long数字里面）.【注：Format只要是packed类型的，则一定不会浪费空间】
public Packed64(int valueCount, int bitsPerValue) {
super(valueCount, bitsPerValue);//他的父类是MutableImpl，里面仅仅保存了数字的数量和每个数字的bitPerValue。
final PackedInts.Format format = PackedInts.Format.PACKED;
final int longCount = format.longCount(PackedInts.VERSION_CURRENT, valueCount, bitsPerValue);//计算使用的long的数量
this.blocks = new long[longCount];//最终使用的数字
maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);//先左移，把高位的去掉，再无符号右移，把高位全部用0填充，这样就把超过bitPerValue的位数上的变为0.其他位上全是1.
bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;//相当于是64-bitPerValue的负数。
}
看看他的set方法
public int set(int index, long[] arr, int off, int len) {
assert len > 0 : "len must be > 0 (got " + len + ")";
assert index >= 0 && index < valueCount;
len = Math.min(len, valueCount - index);
assert off + len <= arr.length;
final int originalIndex = index;
final PackedInts.Encoder encoder = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);
// go to the next block where the value does not span across two blocks 这一块的逻辑和前面的Packed64SingleBlcok中的是一样的，
final int offsetInBlocks = index % encoder.longValueCount();//是不是bulk set的一个块的开始，因为下面的bulk set要在一个块的开始才可以。encoder.longValueCount表示一个块中long的数量
if (offsetInBlocks != 0) {//如果不满足一个快的开始，就单独的调用set。
for (int i = offsetInBlocks; i < encoder.longValueCount() && len > 0; ++i) {
set(index++, arr[off++]);
--len;
}
if (len == 0) {
return index - originalIndex;
}
}
// bulk set 此时存放一定是一个块的开始，块的开始一定是从一个long开始
assert index % encoder.longValueCount() == 0;
int blockIndex = (int) (((long) index * bitsPerValue) >>> BLOCK_BITS);//从第几个long开始放
assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
final int iterations = len / encoder.longValueCount();//放多少次，因为对于bulk set来说，一放就是一个块，块的大小（能存放的int的数量）是encoder.longValueCount。
encoder.encode(arr, off, blocks, blockIndex, iterations);//单独拿出来了下面有
final int setValues = iterations * encoder.longValueCount();
index += setValues;
len -= setValues;
assert len >= 0;
if (index > originalIndex) {
// stay at the block boundary
return index - originalIndex;
} else {//这种情况是可能发生的，比如offsetInBlock正好是0，但是要保存的数字的数量不够encoder.longValueCount，就会发生这种情况。此时就要调用父类的方法，挨个调用set方法
// no progress so far => already at a block boundary but no full block to get
assert index == originalIndex;
return super.set(index, arr, off, len);
}
}
里面有单独的set方法，即一个一个设置的方法，如下：
public void set(final int index, final long value) {
// The abstract index in a contiguous bit stream
final long majorBitPos = (long)index * bitsPerValue;
// The index in the backing long-array
final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // BLOCK_SIZE 除以64求商，也就是计算是第几个long数字
// The number of value-bits in the second long
final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;//结束为止，计算方式为：求余数（在某个long中的开始位置），然后加上长度（bitPerValue）再减去block_size。如果小于0，说明在一个long里面。
if (endBits <= 0) {// Single block 如果没有跨long，则-endBits就是这个数字结束后还剩多少位， 先计算&，表示把这个数字要在的多个位置全部变为0（也就是清空），然后再|，表示将这个字段
blocks[elementPos] = blocks[elementPos] & ~(maskRight << -endBits) | (value << -endBits);//maskRight<< 从这里看出，是从高位到低位存的。
return;
}
// Two blocks 此时，endBits就是在第二个long中的结束位置了。~(maskRight >>> endBits)表示将第一个long上的最后几位清空，然后|(value >>> endBits)，表示保存数据
blocks[elementPos] = blocks[elementPos] & ~(maskRight >>> endBits) | (value >>> endBits);
blocks[elementPos+1] = blocks[elementPos+1] & (~0L >>> endBits) | (value << (BLOCK_SIZE - endBits));//保存第二部分。
}
从上面可以看出来，单独的set方法是由高位到低位的，这一点和Packed64SingleBlock是不同的，后者是从低位到高位。里面的encoder还没有看，使用的是org.apache.lucene.util.packed.BulkOperation.packedBulkOps这个数组里面的对象，根据bitPerValue来获得的。数组里面的都是继承自BulkOperationPacked，只是传入的bitPerValue不一样。我们看下这个类的encode方法（encode方法就是一下子操作一个块，这里的iteration是经过计算后传入的，要么一个块全部填完，要么一个都不填）
public void encode(long[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations) {
long nextBlock = 0;
int bitsLeft = 64;
for (int i = 0; i < longValueCount * iterations; ++i) {//longValueCount即一个块能存放数字的数量，
bitsLeft -= bitsPerValue;
if (bitsLeft > 0) {//当前的long的位数有剩余
nextBlock |= values[valuesOffset++] << bitsLeft;//由高位到低位
} else if (bitsLeft == 0) {//当前的long全部使用完了，则不需要位移动了
nextBlock |= values[valuesOffset++];
blocks[blocksOffset++] = nextBlock;
nextBlock = 0;
bitsLeft = 64;
} else { // bitsLeft < 0
nextBlock |= values[valuesOffset] >>> -bitsLeft;//保存这个数字的高位（bitPerValue-bitsLeft位）
blocks[blocksOffset++] = nextBlock;
nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);//将当前数字的后bitsLeft位保存起来。
bitsLeft += 64;
}
}
}
上面中和单独的set方法也是一样的，都是从高位到低位。
看完了保存的方法，再看一下get方法，先看packed64的批量的get方法：
public int get(int index, long[] arr, int off, int len) {
assert len > 0 : "len must be > 0 (got " + len + ")";
assert index >= 0 && index < valueCount;
len = Math.min(len, valueCount - index);
assert off + len <= arr.length;
final int originalIndex = index;
final PackedInts.Decoder decoder = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);//找到decoder
// go to the next block where the value does not span across two blocks
final int offsetInBlocks = index % decoder.longValueCount();//和encoder的逻辑一样，都是为了凑够一个块的数量。longValueCount表示一个块的数字的数量
if (offsetInBlocks != 0) {//如果不是合适的数字（即不是一个bulk set的块的开始），则调用单独的get方法
for (int i = offsetInBlocks; i < decoder.longValueCount() && len > 0; ++i) {
arr[off++] = get(index++);//单个的get方法
--len;
}
if (len == 0) {
return index - originalIndex;
}
}
// bulk get 前提是一个新的bulk set的块，也一定是一个新的long
assert index % decoder.longValueCount() == 0;
int blockIndex = (int) (((long) index * bitsPerValue) >>> BLOCK_BITS);//从第几个long开始
assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
final int iterations = len / decoder.longValueCount();//需要多少个块（说的是bulk set的块）
decoder.decode(blocks, blockIndex, arr, off, iterations);//解码指定的块，代码在下面。
final int gotValues = iterations * decoder.longValueCount();
index += gotValues;
len -= gotValues;
assert len >= 0;
if (index > originalIndex) {
// stay at the block boundary
return index - originalIndex;
} else {
// no progress so far => already at a block boundary but no full block to get
assert index == originalIndex;
return super.get(index, arr, off, len);
}
}
单个的get方法如下：
public long get(final int index) {
// The abstract index in a bit stream
final long majorBitPos = (long)index * bitsPerValue;
// The index in the backing long-array
final int elementPos = (int)(majorBitPos >>> BLOCK_BITS);//开始位置在哪个long上
// The number of value-bits in the second long
final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;//(majorBitPos & MOD_MASK)表示在指定的long上的开始位置，加上bitPerValue，减去block_size。
if (endBits <= 0) {// Single block 此时 -endBits表示离这个logn的最后还剩几位，右移blocks[elementPos]的目的是要和maskRight做&，和maskRigh做%的目的是将其变为一个
return (blocks[elementPos] >>> -endBits) & maskRight;
}
// Two blocks
return ((blocks[elementPos] << endBits) /*第一个long中的内容左移指定的位数，因为他后面的几位已经在第二个long中了*/ | (blocks[elementPos+1] >>> (BLOCK_SIZE - endBits))) & maskRight;
}
最后看下decoder类，因为对不不同的bitPerValue，所以有 很多个类（和上面的encoder一样，都是org.apache.lucene.util.packed.BulkOperation.packedBulkOps这个数组）,但是我不明白的是他们竟然有很多都覆写了org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)方法，我个人觉得直接使用org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)就可以啊，没有必要再覆写，尤其是在我看到了BulkOperationPacked1和BulkOperationPacked2的方法后，我更是这么认为，因为他们覆写后的方法和没有覆写是一样的，在我看了BulkOperationPacked3之后， 我想到了一小点就是效率会高一点，如果网友有更好的理解，请联系我（qq:1308567317），这里我就只看org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)方法了
public void decode(long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
int bitsLeft = 64;
for (int i = 0; i < longValueCount * iterations; ++i) {
bitsLeft -= bitsPerValue;
if (bitsLeft < 0) {
values[valuesOffset++] = ((blocks[blocksOffset++]
& ((1L << (bitsPerValue + bitsLeft)) - 1)) << -bitsLeft)
| (blocks[blocksOffset] >>> (64 + bitsLeft));
bitsLeft += 64;
} else {
values[valuesOffset++] = (blocks[blocksOffset] >>> bitsLeft) & mask;
}
}
}
上面的方法很简单就能看懂了。
好了，很简单就看懂了所有的PackedInts的源码。如果有人觉得我写的有问题，可以联系我（qq:1308567317）
上一篇： Lucene索引文件查看器luke