javascript - 如何有效地将预定义大小的大块分割成较小的 block ，这些 block 是 JavaScript 中大小的因素？

Question

假设我们有这样的结构:

// 16 bins
let BIN_OF_BINS = [
  [], // 128 bits each chunk
  [], // 256
  [], // 512
  [], // 1024
  [], // 2048
  [], // 4096
  [], // 8192
  [], // 16384
  [], // 32768
  [], // 65536
  [], // 131072
  [], // 262144
  [], // 524288
  [], // 1048576
  [], // 2097152
  [{ start: 0, count: 100 }], // 4194304
]

BIN_OF_BINS 中的每个 bin保存一组代表内存中插槽的节点。 n+1 bin 包含两倍于 n bin 大小的节点。所以第一个 bin 保存 128 位值，下一个保存 256 位值，下一个 512 等等。一个 bin 中包含的值可以是连续的，所以我们可能在“256 位值 bin”中有一个 1024 位的连续 block ，所以这将表示为:

bin2 = [{ count: 4, addressStartsAt: 0 }]

如果它有两个不连续的 1024 block ，它将是:

bin2 = [
  { count: 4, addressStartsAt: 0 },
  { count: 4, addressStartsAt: 4096 /* let's say */ }
]

原则上，您可以在使用和释放内存时从这些 bin 中添加和删除。但是对于这个问题，我们只关心使用释放的内存(即我们不关心为这个问题释放内存)。
所以当 BIN_OF_BINS开始时，只有顶部的 bin 有 100 个值。所以我们从这个开始:

// 16 bins
let BIN_OF_BINS = [
  [], // 128 bits each chunk
  [], // 256
  [], // 512
  [], // 1024
  [], // 2048
  [], // 4096
  [], // 8192
  [], // 16384
  [], // 32768
  [], // 65536
  [], // 131072
  [], // 262144
  [], // 524288
  [], // 1048576
  [], // 2097152
  [{ start: 0, count: 100 }], // 4194304
]

现在，当我们去获取一个 256 位的值时，我们发现没有，所以它遍历列表到更大的 bin，并将它分成两半(或者做一些其他的事情，我会谈到)。因此，如果我们从全新的 BIN_OF_BINS 请求 1 256 值，我们不断地往上爬，直到我们到达顶峰才发现没有。然后我们迭代划分。从 4194304 开始，下面是它的运行方式(在我们已经遍历空白的到达顶部之后):

// step 0
[{ start: 0, count: 100 }], // 4194304, bin 16

// step 1
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 0, count: 2 }], // 2097152, bin 15

// step 2
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 2097152, count: 1 }], // 2097152, bin 15
[{ start: 0, count: 2 }], // 1048576, bin 14

// step 3
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 2097152, count: 1 }], // 2097152, bin 15
[{ start: 1048576, count: 1 }], // 1048576, bin 14
[{ start: 0, count: 2 }] // 524288, bin 13

// etc.

我们一直这样划分，直到我们最终得到:

[{ start: 0, count: 2 }] // 256, bin 2

现在我们可以从这个“bin 2”中获取一个“256 位内存槽”，只需执行以下操作:

node.start += 256
node.count--

我们最终得到:

[{ start: 256, count: 1 }] // 256, bin 2

问题是，如何有效地实现？对我来说，这非常令人困惑和难以理解。

当获取一个大小(这将只是前 4 个 bin 之一)时，如果不存在，请尝试从父级获取并分成两半。

如果父级没有，则分割其父级。

等

基本上就是这样。这是我到目前为止所拥有的。我想在没有递归的情况下执行此操作(仅使用带有循环的迭代方法)，因为它将在没有递归的地方使用。

// 16 bins
let BINS = [
  [], // 4 32-bit values, so 128 bits each chunk
  [], // 8 32-bit values, so 256
  [], // 16 32-bit values, so 512
  [], // 32 32-bit values, so 1024
  [], // 2048
  [], // 4096
  [], // 8192
  [], // 16384
  [], // 32768
  [], // 65536
  [], // 131072
  [], // 262144
  [], // 524288
  [], // 1048576
  [], // 2097152
  [{ start: 0, count: 100 }], // 4194304
]

function fetchBlockWithAllocation(i) {
  let block = fetchBlock(i)
  if (!block) prepareBlocks(i)
  return fetchBlock(i)
}

function fetchBlock(i) {
  if (!BINS[i].length) {
    return -1
  }

  let bin = BINS[i]
  let node = bin[0]
  let address = node.start
  node.count--
  node.start += i * 32
  if (!node.count) {
    bin.shift()
  }
  return address
}

