Symptom
When trying to simulate certain circuits, Amaranth spins at 100% CPU for a long time (hours+) before making any progress (if at all), though the circuit is of modest size (order of 100s of nodes) and might be expected to complete very rapidly.
How to reproduce
This gist has a circuit, and corresponding testbench, that reproduce the issue.
Running the code as-is will take a very long time to complete. Reducing the size of the circuit (by, say, changing the number of digits in line 54) means the circuit works and the simulator runs quickly.
Root cause
When preparing for simulation, Amaranth walks various tree structures that describe the circuit to be simulated. The tree-walking is done in a simple recursive fashion that doesn't take into account that nodes may appear more than once - if a node appears twice, it is walked twice. This is ordinarily not a problem (the operations are idempotent), but in certain pathological cases it can lead to exponential time behaviour, because every path through the graph will be explored, and this can be exponential in the number of nodes.
In particular, if the graph resembles a ladder graph, it is possible to walk the graph from the bottom rung to the top by taking either the left or right path from the first rung to the second, and the left or right path from the second rung to the third, and so on - so if there are 2*N nodes, there will be roughly 2^N possible paths.
Workarounds
@whitequark says:
be aware that the expected method of entering such designs here is to use intermediate comb assignments
The above gist also has a very hacky diff (against git+https://github.com/amaranth-lang/amaranth.git@870b6e3734d156c6f99c3df0f60ec8c4038e8717) that teaches Amaranth to keep track of which nodes it has visited, so that the exponential behaviour is avoided. With the diff, the circuit in the same gist simulates fine (and very quickly). It is not known whether the diff causes any adverse effects (it has not been thoroughly reviewed or tested).
Symptom
When trying to simulate certain circuits, Amaranth spins at 100% CPU for a long time (hours+) before making any progress (if at all), though the circuit is of modest size (order of 100s of nodes) and might be expected to complete very rapidly.
How to reproduce
This gist has a circuit, and corresponding testbench, that reproduce the issue.
Running the code as-is will take a very long time to complete. Reducing the size of the circuit (by, say, changing the number of digits in line 54) means the circuit works and the simulator runs quickly.
Root cause
When preparing for simulation, Amaranth walks various tree structures that describe the circuit to be simulated. The tree-walking is done in a simple recursive fashion that doesn't take into account that nodes may appear more than once - if a node appears twice, it is walked twice. This is ordinarily not a problem (the operations are idempotent), but in certain pathological cases it can lead to exponential time behaviour, because every path through the graph will be explored, and this can be exponential in the number of nodes.
In particular, if the graph resembles a ladder graph, it is possible to walk the graph from the bottom rung to the top by taking either the left or right path from the first rung to the second, and the left or right path from the second rung to the third, and so on - so if there are 2*N nodes, there will be roughly 2^N possible paths.
Workarounds
@whitequark says:
The above gist also has a very hacky diff (against
git+https://github.com/amaranth-lang/amaranth.git@870b6e3734d156c6f99c3df0f60ec8c4038e8717) that teaches Amaranth to keep track of which nodes it has visited, so that the exponential behaviour is avoided. With the diff, the circuit in the same gist simulates fine (and very quickly). It is not known whether the diff causes any adverse effects (it has not been thoroughly reviewed or tested).