You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The current algorithm is queue based, which worked great when loops weren't a thing. As execution has grown more complex, it went from worst case n², to in complex case n². What I mean by this, is that any complex chip with loops (a CPU with registers / memory for example), is going to execute pretty slow.
The really nice things about the current algorithm is that it always executes in the right order, detects infinite loops, and only executes relevant nodes.
An alternative algorithm could be a stack based one. I've made some sketches and tests, and it seems it'd be worst case n, with a slightly higher constant. I couldn't get it to only execute relevant nodes however, so it is a tradeoff instead of a direct improvement.
It would be great if this could be a drop in replacement - not changing any behaviour, just execution times - but there's a chance it won't be. The "last" gates might change behaviour, and depending on how it chooses which nodes are executed when, some gates that change output when given the same input (increment gate as an example) will change behaviour.
The text was updated successfully, but these errors were encountered:
The current algorithm is queue based, which worked great when loops weren't a thing. As execution has grown more complex, it went from worst case n², to in complex case n². What I mean by this, is that any complex chip with loops (a CPU with registers / memory for example), is going to execute pretty slow.
The really nice things about the current algorithm is that it always executes in the right order, detects infinite loops, and only executes relevant nodes.
An alternative algorithm could be a stack based one. I've made some sketches and tests, and it seems it'd be worst case n, with a slightly higher constant. I couldn't get it to only execute relevant nodes however, so it is a tradeoff instead of a direct improvement.
It would be great if this could be a drop in replacement - not changing any behaviour, just execution times - but there's a chance it won't be. The "last" gates might change behaviour, and depending on how it chooses which nodes are executed when, some gates that change output when given the same input (increment gate as an example) will change behaviour.
The text was updated successfully, but these errors were encountered: