How to efficiently segment a large block of predefined size into smaller blocks that are factors of its size in JavaScript?

user_169992 0
Viewed 244

Say we have this structure:

// 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
]

Each bin in the BIN_OF_BINS hold a set of nodes representing slots in memory. The n+1 bin holds nodes of twice the size of the n bin. So the first bin holds 128 bit values, the next holds 256 bit values, the next 512, etc. The values contained in a bin can be contiguous, so we might have in the "256 bit value bin" a contiguous chunk of 1024 bits, so that would be represented with:

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

If it had two non-contiguous chunks of 1024, it would be:

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

In principle, you can add and remove from these bins as memory is used and freed. But for this question, we are only concerned with using freed memory (i.e. we are not concerned with freeing memory for this question).

So when the BIN_OF_BINS starts, only the top bin has let's say 100 values. So we start with this:

// 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
]

Now, when we go to fetch a 256 bit value, we find there are none, so it traverses up the list to larger bins, and divides it in half (or does some other thing, which I'll get to). So if we request 1 256 value from a brand new BIN_OF_BINS, we go up and up and up, finding none until we get to the top. Then we iteratively divide. Starting with 4194304, here is how it goes (after we already iterated through the blank ones to get to the top):

// 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.

We keep dividing like that until we end up with:

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

Now we can fetch from this "bin 2" a "256 bit memory slot" by simply doing:

node.start += 256
node.count--

And we end up with:

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

The question is, how can this be implemented efficiently? It is very confusing and difficult for me to wrap my head around.

  • When fetching for a size (which will only be one of the first 4 bins), if none exist, try fetching from the parent and dividing in half.
  • If parent doesn't have any, subdivide its parent.
  • etc.

That's basically it. Here's what I have so far. I would like to do this without recursion (using just an iterative approach with loops), because it will be used in a place without recursion.

// 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 {

    }
  }
}

The stack/iteration aspect gets me tripped up. It seems like there is something simple which I am missing to create an elegant solution, and I am going off the track. I have the prepareBlocks to preallocate a bunch of blocks, so it sort of does it in bulk whenever it finds none, as an optimization. Ideally it does this without having to create any other temporary arrays.

I keep thinking:

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

Attempting in a more recursive fashion, I still get stuck around the same point:

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
        }
      }
    }
  }
}

It's almost as if it must zig-zag through the first items in each list, then the second, etc., so it only divides what it needs.

Latest pseudocode is:

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()
}

Note: It doesn't really matter how many it preallocates when looking for one, I would say max 4096 or something just because seems reasonable enough. So in trying to fetch a block, just divide from wherever is closest, all the way down so you get that many more blocks at your desired size. If it's not enough, then just repeat the process. Just not sure how to yet.

Also note, if you consider how to "free memory" in this system, you could merge every node when paired with an odd value, and merge them up, so you get larger and larger blocks. Maybe that affects how you were to implement this, just wanted to point out.

Looking for maximum efficiency as well, by that I mean using caching or non-naive solutions if possible (such as repeatedly doing calculations or doing more work than necessary).

Bounty will go to most optimized version (in terms of execution steps, no recursion, etc.) that is also straightforward.

iteration algorithm javascript
2 Answers

One way to do it without recursion is to "follow" the descending block. So you loop up until you find a parent with a block (idx will increment) then loop down until you reach the child (idx will decrement).

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
]

function blockCount(binNumber) {
    return BIN_OF_BINS[binNumber].length
}

function totalBlockCount(binNumber) {
    let count = 0
    for (let idx = 0; idx < blockCount(binNumber); idx++) {
        count += BIN_OF_BINS[binNumber][idx].count
    }
    return count
}

function noBlocks(binNumber) {
    return blockCount(binNumber) === 0
}

function bitsPerBlock(binNumber) {
    return 2 ** (binNumber + 7)
}

function largestBlockIdx(binNumber) {
    if (noBlocks(binNumber)) {
        return -1
    }
    let largestIdx = 0
    for (let idx = 1; idx < blockCount(binNumber); idx++) {
        if (BIN_OF_BINS[binNumber][idx].count > BIN_OF_BINS[binNumber][largestIdx].count) {
            largestIdx = idx
        }
    }
    return largestIdx
}

function lastBlockIdx(binNumber) {
    return blockCount(binNumber) - 1
}

function descendBlock(binNumber) {
    // attempt to descend a block to the next bin, return true if successful and false otherwise

    let largestIdx = largestBlockIdx(binNumber)
    if (largestIdx < 0 || binNumber == 0) {
        return false
    }

    BIN_OF_BINS[binNumber][largestIdx].count--
    BIN_OF_BINS[binNumber][largestIdx].start += bitsPerBlock(binNumber)

    if (BIN_OF_BINS[binNumber][largestIdx].count == 0) {
        // we cab safely reset here because we know that it was the biggest and now it has no blocks
        BIN_OF_BINS[binNumber] = []
    }


    // count = 2 because a block from the next highest bin is always twice the size of the block from the current bin
    let lastIdx = lastBlockIdx(binNumber - 1)
    if (lastIdx < 0) {
        BIN_OF_BINS[binNumber - 1][0] = { start: 0, count: 2}
    } else {
        BIN_OF_BINS[binNumber - 1][lastIdx].count += 2
    }

    return true
}

function descendAllBlocks(binNumber) {
    while (descendBlock(binNumber));
}

function allocate(binNumber, minBlockCount) {
    while (totalBlockCount(binNumber) < minBlockCount) {
        // allocate to the binNumber bin from its earliest parent, cascading allocations down the chain if required
        // conceptually, we are looping in two directions - up until we find a bin that can descend a block, then back down
        // as we descend it
        for (let binIndexA = binNumber + 1; binIndexA < BIN_OF_BINS.length; binIndexA++) {
            if (descendBlock(binIndexA)) {
                for (let binIndexB = binIndexA - 1; binIndexB > binNumber; binIndexB--) {
                    descendAllBlocks(binIndexB) // to achieve the example result
                    // descendBlock(binIndexA) // take only what you need, leaving behind 1 block in each bin
                }
                break
            }
        }
    }
}


allocate(1, 1)
console.log(BIN_OF_BINS)
/*
[
  [],
  [ { start: 0, count: 16384 } ],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [ { start: 4194304, count: 99 } ]
]
*/
user_90642060 
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]));
}

To allocate 4096 x 128 blocks

//
// 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]));
}

ADDED

The version below is very similar to first version only it doesn't go through the smaller bins.

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...
}
user_13675690
Related