function prepareBlocks(index, howMany = 1024) {
  let startBinIndex = index + 1
  let scaleFactor = 1
  while (startBinIndex < 16) {
    let bin = BINS[startBinIndex++]
    if (bin.length) {
      for (let k = 0, n = bin.length; k < n; k++) {
        let node = bin[k]
        while (node.count) {
          howMany -= scaleFactor
          node.count--
        }
      }
      // starting to get lost
    } else {

    }
  }
}

堆栈/迭代方面让我绊倒了。似乎我缺少一些简单的东西来创建一个优雅的解决方案，而我正在偏离轨道。我有 prepareBlocks预先分配一堆 block ，所以当它没有找到时，它会批量执行，作为一种优化。理想情况下，它无需创建任何其他临时数组即可执行此操作。
我一直在想:

• Bring down the next level.
• How many do we have left?
• Bring down the next level.
• How many do we have left?

以更递归的方式尝试，我仍然陷入同一点:

let BINS = [
  { count: 0, array: [] }, // 4 32-bit values, so 128 bits each chunk
  { count: 0, array: [] }, // 8 32-bit values, so 256
  { count: 0, array: [] }, // 16 32-bit values, so 512
  { count: 0, array: [] }, // 32 32-bit values, so 1024
  { count: 0, array: [] }, // 2048
  { count: 0, array: [] }, // 4096
  { count: 0, array: [] }, // 8192
  { count: 0, array: [] }, // 16384
  { count: 0, array: [] }, // 32768
  { count: 0, array: [] }, // 65536
  { count: 0, array: [] }, // 131072
  { count: 0, array: [] }, // 262144
  { count: 0, array: [] }, // 524288
  { count: 0, array: [] }, // 1048576
  { count: 0, array: [] }, // 2097152
  { count: 0, array: [ { start: 0, count: 100 }] }, // 4194304
]

function prepareBlocks(index, minHowMany = 1024) {
  let bin = BINS[index]
  if (bin.count === 0) {
    return prepareBlocks(index + 1, Math.ceil(minHowMany / 2))
  } else {
    let diff = Math.max(0, bin.count - minHowMany)
    if (diff <= 0) {
      return prepareBlocks(index + 1, Math.ceil(minHowMany / 2))
    } else {
      for (let k = 0, n = bin.length; k < n; k++) {
        let node = bin[k]
        if (node.count >= minHowMany) {
          node.count -= minHowMany
        } else {
          // getting lost at same point
        }
      }
    }
  }
}

就好像它必须在每个列表中的第一个项目中进行曲折，然后是第二个，等等，所以它只划分它需要的东西。
最新的伪代码是:

function allocateBunch(base, size, count) {
  let desiredBits = size * count
  let totalBits = 0
  for bin, i in bins
    let blockBits = 128 << i
    while (bin.length)
      block = bin[0]
      let k = 0
      let totalNewBits = block.count * blockBits
      let totalWithNewBits = totalBits + totalNewBits
      let diff = Math.floor(totalNewBits - desiredBits / blockBits)
      block.count -= diff
      let newChildBlock = { count: diff * (2 ** i) }
      base.push(newChildBlock)
      totalWithNewBits >= desiredBits
        return
      bin.shift()
}

注意:在寻找一个时它预先分配多少并不重要，我会说最大 4096 或其他东西，因为它看起来足够合理。因此，在尝试获取一个 block 时，只需从最近的任何地方划分，一直向下，这样您就可以获得更多所需大小的 block 。如果还不够，那就重复这个过程。只是不知道怎么做。
另请注意，如果您考虑如何在此系统中“释放内存”，您可以在与奇数配对时合并每个节点，并将它们合并起来，这样您就会得到越来越大的 block 。也许这会影响您如何实现这一点，只是想指出。
还要寻求最大效率，我的意思是尽可能使用缓存或非天真的解决方案(例如重复进行计算或做不必要的工作)。
Bounty 将转到最优化的版本(在执行步骤、无递归等方面)，这也很简单。

Answer 1

