JavaScript base64string -> 二进制值 -> [整数] ... 性能改进

Question

我正在使用 Parse Server 并尝试加速使用布隆过滤器的查询。

每个文档都有一个字段 bf，数值在 0...bloomSize 范围内，例如文档 ID“xyz”被散列为 bf = 6462

查询然后加载编码并保存在 base64 字符串中的二进制布隆过滤器值。要在 Parse Server / MongoDB 中使用索引查询，我需要生成一个整数数组，然后我可以将其与上述字段进行比较。因此需要对 base64 字符串进行解码，并且对于二进制数据中的每个 0，我必须附加该 0 值位置的整数。目前我正在使用以下代码段：

//loading [UInt8] from saved base64 string
const buf = new Buffer.from(request.user.get("daBlm"), 'base64');

var blm = Array()

for (var i = 0; i < buf.length; i++) {
    //iterating through 8-bit chunks and convert each UInt8 into string
    //as "toString" does not respect 8-bit length we chain ".padStart(8, '0')"
    const byte = buf[i].toString(2).padStart(8, '0');
    //loop through characters and for each 0, push the position into array
    for (var l = 0; l < byte.length; l++) {
        //push int to array for each bloom 0 value - not used bit
        if (byte[l] == "0") {
            blm.push(i*8 + l);
        } 
    }
}
//at the end is the blm array user in containedIn query constraint that use indexes    
dateQuery.containedIn("bf", blm);

虽然它按预期工作并且我的查询使用索引，但数组的生成是查询中最慢的部分。

我发现在进入循环之前设置数组长度稍微加快了速度：

//从保存的 base64 字符串中加载 [UInt8] const buf = new Buffer.from(request.user.get("daBlm"), 'base64');

var blm = Array()
blm.lenght = buf.lenght * 8  <-- this seems to help
for (var i = 0; i < buf.length; i++) {
    //iterating through 8-bit chunks and convert each UInt8 into string
    //as "toString" does not respect 8-bit length we chain ".padStart(8, '0')"
    const byte = buf[i].toString(2).padStart(8, '0');
    //loop through characters and for each 0, push the position into array
    for (var l = 0; l < byte.length; l++) {
        //push int to array for each bloom 0 value - not used bit
        if (byte[l] == "0") {
            blm.push(i*8 + l);
        } 
    }
}

我没有注意到数组的 const 和 var 之间有任何区别。

我也尝试用 switch 直接从 base64 生成，但这似乎比上面的循环慢了大约 10%-30%：

