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.
