I am working on a project in which an array can easily grow beyond 50M in length. It's an array holding only boolean (0/1) values. Using Uint8Array is just fine and it's very performant compared normal arrays. Still I just wanted to try implementing a BitArray by extending DataView object. BitArray enormously reduces the memory footprint compared to normal Arrays (1/32) and Uint8Array (1/8). So that's a certain gain but as for speed, despite I did everything to my knowledge BitArray is still slightly slower compared to both unless the size hits the 33,554,433 limit (> 2²⁵). As I have read from this document, at this point the normal Array reaches to ~268MB memory limit and it's internal structure gets switched to NumberDictionary[16] yielding a dramatic slow down in v8. Note that when the length is 33,554,433 the BitArray uses only 4MB of memory.
One other point to note is, for my application i need the total number of 1s in the BitArray (population count) which is the popcount property in below code. Thanks to the blazingly fast Hamming Weight algorithm BitArray is like 80 times faster compared to counting the existing items in array though I am not testing it here.
Any ideas to boost the BitArray up a little are most welcome.
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");