function availArr(base64Str) {
    const lenght = base64Str.length;
    if (lenght > 0) {
        var arr = Array();
        
        for (var i = 0; i < lenght; i++) {
            //iterating through characters of base64String
            switch (base64Str.charAt(i)) {
                case "A": //000000
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+3, i*8+4, i*8+5]);break;
                case "B": //000001
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+3, i*8+4]);break;
                case "C": //000010
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+3, i*8+5]);break;
                case "D": //000011
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+3]);break;
                case "E": //000100
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+4, i*8+5]);break;
                case "F": //000101
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+4]);break;
                case "G": //000110
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+5]);break;
                case "H": //000111
                    arr.push(...[i*8, i*8+1, i*8+2]);break;
                case "I": //001000
                    arr.push(...[i*8, i*8+1, i*8+3, i*8+4, i*8+5]);break;
                case "J": //001001
                    arr.push(...[i*8, i*8+1, i*8+3, i*8+4]);break;
                case "K": //001010
                    arr.push(...[i*8, i*8+1, i*8+3, i*8+5]);break;
                case "L": //001011
                    arr.push(...[i*8, i*8+1, i*8+3]);break;
                case "M": //001100
                    arr.push(...[i*8, i*8+1, i*8+4, i*8+5]);break;
                case "N": //001101
                    arr.push(...[i*8, i*8+1, i*8+4]);break;
                case "O": //001110
                    arr.push(...[i*8, i*8+1, i*8+5]);break;
                case "P": //001111
                    arr.push(...[i*8, i*8+1]);break;
                case "Q": //010000
                    arr.push(...[i*8, i*8+2, i*8+3, i*8+4, i*8+5]);break;
                case "R": //010001
                    arr.push(...[i*8, i*8+2, i*8+3, i*8+4]);break;
                case "S": //010010
                    arr.push(...[i*8, i*8+2, i*8+3, i*8+5]);break;
                case "T": //010011
                    arr.push(...[i*8, i*8+2, i*8+3]);break;
                case "U": //010100
                    arr.push(...[i*8, i*8+2, i*8+4, i*8+5]);break;
                case "V": //010101
                    arr.push(...[i*8, i*8+2, i*8+4]);break;
                case "W": //010110
                    arr.push(...[i*8, i*8+2, i*8+5]);break;
                case "X": //010111
                    arr.push(...[i*8, i*8+2]);break;
                case "Y": //011000
                    arr.push(...[i*8, i*8+3, i*8+4, i*8+5]);break;
                case "Z": //011001
                    arr.push(...[i*8, i*8+3, i*8+4]);break;
                case "a": //011010
                    arr.push(...[i*8, i*8+3, i*8+5]);break;
                case "b": //011011
                    arr.push(...[i*8, i*8+3]);break;
                case "c": //011100
                    arr.push(...[i*8, i*8+4, i*8+5]);break;
                case "d": //011101
                    arr.push(...[i*8, i*8+4]);break;
                case "e": //011110
                    arr.push(...[i*8, i*8+5]);break;
                case "f": //011111
                    arr.push(...[i*8]);break;
                case "g": //100000
                    arr.push(...[i*8+1, i*8+2, i*8+3, i*8+4, i*8+5]);break;
                case "h": //100001
                    arr.push(...[i*8+1, i*8+2, i*8+3, i*8+4]);break;
                case "i": //100010
                    arr.push(...[i*8+1, i*8+2, i*8+3, i*8+5]);break;
                case "j": //100011
                    arr.push(...[i*8+1, i*8+2, i*8+3]);break;
                case "k": //100100
                    arr.push(...[i*8+1, i*8+2, i*8+4, i*8+5]);break;
                case "l": //100101
                    arr.push(...[i*8+1, i*8+2, i*8+4]);break;
                case "m": //100110
                    arr.push(...[i*8+1, i*8+2, i*8+5]);break;
                case "n": //100111
                    arr.push(...[i*8, i*8+1, i*8+2, i*8+3, i*8+4, i*8+5]);break;
                case "o": //101000
                    arr.push(...[i*8+1, i*8+3, i*8+4, i*8+5]);break;
                case "p": //101001
                    arr.push(...[i*8+1, i*8+3, i*8+4]);break;
                case "q": //101010
                    arr.push(...[i*8+1, i*8+3, i*8+5]);break;
                case "r": //101011
                    arr.push(...[i*8+1, i*8+3]);break;
                case "s": //101100
                    arr.push(...[i*8+1, i*8+4, i*8+5]);break;
                case "t": //101101
                    arr.push(...[i*8+1, i*8+4]);break;
                case "u": //101110
                    arr.push(...[i*8+1, i*8+5]);break;
                case "v": //101111
                    arr.push(...[i*8+1]);break;
                case "w": //110000
                    arr.push(...[i*8+2, i*8+3, i*8+4, i*8+5]);break;
                case "x": //110001
                    arr.push(...[i*8+2, i*8+3, i*8+4]);break;
                case "y": //110010
                    arr.push(...[i*8+2, i*8+3, i*8+5]);break;
                case "z": //110011
                    arr.push(...[i*8+2, i*8+3]);break;
                case "0": //110100
                    arr.push(...[i*8+2, i*8+4, i*8+5]);break;
                case "1": //110101
                    arr.push(...[i*8+2, i*8+4]);break;
                case "2": //110110
                    arr.push(...[i*8+2, i*8+5]);break;
                case "3": //110111
                    arr.push(...[i*8+2]);break;
                case "4": //111000
                    arr.push(...[i*8+3, i*8+4, i*8+5]);break;
                case "5": //111001
                    arr.push(...[i*8+3, i*8+4]);break;
                case "6": //111010
                    arr.push(...[i*8+3, i*8+5]);break;
                case "7": //111011
                    arr.push(...[i*8+3]);break;
                case "8": //111100
                    arr.push(...[i*8+4, i*8+5]);break;
                case "9": //111101
                    arr.push(...[i*8+4]);break;
                case "+": //111110
                    arr.push(...[i*8+5]);break;
            }
        }
        return arr;
    }
    return [];
}

