Aim

Create a sparse array with a larger number of KV pairs in comptime

Expected Behavior

sparse_array::SparseArray::create will work with a large N value in comptime

Bug

Will throw

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

To Reproduce

global ELEMENT_COUNT: u32 = 45; // this one works
// global ELEMENT_COUNT: u32 = 46;  // this will throw with...
// thread '<unknown>' has overflowed its stack
// fatal runtime error: stack overflow
// Aborted (core dumped)

global table: sparse_array::SparseArray<ELEMENT_COUNT, Field> = make_sparse_array();

comptime fn make_sparse_array() -> sparse_array::SparseArray<ELEMENT_COUNT, Field> {
    let mut indices: [Field; ELEMENT_COUNT] = [0; ELEMENT_COUNT];
    let mut values: [Field; ELEMENT_COUNT] = [0; ELEMENT_COUNT];
    for i in 0..ELEMENT_COUNT {
        indices[i] = (i) as Field;
        values[i] = (i * 2) as Field;
    }
    sparse_array::SparseArray::create(indices, values, (ELEMENT_COUNT * 2) as Field)
}

fn main(x: Field) {
    // just something to compile
    let y = table.get(x);
    assert(y == 0);
}

#[test]
fn test_main() {
    main(1);
}

run nargo compile with this library as a dependency in Nargo.toml

Workaround

None

Workaround Description

It works totally fine* at run time, but A: is still doing witcalc which takes a while and B: adds constraints for the user

Alternatively exploring building the SparseArray outside of Noir autogen

Finally could potentially recompile nargo with large RUST_MIN_STACK to get this done - however if this works it would still be prohibitive for 99% of developers

Additional Context

Appears that sparse_array::SparseArray::create -> sort_advanced -> quicksort_explicit is the culprit, with many

Project Impact

Blocker

Blocker Context

Blocks efficient use of zk-regex

Nargo Version

No response

NoirJS Version

1.0.0-beta.1+03b58fa2dfcc8acc8cf5198b1b23b55676fbdb02

Proving Backend Tooling & Version

0.66.0

Would you like to submit a PR for this Issue?

None

Support Needs

No response