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

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: 1048576, count: 1 }], // 2097152, bin 15
[{ start: 0, count: 2 }], // 1048576, bin 14

// step 3
[{ start: 4194304, count: 99 }], // 4194304, bin 16
[{ start: 1048576, count: 1 }], // 2097152, bin 15
[{ start: 524288, 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.

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.

from Recent Questions - Stack Overflow https://ift.tt/2Zr3Fft
https://ift.tt/eA8V8J