有人知道如何加快速度吗？

EDIT2+3

我将函数移到了单独的代码中，其行为保持不变，但允许我在其他函数中重用它。后来根据@Jonas 的建议，我尝试避免字符串转换：

Buffer.prototype.toIntegerArray = function() {
    const buffLenght = this.length;
    if (buffLenght > 0) {
        const arr = Array();
        arr.lenght = buffLenght * 8
        for (var i = 0; i < buffLenght; i++) {
            //iterating through 8-bit chunks
            for (var l = 0; l < 8; l++) {
                //push int to array for each bloom 0 value - not used bit
                //corrected syntax
                if (((this[i] >> l) & 1) === 0) {
                    arr.push(i*8 + l);
                }
            }
        }
        return arr;
    }
    return [];
}

根据@Jonas 的评论，更正后的语法确实找到了零。通过控制台时间戳测量查询的数组构建部分，平均 10 个查询响应，所有 0 的 65536 位布隆大小（最终随机半全布隆，所有布隆相同）：

toString(2).padStart(8, '0') => ~ 303 毫秒 (152 毫秒)
switch => ~322 毫秒（145 毫秒）
(((this[i] >> l) & 1) === 0) => ~340 毫秒
(var mask = 0x80; mask > 0; mask>>=1) => ~354ms
if ((byte & 0x80) === 0) arr.push(counter); => 314 毫秒（158 毫秒）

正如我从测量中注意到的那样，循环遍历全 0 数组和随机半盛放有很大的不同。因此，我猜更大的部分会自己推动。

我知道测量有部分误导性，但环境是给定的（Parse Server 云功能），不幸的是，我没有那么丰富的经验，无法在那里进行更复杂的调查。越难是DBaaS上的共享服务器

Answer 1

当您避免使用 .toString(2) 转换为字符串时，它应该会有所改善。也可以通过使用单独的计数器变量来避免重复的 i*8+l：

for (var i = 0, counter = 0; i < buf.length; i++) {
    var byte = buf[i];
    for (var mask = 0x80; mask > 0; mask>>=1) {
        if ((byte & mask) === 0) {
            blm.push(counter);
        }
        counter++;
    }
}

由于内部循环只有 8 次迭代，您也可以将代码复制 8 次，从而减少移位操作：

for (var i = 0, counter = 0; i < buf.length; i++, counter+=8) {
    var byte = buf[i];
    if ((byte & 0x80) === 0) blm.push(counter);
    if ((byte & 0x40) === 0) blm.push(counter+1);
    if ((byte & 0x20) === 0) blm.push(counter+2);
    if ((byte & 0x10) === 0) blm.push(counter+3);
    if ((byte & 0x08) === 0) blm.push(counter+4);
    if ((byte & 0x04) === 0) blm.push(counter+5);
    if ((byte & 0x02) === 0) blm.push(counter+6);
    if ((byte & 0x01) === 0) blm.push(counter+7);
}

跳过 base64 解码的想法也是一个很好的尝试，尽管这意味着在纯 JavaScript 中有更长的字符串要迭代（而不是在更低、更快的级别上发生这种情况）。尽管如此，在您的尝试中仍有一些需要改进的地方：构建一个数组然后传播它是浪费时间。您可以将这些参数直接传递给 push。例如：

case "A": //000000
    arr.push(i*8, i*8+1, i*8+2, i*8+3, i*8+4, i*8+5);break;

此外，应避免重复 i*8（与上述相同的解决方案）。

JavaScript base64string -> 二进制值 -> [整数] ... 性能改进

JavaScript base64string -> binary values -> [Integer] ... performance improvement

javascript

binary

base64