Conditional RAM writes scale nonlinearly in loops

[sirasistant]

Aim

Using conditional ram writes:

global SIZE = 500;

fn main(mut fields: [Field; SIZE], enables: [bool; SIZE], indices: [u64; SIZE]) -> pub [Field; SIZE] {
    for i in 0..SIZE {
        if enables[i] {
            fields[indices[i]] = i as Field;
        }
    }

    fields
}

Expected Behavior

I expected conditional RAM writes to scale in the same way with the number of iterations as the unconditional ones

global SIZE = 500;

fn main(mut fields: [Field; SIZE], indices: [u64; SIZE]) -> pub [Field; SIZE] {
    for i in 0..SIZE {
        fields[indices[i]] = i as Field;
    }

    fields
}

Bug

The first example scales nonlinearly: With size=30 it's 10k constraints (333 constraints/iteration) and with size=500 it's 1.65M constraints (3300 constraints/iteration)

The second example (unconditional) scales sublinearly (possibly because of fixed costs): with size=100 it's 4.6k constraints and with size=500 it's 12k constraints.

Also, it seems like even without the nonlinear scaling the conditional ram writes are quite expensive (10x the cost of a unconditional one in the best case)

To Reproduce

Project Impact

None

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

None

Nargo Version

No response

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[TomAFrench]

SSA for the expensive program with SIZE = 2

After Array Set Optimizations:
acir(inline) fn main f0 {
  b0(v0: [Field; 2], v1: [u1; 2]):
    v92 = array_get v1, index u64 0
    enable_side_effects v92
    v93 = array_get v0, index u64 0
    enable_side_effects u1 1
    v95 = cast v92 as Field
    v97 = mul v95, v93
    v98 = cast v92 as u64
    v100 = array_get v1, index u64 1
    enable_side_effects v100
    v101 = array_get v0, index u64 1
    v102 = lt v98, u64 2
    v103 = mul v102, v100
    constrain v103 == v100 'push out of bounds'
    v104 = array_set [v97, Field 0], index v98, value v101
    v105 = add v98, u64 1
    v106 = not v100
    enable_side_effects v100
    v107 = array_get v104, index v98
    v108 = array_get [v97, Field 0], index v98
    v109 = cast v100 as Field
    v110 = cast v106 as Field
    v111 = mul v109, v107
    v112 = mul v110, v108
    v113 = add v111, v112
    v114 = array_set mut v104, index v98, value v113
    enable_side_effects u1 1
    v115 = cast v100 as u64
    v116 = cast v106 as u64
    v117 = mul v115, v105
    v118 = mul v116, v98
    v119 = add v117, v118
    constrain v119 == u64 0
    return v114
}

One thing that jumps out is the check that we're not pushing past the capacity of the BoundedVec. We have enough information here that we should be able to rule that out at compile time.

[TomAFrench]

noir/noir_stdlib/src/collections/bounded_vec.nr

Line 24 in 9c6de4b

assert(self.len < MaxLen, "push out of bounds");

We should be able to just remove this assertion (or throw the error in an unconstrained block if we want to maintain the error message). The attempt to write past the end of the array would trigger the ACVM to fail.

[TomAFrench]

This ends up being just a small contribution (~4000) constraints.

[guipublic]

Did you really compare the number of constraints or just the number of acir opcodes?
Because 25 constraints for writing 500 times into an array of 500 elements does not seem right. I would expect ~2000 instead.

[sirasistant]

@guipublic

I was referring to 25 constraints/item, will update first message!

This function:

global SIZE = 500;

fn main(fields: [Field; SIZE], to_keep: [bool; SIZE]) -> pub [Field; SIZE] {
    let mut bounded_vec: BoundedVec<Field, SIZE> = BoundedVec::new();

    for i in 0..SIZE {
        if to_keep[i] {
            bounded_vec.push(fields[i]);
        }
    }

    assert_eq(bounded_vec.len(), 0);
    bounded_vec.storage
}

is 1.6M gates

This one:

global SIZE = 500;

fn main(mut fields: [Field; SIZE], indices: [u64; SIZE]) -> pub [Field; SIZE] {
    for i in 0..SIZE {
        fields[indices[i]] = i as Field;
    }

    fields
}

is 12k gates

[jfecher]

One thing that jumps out is the check that we're not pushing past the capacity of the BoundedVec. We have enough information here that we should be able to rule that out at compile time.

This looks like it'd be difficult to rule out at compile-time. We know that we only push at most once per loop and only loop SIZE times but the compiler just sees that each push is conditional on to_keep and can't keep an exact count. If we wanted to remove this condition we'd need much more meticulous tracking of maximum bounds, probably tracking each individual case of the value (e.g. len can be 0 or 1 here) then verifying all of those cases are < 2.

[sirasistant]

The length check is not the main contributor though, there seems to be some weird scaling with loop sizes going on. Constraint counts per iteration become much more similar if we decrease the number of iterations to 20. In that case, the version costs 320 constraints/write (a 10x reduction per iteration by scaling down the number of iterations)

[sirasistant]

To avoid any boundedvec related overhead, tried this code:

global SIZE = 500;

fn main(mut fields: [Field; SIZE], enables: [bool; SIZE], indices: [u64; SIZE]) -> pub [Field; SIZE] {
    for i in 0..SIZE {
        if enables[i] {
            fields[indices[i]] = i as Field;
        }
    }

    fields
}

And it also scales nonlinearly. With size=500 it's 1.65M constraints (3300 constraints/iteration) and with size=30 it's 10k constraints (333 constraints/iteration)

[sirasistant]

Updating the original issue

[jfecher]

And it also scales nonlinearly. With size=500 it's 1.65M constraints (3300 constraints/iteration) and with size=30 it's 10k constraints (333 constraints/iteration)

Sounds related to #4629 then.

Testing your most recent example in the comment I get:

SIZE | Acir Opcodes | Change
2    |     57       |
3    |     88       |   31
4    |     121      |   33
5    |     156      |   35

So it is increasing by 2 per each increase in SIZE.

[sirasistant]

Is there a way to use the as_witness intrinsic to fix this nonlinear scaling? or it's not fixable by that? Haven't looked much into the actual constraints being generated for predicated RAM writes yet