ACIR gen extremely slow for eddsa

[joss-aztec]

Aim

Compile time should be comparable to old SSA solution.

Expected Behavior

^

Bug

Compiling the example eddsa with --experimental-ssa takes approximately 13 minutes on my 2.3 GHz 8-Core Intel Core i9 MacBook Pro. By contrast the old implementation only takes 1 minute to compile. The time is spent predominantly in ACIR gen.

To Reproduce

Installation Method

None

Nargo Version

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[joss-aztec]

I'm timing this again and it's taking a lot longer than 13 minutes this run... already passed 30mins

[joss-aztec]

Over an hour has passed - killing it.

[jfecher]

The eddsa test is now hanging during calling find_branch_ends in the flattening pass.

Edit: sha256_byte is also hanging on find_branch_ends

[jfecher]

Because acir-gen iterates instruction by instruction it is fairly easy to get a progress bar of how far and how fast it is going. My initial impressions are:

1. It is much too slow for larger programs, of course as identified by this issue, and
2. It seems to get slower with each additional instruction pushed. At instruction 6000/67000 it was taking ~3.5-4s to process 100 instructions. At instruction 20000 / 67000 it was taking closer to 7s. Even if we assume 7s managed to be the average speed, estimated completion time for 67k instructions is over 78 minutes.
3. It is not memory bound. At the 20k instruction point mentioned earlier, it was still only using 2% of my computer's memory.

[kevaundray]

Re-opening this issue as eddsa takes a long time still cc @Ethan-000 for visibility

[Ethan-000]

not sure what the ideal speed should be this is the result

benchmarked with code https://github.com/Ethan-000/noir/tree/b_eddsa

[Ethan-000]

another run