function allocate(bits) {
    if ((bits & (bits - 1)) != 0) {
        throw "Parameter is not a power of 2";
    }

    if (bits < 128 || bits > 4194304) {
        throw "Bits required out of range";
    }
    
    var startBinIndex = Math.log2(bits >> 7);
    var lastBin = BIN_OF_BINS.length - 1;

    
    for (var binIndex = 0; binIndex <= lastBin ; binIndex++) {
        var bin = BIN_OF_BINS[binIndex];

        //
        // We have found a bin that is not empty...
        //
        if (bin.length != 0) {
            //
            // Calculate amount of memory this bin takes up
            //
            var thisBinMemorySize = (128 << binIndex);
            var enoughMemory = thisBinMemorySize >= bits;


            if (!enoughMemory) {
                //
                // This bin is too small, but it may have continuous blocks, so lets find a continuous block big enough to accomodate the size we want...
                //
                for (var b = 0; b < bin.length; b++) {
                    var blockOfInterest = bin[b];
                    var blockSize = blockOfInterest.count * thisBinMemorySize;
                    //
                    // We've found a continous block in the lower size bin that fits the amount we want
                    //
                    if (blockSize >= bits) {
                        //
                        // We are going to return this block
                        //
                        var allocatedMemoryBlock = {start : blockOfInterest.start, count : 1};
                        //
                        // Perfect size, we are simply going to delete the whole block
                        //
                        if (blockSize == bits) {
                            bin.splice(b);
                        }
                        else {
                            //
                            // Otherwise we'll take what we need and adjust the count and adjust the start address
                            //
                            blockOfInterest.start += bits;
                            blockOfInterest.count -= bits / thisBinMemorySize; // because we are working in power of 2 we'll never get remainder
                        }

                        return allocatedMemoryBlock;
                    }
                }
                //
                // Failed to find a block big enough so keep searching
                //
            }
            else {
                //
                // This big enough even with just 1 block...
                //
                console.log(thisBinMemorySize);

                //
                // We are going to return this block
                //
                var lastBinOfBinsIndex = bin.length - 1;
                var binBlock = bin[lastBinOfBinsIndex];
                var memoryAddress = binBlock.start;


                //
                // We are going to return this block
                //
                var allocatedMemoryBlock = {start : memoryAddress, count : 1};

                //
                // Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
                //
                if (binBlock.count == 1) {
                    bin.pop();
                }
                else {
                    binBlock.count--;
                    binBlock.start += thisBinMemorySize;
                }
                
                //
                // if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280 
                // if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
                //
                var remainingUnsedMemory = thisBinMemorySize - bits;
                var adjustmentSize = bits;
                while (remainingUnsedMemory != 0) {
                    memoryAddress += adjustmentSize;

                    BIN_OF_BINS[startBinIndex].push({start : memoryAddress, count : 1});
                    startBinIndex++;
                    remainingUnsedMemory -= bits;
                    adjustmentSize = bits;
                    bits <<= 1;
                }

                return allocatedMemoryBlock;
            }
        }
    }
    return null; // out of memory...
}

console.log("Memory returned:", allocate((128 << 1)));
for (i = 0; i < BIN_OF_BINS.length; i++) {
    console.log(JSON.stringify(BIN_OF_BINS[i]));
}

分配 4096 x 128 block

//
// Allocate 524288 bytes...
//
var memorySize = 128 << 12; 
var memoryAllocated = allocate(memorySize); 

// Adjust the count to 524288 / 128 to give 4096 blocks of 128
memoryAllocated.count = (memorySize / 128);

// Put the allocated memory back on the BIN_OF_BINS stack
BIN_OF_BINS[0].push(memoryAllocated);


for (i = 0; i < BIN_OF_BINS.length; i++) {
    console.log(JSON.stringify(BIN_OF_BINS[i]));
}

已添加
下面的版本与第一个版本非常相似，只是它不通过较小的垃圾箱。

function allocate(bits) {
    if ((bits & (bits - 1)) != 0) {
        throw "Parameter is not a power of 2";
    }

    if (bits < 128 || bits > 4194304) {
        throw "Bits required out of range";
    }
    
    var startBinIndex = Math.log2(bits >> 7);
    var lastBin = BIN_OF_BINS.length - 1;

    
    for (var binIndex = startBinIndex; binIndex <= lastBin ; binIndex++) {
        var bin = BIN_OF_BINS[binIndex];

        //
        // We have found a bin that is not empty...
        //
        if (bin.length != 0) {
            //
            // Calculate amount of memory this bin takes up
            //
            var thisBinMemorySize = (128 << binIndex);
            var lastBinOfBinsIndex = bin.length - 1;
            var binBlock = bin[lastBinOfBinsIndex];
            var memoryAddress = binBlock.start;


            //
            // We are going to return this block
            //
            var allocatedMemoryBlock = {start : memoryAddress, count : 1};

            //
            // Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
            //
            if (binBlock.count == 1) {
                bin.pop();
            }
            else {
                binBlock.count--;
                binBlock.start += thisBinMemorySize;
            }
            
            //
            // if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280 
            // if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
            //
            var remainingUnsedMemory = thisBinMemorySize - bits;
            var adjustmentSize = bits;
            while (remainingUnsedMemory != 0) {
                memoryAddress += adjustmentSize;

                BIN_OF_BINS[startBinIndex].push({start : memoryAddress, count : 1});
                startBinIndex++;
                remainingUnsedMemory -= bits;
                adjustmentSize = bits;
                bits <<= 1;
            }

            return allocatedMemoryBlock;
        }
    }
    return null; // out of memory...
}