Open
Description
Consider the program below which looks suspiciously similar to __compute_partial_sums
global ROOTS: [Field; 16] = [1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11, 12, 13, 14, 15, 16];
unconstrained fn main(
fracs: [Field; 16],
) -> pub [Field; 2] {
let mut partial_sums: [Field; 2] = std::mem::zeroed();
let mut partial_sum: Field = 0;
for i in 0..8 {
let summand = ROOTS[i] * fracs[i];
partial_sum = partial_sum + summand;
}
partial_sums[0] = partial_sum;
let NUM_PARTIAL_SUMS = 2;
for i in 1..NUM_PARTIAL_SUMS {
let mut partial_sum: Field = partial_sums[i - 1];
for j in 0..8 {
let k = i * 8 + j;
let summand = ROOTS[k]* fracs[k];
partial_sum = partial_sum + summand;
}
partial_sums[i] = partial_sum;
}
partial_sums
}This should be able to be compiled down to a stack of adds and muls but instead we get
g0 = Field 1
g1 = Field 2
g2 = Field 3
g3 = Field 4
g4 = Field 5
g5 = Field 6
g6 = Field 7
g7 = Field 8
g8 = Field 9
g9 = Field 10
g10 = Field 11
g11 = Field 12
g12 = Field 13
g13 = Field 14
g14 = Field 15
g15 = Field 16
g16 = make_array [Field 1, Field 2, Field 3, Field 4, Field 5, Field 6, Field 7, Field 8, Field 9, Field 10, Field 11, Field 12, Field 13, Field 14, Field 15, Field 16] : [Field; 16]
brillig(inline) fn main f0 {
b0(v17: [Field; 16]):
v21 = make_array [Field 0, Field 0] : [Field; 2]
v22 = allocate -> &mut [Field; 2]
store v21 at v22
v23 = allocate -> &mut Field
store Field 0 at v23
jmp b1(u32 0)
b1(v18: u32):
v26 = lt v18, u32 8
jmpif v26 then: b6, else: b2
b2():
v27 = load v22 -> [Field; 2]
v28 = load v23 -> Field
v29 = array_set v27, index u32 0, value v28
store v29 at v22
v30 = allocate -> &mut Field
store v28 at v30
jmp b3(u32 0)
b3(v19: u32):
v31 = lt v19, u32 8
jmpif v31 then: b5, else: b4
b4():
v32 = load v22 -> [Field; 2]
v33 = load v30 -> Field
v35 = array_set v32, index u32 1, value v33
store v35 at v22
return v35
b5():
v36 = add u32 8, v19
v37 = array_get g16, index v36 -> Field
v38 = array_get v17, index v36 -> Field
v39 = mul v37, v38
v40 = load v30 -> Field
v41 = add v40, v39
store v41 at v30
v42 = unchecked_add v19, u32 1
jmp b3(v42)
b6():
v43 = array_get g16, index v18 -> Field
v44 = array_get v17, index v18 -> Field
v45 = mul v43, v44
v46 = load v23 -> Field
v47 = add v46, v45
store v47 at v23
v48 = unchecked_add v18, u32 1
jmp b1(v48)
}
Compare this with the equivalent ACIR, it's marginally more instructions but much faster execution. (once we count the overhead of dealing with globals then it's probably more instructions anyway)
acir(inline) fn main f0 {
b0(v17: [Field; 16]):
v19 = array_get v17, index u32 0 -> Field
v21 = array_get v17, index u32 1 -> Field
v23 = mul Field 2, v21
v24 = add v19, v23
v26 = array_get v17, index u32 2 -> Field
v28 = mul Field 3, v26
v29 = add v24, v28
v31 = array_get v17, index u32 3 -> Field
v33 = mul Field 4, v31
v34 = add v29, v33
v36 = array_get v17, index u32 4 -> Field
v38 = mul Field 5, v36
v39 = add v34, v38
v41 = array_get v17, index u32 5 -> Field
v43 = mul Field 6, v41
v44 = add v39, v43
v46 = array_get v17, index u32 6 -> Field
v48 = mul Field 7, v46
v49 = add v44, v48
v51 = array_get v17, index u32 7 -> Field
v53 = mul Field 8, v51
v54 = add v49, v53
v56 = array_get v17, index u32 8 -> Field
v58 = mul Field 9, v56
v59 = add v54, v58
v61 = array_get v17, index u32 9 -> Field
v63 = mul Field 10, v61
v64 = add v59, v63
v66 = array_get v17, index u32 10 -> Field
v68 = mul Field 11, v66
v69 = add v64, v68
v71 = array_get v17, index u32 11 -> Field
v73 = mul Field 12, v71
v74 = add v69, v73
v76 = array_get v17, index u32 12 -> Field
v78 = mul Field 13, v76
v79 = add v74, v78
v81 = array_get v17, index u32 13 -> Field
v83 = mul Field 14, v81
v84 = add v79, v83
v86 = array_get v17, index u32 14 -> Field
v88 = mul Field 15, v86
v89 = add v84, v88
v91 = array_get v17, index u32 15 -> Field
v93 = mul Field 16, v91
v94 = add v89, v93
v95 = make_array [v54, v94] : [Field; 2]
return v95
}
Metadata
Metadata
Assignees
Labels
No labels
Type
Projects
Status
📋 Backlog
Activity