JavaScript BitArray实现

Question

我正在做一个项目，在这个项目中，数组的长度可以很容易地超过50米。它是一个只保存布尔值(0/1)值的数组。使用Uint8Array很好，与普通数组相比，它的性能非常好。不过，我还是想尝试通过扩展BitArray对象来实现DataView。与普通数组(1/32)和Uint8Array (1/8)相比，D6大大减少了内存占用。因此，这是一个一定的增益，但就速度而言，尽管我已经尽了一切努力，BitArray仍然比两者都慢一些，除非大小达到33,554,433个极限(> 2⁵)。正如我从这份文件中读到的，此时正常的Array达到了~268 v8的内存限制，它的内部结构被转换为NumberDictionary[16]，在v8中产生了显著的减速。注意，当长度为33,554,433时，BitArray只使用4MB内存。

另外一点要注意的是，对于我的应用程序，我需要BitArray (人口计数)中的1s总数，这是下面代码中的popcount属性。由于速度快得惊人，Hamming权算法 BitArray比计算数组中的现有项快80倍，尽管我在这里没有测试它。

任何提振BitArray的想法都是最受欢迎的。

class BitArray extends DataView{

  constructor(n,ab){
    var abs = n >> 3; // ArrayBuffer Size
    super(ab instanceof ArrayBuffer ? ab
                                    : n & 31 ? new ArrayBuffer(abs + 4 - (abs & 3))
                                             : new ArrayBuffer(abs));
  }

  get length(){
    return this.buffer.byteLength*8;
  }

  get popcount(){
    var m1  = 0x55555555,
        m2  = 0x33333333,
        m4  = 0x0f0f0f0f,
        h01 = 0x01010101,
        pc  = 0,
        x;
    for (var i = 0, len = this.buffer.byteLength >> 2; i < len; i++){
       x = this.getUint32(i << 2);
       x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
       x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
       x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
       pc += (x * h01) >> 56;
    }
    return pc;
  }

  // n >> 3 is Math.floor(n/8)
  // n & 7 is n % 8

  at(n){  
    return this.getUint8(n >> 3) & (1 << (n & 7)) ? 1 : 0;
  }

  set(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) | (1 << (n & 7)));
  }

  reset(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) & ~(1 << (n & 7)));
  }

  slice(a = 0, b = this.length){
    return new BitArray(b-a,this.buffer.slice(a >> 3, b >> 3));
  }

  toggle(n){
    this.setUint8(n >> 3, this.getUint8(n >> 3) ^ (1 << (n & 7)));
  }

  toString(){
    return new Uint8Array(this.buffer).reduce((p,c) => p + Array.prototype.reduce.call(c.toString(2).padStart(8,"0"),(f,s) => s+f), "")
                                      .slice(0,this.length);
  }
}

// Test code starts from here

var len = 1e6,  // array length
    tst = 10,   // test count
    arr = Array(len),
    bar = new BitArray(len),
    uia = new Uint8Array(len),
    r1,r2,r3,t = 0;

console.log(`There are ${bar.popcount} 1s in the BitArray`);
for (var i = 0; i < len; i++){
  (Math.random() > 0.5) && ( t++
                           , bar.set(i)
                           );
}

console.log(`${t} .set() ops are made and now there are ${bar.popcount} 1s in the BitArray`);

console.time("Array");
for (var k = 0; k < tst; k++){
  for (var i = 0; i < len; i++) arr[i] = Math.random() > 0.5 ? 1 : 0;
  for (var i = 0; i < len; i++) t = arr[1];
  r1 = arr.slice();
}
console.timeEnd("Array");

console.time("BitArray");
for (var k = 0; k < tst; k++){
  for (var i = 0; i < len; i++) Math.random() > 0.5 ? bar.set(i) : bar.reset(i)
  for (var i = 0; i < len; i++) t = bar.at(i);
  r2 = bar.slice();
}
console.timeEnd("BitArray");

console.time("Uint8Array");
for (var k = 0; k < tst; k++){
  for (var i = 0; i < len; i++) uia[i] = Math.random() > 0.5 ? 1 : 0;
  for (var i = 0; i < len; i++) t = uia[i];
  r3 = uia.slice();
}
console.timeEnd("Uint8Array");

Answer 1

abs + 4 - (abs & 3)

可以简化：(abs + 3) & -4

它们不是等价表达式，但当abs不是4的倍数时，它们是等价的。实际上，在这种情况下，更简单的表达式更方便:使用这个表达式，您可以跳过三元表达式，因为它不会不适当地将4的倍数集合起来，因此不再是特例。

popcount诡计

你已经使用了一个很好的技巧，但是还有更多的可能。这个技巧的一个有趣的特点是，当它完成了几个步骤之后，它就开始浪费它的一些潜力，例如，我的意思是，第三步(x + (x >> 4)) & m4添加相邻的咬口，但是这些小块中的值从0到4不等(包括)，而不是0到15的范围。如果循环被展开为2的因子，那么只需要复制前半部分:然后可以添加中间结果(产生的值范围为0到8，包括在内)。技巧的后半部分(第三和第四步)只需要执行一次。

还有更多的技巧，例如，给定3位uint32s (a, b, c)，我们只需要2位32位波普计数就可以计算所有比特：

b0 = a ^ b ^ c
b1 = (a & (b | c)) | (b & c)
count = popcount(b0) + 2 * popcount(b1)

位操作步骤实际上是位级3输入加法，2位结果分布于两个变量:在每个位置，b0持有该位置之和的0位，b1持有之和的第1位。这可以概括为将7个输入组合成3，15到4，等等。在使用AVX2 2指令进行更快的填充计数中可以找到更好的版本(当然，您不会在JavaScript中使用AVX2，但是可以使用一些相同的技术来减少实际的流行次数)。