SebLague
[Potential Optimization] Truth Table Cache for Static Gates
The idea is to, instead of just running all the gates inside a chip, to calculate what should come out of a chip you first calculate a Truth Table by providing every possible input combination and mapping the input combinations to outputs. This truth table is equivalent to the chip, up to implementation detail. (for instance, where all the chips are and how the wires are arranged)
The creation of a truth table can even speed up the rate at which a larger truth table containing the equivalent chip is created, in the same way that it speeds up the running of a chip inside a larger chip. The truth table could either be inferred from the gates (harder, more prone to errors) or just created by running the chip for all possible inputs. (easier, takes exponential time to complete based on the number of inputs)
Let us consider a chip like this:
As you can probably already tell, this is a Half Adder. It takes in 2 binary inputs and adds them together.
This is it's truth table:
| A | B | A&B | A^B |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 |
Instead of evaluating the individual XOR (represented with the ^ symbol) and AND (represented with the & symbol) gates, you could evaluate the truth table without having the evaluate individual gates any more than required to create the truth table. For 2 (1-bit) inputs, that's 4 times. Though, the size scales with the number of inputs - for just a 4-bit XOR, (bitwise XOR on 4-bit numbers) you need 2^8 repeated runs of the gate, which for more complex gates (which tend to have more inputs, further increasing the time increased) could take a few seconds to a few minutes. Maybe even more if people decide to make really complex "gates". (they probably wouldn't be called gates anymore) This would likely be ran only when saving the chip, which for larger chips will likely happen infrequently. The chip can still be called upon without the generation of an Truth Table, though it'd be slower than with one. This means that a truth table can be generated in the background while other stuff (such as creating another new chip) is done, even if that involves the chip a truth table is being generated for. Then, once the truth table is complete, the simulation starts applying the speedup technique of using Truth Tables. This makes them more like a cache, being faster-access memory, with smaller storage size. (except instead of reduced storage size, this cache-like behaviour has a slower write time, so I guess it's also kind of like a ROM in that way)
Truth tables wouldn't make much difference to built-in chips, since they're made directly in C# instead of implemented through the abstraction layer of gates. I guess this cleaner notation can be adopted for chips with multi-bit inputs, where we use the whole input bitstring as 1 input. (exactly as treated in the simulation)
| A | B | A&B |
|---|---|---|
| 11 | 11 | 11 |
| 11 | 10 | 10 |
| 10 | 11 | 10 |
| 10 | 10 | 10 |
| 11 | 01 | 01 |
| 01 | 11 | 01 |
| 10 | 01 | 00 |
| 01 | 10 | 00 |
| 01 | 01 | 01 |
| 11 | 00 | 00 |
| 00 | 11 | 00 |
| 10 | 00 | 00 |
| 00 | 10 | 00 |
| 01 | 00 | 00 |
| 00 | 00 | 00 |
In case you didn't know, that truth table is bitwise AND on 2-bit numbers.
Here's an example as a gate:
As you can see, for more complicated gates, it's easier to view the chip rather than the truth table, since the truth table doesn't hide any layers of abstraction, (the gates/chips) where-as the simulation's view gives a more high-level overview over the chip.
The fact that the simulation view is expanded in both directions, where-as the truth table is primarily expanded in the downward direction. (or sometimes the rightward direction)
This is similar to how high-level languages (that's why I called it a "high-level overview") are (usually) easier to read than low-level languages, like assembly. I don't want this issue to go on for that much longer, so I'll end it here.
I think that this is a really clever idea - you're basically talking about chip memoization.
The problem is that not all chips will have the same output given a particular input. Take a counter that has an "Increment" or "Decrement" input and a clock signal. The output will vary based on some internal state despite the same arrangement of those Increment and Decrement pins. No doubt that this is what you were getting at by specifying "Static" chips - chips that wouldn't have an internal state, the equivalent of a Pure Function in chip land.
The real problem is, how can one determine if a chip is, in fact, a stateless chip, programmatically? The presence of some kind of flip-flop, which uses loopback circuitry, is certainly a strong signal, but I don't think it follows that the presence of loopback circuitry guarantees that a chip is stateful, and I'm not certain that a stateful chip has to have loopback circuitry.
I think that this is a really clever idea - you're basically talking about chip memoization.
The problem is that not all chips will have the same output given a particular input. Take a counter that has an "Increment" or "Decrement" input and a clock signal. The output will vary based on some internal state despite the same arrangement of those Increment and Decrement pins. No doubt that this is what you were getting at by specifying "Static" chips - chips that wouldn't have an internal state, the equivalent of a Pure Function in chip land.
The real problem is, how can one determine if a chip is, in fact, a stateless chip, programmatically? The presence of some kind of flip-flop, which uses loopback circuitry, is certainly a strong signal, but I don't think it follows that the presence of loopback circuitry guarantees that a chip is stateful, and I'm not certain that a stateful chip has to have loopback circuitry.
Hmmm... Well, this chip stores a state, it just doesn't have a way to change to another state without an error occuring in one of the AND gates causing it to output 1 instead of 0:
That means that the chip should probably be classified as non-static, since it has 2 possible states for the same chip layout and inputs.
I think it's safe to say that any chip containing non-static chips is itself non-static. The only false positives would be when the non-static chip is disconnected, with no output. (because you can make non-static chips with no inputs, but any non-static chip would be useless without connected outputs) These can themselves be detected. Though, at this point, we're traversing into the realm of inferring the Truth Table from gates directly, since we're now analyzing the chip as a whole, instead of just considering how the chip behaves when subjected to inputs. I don't actually see an easy (but slow) way of finding if a chip is static or non-static. If a non-static chip is classified as static incorrectly, that's an issue since the Truth Table doesn't match up with what the gate does.
Proposed in #396, additional inputs/outputs could be added to the truth table to represent the state of the chip. This however reduces the speed of processing the truth table, making the optimisation less optimal. It also suffers from the same issue as not doing any optimization in the first place for dynamic chips, where we cannot determine if a gate is stateless or not. In fact, it suffers from another related issue where we cannot determine how to represent the state - should it be a 1-bit input/output, 2-bit, 3-bit or more?
I guess the easiest way would be the ask the user whether their chip has a state, but they might not know what that means.
Duplicate of #396?
Nope, #396 suggests using truth tables for non-static gates in a slower way - I suggest not doing optimizations for them at all, bypassing 1 out of 2 issues with that method.
I think it's reasonable to only create LUTs for combinational chips. The sim already has a pass that detects this. Have to just be careful to also avoid chips containing elements such as keys, displays, buzzers etc. Also obviously have to switch to full sim if player views one of these chips so that wires and so on display correctly.
Perhaps an option to "bake" custom chips would work? I.E pressing the "bake" button from the context menu when right clicking the chip, generating a truth table for them and thus improving their performance, with the drawback of them not being viewable. Not sure.
I think it's reasonable to only create LUTs for combinational chips. The sim already has a pass that detects this. Have to just be careful to also avoid chips containing elements such as keys, displays, buzzers etc. Also obviously have to switch to full sim if player views one of these chips so that wires and so on display correctly.
Chips containing elements (like you said with keys, displays and buzzers) could just have the elements interpreted as inputs/outputs. A key would be an input and a display or buzzer would be an output. They just wouldn't be pin outputs, but rather interact with the simulation in other ways. (as they would without Truth Tables)
I think it's reasonable to only create LUTs for combinational chips. The sim already has a pass that detects this. Have to just be careful to also avoid chips containing elements such as keys, displays, buzzers etc. Also obviously have to switch to full sim if player views one of these chips so that wires and so on display correctly.
Chips containing elements (like you said with keys, displays and buzzers) could just have the elements interpreted as inputs/outputs. A key would be an input and a display or buzzer would be an output. They just wouldn't be pin outputs, but rather interact with the simulation in other ways. (as they would without Truth Tables)
Yeah, good point