search

YosysHQ / yosys

Yosys Open SYnthesis Suite
https://yosyshq.net/yosys/
ISC License
3.5k stars 895 forks source link

`write_verilog`: Fix `O(N^2)` port dumping to `O(N)` #4753

Closed akashlevy closed 4 days ago

akashlevy commented 5 days ago

What are the reasons/motivation for this change?

write_verilog is incredibly slow for modules with lots of ports. We have some modules with thousands of ports and write_verilog can take hours to run. Related to issue #3845 perhaps.

This is because port dumping is O(N^2) runtime, where N is the number of ports in the design. This poor runtime behavior arises due to the nested for loop (see lines 2337-2349); each loop can iterate up to the number of ports in the design.

Explain how this is achieved.

We reduce the runtime to O(N) by pre-building a port_id to wire vector, then using a single for loop.

If applicable, please suggest to reviewers how they can test the change.

Passes all tests.

povik commented 5 days ago

Fwiw the ports field on modules is holding the ordered port names too

akashlevy commented 5 days ago

Should we use that instead? Iterate through port names and get module->wire(port)?

zachjs commented 5 days ago

Should we use that instead? Iterate through port names and get module->wire(port)?

That sounds like a nice improvement!

akashlevy commented 5 days ago

I'm on it :)

zachjs commented 4 days ago

Patch looks good to me.

povik commented 4 days ago

Let’s wait for green CI and merge