Open vezenovm opened 3 weeks ago
We could possibly perform this lowering in ssa-gen as well whenever we see a nested array type, translating it into a larger unnested array. I think the main difficulty would be when users do access and pass around the sub-arrays. We'd probably have to iterate through each index at that point to make a new array. Then if they later set the sub-array we'd have to iterate and set each index as well. I don't expect that to be a common case though.
We could possibly perform this lowering in ssa-gen as well whenever we see a nested array type, translating it into a larger unnested array.
Yeah I was thinking to do this during ssa gen in the manner you laid out.
I think the main difficulty would be when users do access and pass around the sub-arrays. We'd probably have to iterate through each index at that point to make a new array. Then if they later set the sub-array we'd have to iterate and set each index as well. I don't expect that to be a common case though.
I agree I think this case will most likely just require making a new array for the sub array.
Problem
Our nested arrays have a recursive structure. When working with dynamic indices, this can lead to a lot of extra array operations that would otherwise be unnecessary if we had a flat memory representing the nested array.
Happy Case
Goal: Treat nested arrays as a single flat memory. We want to trade off extra array get/set operations for extra calculations to compute the index into the nested memory.
For example:
Here we do not need the first array get. We should be able to determine the following for the second array get and the other follow-ups.
In this case the extra computation needed to compute the index might not benefit us as much as getting rid of the first array get. But when it comes to writing into a nested array the benefits can be much greater.
Take this code:
This is the SSA for the if block:
There is a lot of fetching and setting that is unnecessary. Looking at
v43
we can see that it is actually set back into the equivalent index in the nested array. We should be able to have a singlearray_set
inside ofb2
with some extra arithmetic operations on the dynamic index.Workaround
Yes
Workaround Description
Flatten the memory manually. This is a pretty infeasible workaround to put on developers though and we should do this flattening in the compiler.
Here is the example above manually flattened:
This
main
is 229 Brillig opcodes vs. 383 Brillig opcodes in the original code snippet.Here is the SSA of the flat main:
There are a lot more array get operations for fetching from the dynamic main inputs, however,
b2
has been greatly simplified and we removed lots of unnecessary array sets (which are a lot more expensive than array gets). Technically ifv0
was also treated as a flat list of memory we could also just have 7 array gets rather than 9 array gets as we would not need to do the unnecessary fetching ofv6
andv8
.Additional Context
Additional updates such as treating the block param as an array constant rather than a single value ID would also allow us to get rid of all the array gets that precede the store into
v2
. This change is slightly different than flattening the memory itself and can be done in follow-up work.Project Impact
Nice-to-have
Blocker Context
This does not truly block anything, but would be a very good optimization to have.
Would you like to submit a PR for this Issue?
None
Support Needs
No response