Lan*_*ard 5 javascript iteration algorithm
假设我们有这样的结构：
// 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
]
中的每个 binBIN_OF_BINS包含一组代表内存中插槽的节点。n+1 bin 包含两倍于 n bin 大小的节点。所以第一个 bin 包含 128 位值，下一个包含 256 位值，接下来是 512 位值，等等。 bin 中包含的值可以是连续的，所以我们可能在“256 位值 bin”中有一个 1024 位的连续块，因此将表示为：
bin2 = [{ count: 4, addressStartsAt: 0 }]
如果它有两个不连续的 1024 块，它将是：
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，并将它分成两半（或者做一些其他的事情，我会讲到）。因此，如果我们从一个全新的 中请求 1 256 值BIN_OF_BINS，我们会一直向上，直到到达顶部为止都找不到。然后我们迭代划分。从 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
问题是，如何有效地实现这一点？对我来说，这非常令人困惑和难以理解。
基本上就是这样。这是我到目前为止所拥有的。我想在没有递归的情况下执行此操作（仅使用带有循环的迭代方法），因为它将在没有递归的地方使用。
// 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
]
堆栈/迭代方面让我绊倒了。似乎我缺少一些简单的东西来创建一个优雅的解决方案，我正在偏离轨道。我有prepareBlocks到预分配一堆块，所以它像是做它在散装只要找到没有，作为优化。理想情况下，它无需创建任何其他临时数组即可完成此操作。
我一直在想：
- 降低下一个级别。
- 我们还剩下多少？
- 降低下一个级别。
- 我们还剩下多少？
尝试以更递归的方式，我仍然卡在同一点上：
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()
}
注意：在寻找一个时预分配多少并不重要，我会说 max 4096 或者只是因为看起来足够合理。因此，在尝试获取块时，只需从最近的地方一直向下划分，这样您就可以获得所需大小的更多块。如果这还不够，那么只需重复该过程。只是不确定如何。
另请注意，如果您考虑如何在此系统中“释放内存”，则可以在与奇数配对时合并每个节点，然后将它们合并，这样您就会得到越来越大的块。也许这会影响您如何实现这一点，只是想指出。
寻求最高效率，我的意思是如果可能的话使用缓存或非幼稚的解决方案（例如重复进行计算或做不必要的工作）。
赏金将转到最优化的版本（在执行步骤、无递归等方面），这也很简单。
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 块
//
// 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...
}
| 归档时间： |
|
| 查看次数： |
214 次 |
| 最近记录： |