Say I have items like this, where foo and bar are simple instructions, and a and b are simple instruction blocks:
a:
foo 1
foo 2
bar 10
bar 20
foo 1
bar 30
b:
foo 20
bar 30
foo 10
foo 100
bar 31
...
The corresponding data structure is sort of like this:
const blocks = [
[
{ type: 'foo', val: 1 },
{ type: 'foo', val: 2 },
{ type: 'bar', val: 10 },
{ type: 'bar', val: 20 },
...
],
...
]
The goal is to, starting from the first block in blocks, to iterate through all the blocks and lay them out in a certain way in memory:
<foo><1><foo><2>...
Or more generally:
<type><val><type><val>...
Where each <> angle bracket object symbolizes a 32-bit integer (assume foo == 1 and bar == 2 or something). So this:
a:
foo 1
foo 2
bar 10
bar 20
foo 1
bar 30
Becomes this:
<foo><1><foo><2><bar><10><bar><20><foo><1><bar><30>
or
32 32 32 32 32 32 32 32 32 32 32 32
Notice that each instruction only takes one parameter, so the memory layout for each "instruction call" takes only 2 32-bit slots.
The thing is though, we have to adhere to the following constraint: We only allow contiguous sequences of 1, 2, 4, 8, 16, 32, 64, or 128 32-bit integers. If the instruction block doesn't fit those patterns, you can combine it with (part of) a subsequent block, or divide it into a chunk that fits the contiguous array constraint. BUT, you ALSO have to add 4 32-bit integers (a foo and a bar) to the end of whatever chunk you create, and that in total must reach 1, 2, 4, 8, 16, 32, 64, or 128 items.
So the question is, how do you take an array of blocks like we've started above, and most efficiently transform them into a set of contiguous memory allocations of those certain sizes? By "efficiently" I don't necessarily mean the performance of the algorithm that chunks the blocks, but rather, that the final chunks take up the ideal amount of space (ideally filling 128 slots, then 64, then 32, etc.). The goal is we want to pack the instructions into as many large contiguous arrays as we can.
For example, take this:
a:
foo 1
foo 2
bar 10
bar 20
foo 1
bar 30
There are 6 instructions, so 12 32-bit values. But 12 isn't 1, 2, 4, 8, 16, 32, 64, or 128. So what we need to do is break somewhere to make it one of these 6 contiguous array sizes. BUT, we can only break AFTER a bar. In addition, we need to account for linking between the contiguous arrays. So we add an extra special pair of instructions adding an additional 4 32-bit values to the equation (a foo and a bar). So wherever we decide to split, we need to insert 4 extra 32-bit values which will encode the address and the instruction for jumping to the next contiguous array.
So in our example, we might do this:
a_1:
foo 1 # 2
foo 2 # 4
bar 10 # 6
bar 20 # 8
foo 1 # 10
bar 30 # 12
<ins1> x # 14
<ins2> y # 16
That correctly balances to a 16-item contiguous array.
Here is an example that takes up 10 32-bit slots (14 if you imagine trying to divide it). Neither of these sizes fits the constraints.
x:
foo 1
bar 2
foo 1
foo 1
bar 3
If we were only dealing with this 1 instruction block (and not a collection of instruction blocks), then we might end up with this:
foo 1
bar 2
foo 1
foo 1
bar 3
<insert-foo>
<insert-bar>
<empty><empty>
That equals 16 too. It is okay to leave trailing space in the contiguous array. But you don't want to create too much trailing empty space haha.
A final example is of 16 items:
foo 1 # 2
foo 1 # 4
bar 2 # 6
foo 1 # 8
bar 3 # 10
foo 1 # 12
bar 3 # 14
bar 5 # 16
Adding the 2 extra instructions gets us to 20, which doesn't fit the constraints.
# NOPE
foo 1 # 2
foo 1 # 4
bar 2 # 6
foo 1 # 8
bar 3 # 10
foo 1 # 12
bar 3 # 14
bar 5 # 16
<ins-foo> # 18
<ins-bar> # 20
We could add empty space at the end:
foo 1 # 2
foo 1 # 4
bar 2 # 6
foo 1 # 8
bar 3 # 10
foo 1 # 12
bar 3 # 14
bar 5 # 16
<ins-foo> # 18
<ins-bar> # 20
<empty-pair> # 22
<empty-pair> # 24
<empty-pair> # 26
<empty-pair> # 28
<empty-pair> # 30
<empty-pair> # 32
But if we did that a lot, that would be a lot of wasted space. A better solution is this:
# block 1
foo 1 # 2
foo 1 # 4
bar 2 # 6
foo 1 # 8
bar 3 # 10
<ins-foo> # 12
<ins-bar> # 14
<empty-pair> # 16
# block 2
foo 1 # 2
bar 3 # 4
bar 5 # 6
<ins-foo> # 8
<ins-bar> # 10
<empty-pair> # 12
<empty-pair> # 14
<empty-pair> # 16
Because it minimizes the empty trailing pairs.
So what I did first here is generate some demo data to test against: a bunch of blocks with random sizes and random combinations of foo/bar sequences. This simulates a production-sized programs with various instruction blocks doing various things:
const blocks = rand_block_collection()
function rand_block_collection() {
let rand_i = rand_int(70, 80)
const blocks = []
while (rand_i--) {
blocks.push(rand_block())
}
return blocks
}
function rand_block() {
let rand_i = rand_int(2, 40)
const block = []
while (rand_i--) {
let rand_seq = [ rand_seq_0, rand_seq_1, rand_seq_2 ][rand_int(0, 2)]
block.push.apply(block, rand_seq())
}
return block
}
function rand_seq_0() {
return [
{ type: 'bar', val: rand_int(0, 255) }
]
}
function rand_seq_1() {
return [
{ type: 'foo', val: rand_int(0, 255) },
{ type: 'bar', val: rand_int(0, 255) }
]
}
function rand_seq_2() {
return [
{ type: 'foo', val: rand_int(0, 255) },
{ type: 'foo', val: rand_int(0, 255) },
{ type: 'bar', val: rand_int(0, 255) }
]
}
function rand_int(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min
}
That gives some demo data below.
So the goal is to take that blocks array and come up with an algorithm to generate multiple contiguous arrays of 2, 4, 6, 8, 16, 32, 64, or 128 items in length, following the additional rule that you have to add 4 32-bit values (a foo and a bar) to the sequence that will be the call to jump to the next contiguous array.
How would you do that? What is a decent algorithm, or an optimal algorithm in JS?
let xhr = new XMLHttpRequest()
xhr.open('GET', 'https://gist.githubusercontent.com/lancejpollard/e75e0e5e091064d54a9d9502316b1c4c/raw/9d3276f9a712e6547b8ba44d009475a1b945f684/instblock.json')
xhr.onreadystatechange = function(){
if (xhr.readyState !== 4) return
if (xhr.status !== 200) return
const blocks = JSON.parse(xhr.responseText)
const chunks = divide(blocks)
console.log('chunks', chunks)
}
xhr.send()
function divide(blocks) {
const SIZEOF_LINK = 4
const MAX_CHUNK_SIZE = 128
let chunk = []
let seq = []
let next = []
let chunks = [chunk]
blocks.forEach(block => {
block.forEach(inst => {
chunk.push(inst)
if (inst.type == 'bar') {
const size = chunk.length + SIZEOF_LINK
if (size >= MAX_CHUNK_SIZE - 3 && size <= MAX_CHUNK_SIZE) {
// add special instructions
chunk.push({ type: 'foo', val: 1 })
chunk.push({ type: 'bar', val: 100 })
chunk = []
chunks.push(chunk)
}
// divide if it's optimal to divide.
}
})
})
return chunks
}Did I do this right?