comptime intepretter fails with stack-too-deep error from recursing when quicksorting a not-excessively large array #7213
Comments
|
Not addressed by zkemail/zk-regex#75 (comment) btw |
|
Hey, this isn't an issue with the library but with noir's comptime interpreter. I've then moved this issue across to the main noir repository. |
|
This can be replicated with the programs global ELEMENT_COUNT: u32 = 100;
comptime fn main() {
let values: [u32; ELEMENT_COUNT] = [0; ELEMENT_COUNT];
let _ = quicksort(values);
}
comptime fn partition<let N: u32>(
arr: &mut [u32; N],
low: u32,
high: u32,
) -> u32 {
let pivot = high;
let mut i = low;
for j in low..high {
if arr[j] < arr[pivot] {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i += 1;
}
}
let temp = arr[i];
arr[i] = arr[pivot];
arr[pivot] = temp;
i
}
comptime fn quicksort_recursive<let N: u32>(
arr: &mut [u32; N],
low: u32,
high: u32,
) {
if low < high {
let pivot_index = partition(arr, low, high);
if pivot_index > 0 {
quicksort_recursive(arr, low, pivot_index - 1);
}
quicksort_recursive(arr, pivot_index + 1, high);
}
}
comptime fn quicksort<let N: u32>(
_arr: [u32; N],
) -> [u32; N] {
let mut arr: [u32; N] = _arr;
if N > 1 {
quicksort_recursive(&mut arr, 0, N - 1);
}
arr
}
or more minimally global RECURSION_LIMIT: u32 = 33;
comptime fn main() {
recurse(RECURSION_LIMIT);
}
comptime fn recurse(n: u32) {
if n > 0 {
recurse(n-1);
}
}
|
TomAFrench
changed the title
|
@jfecher can you assign someone to look into this? |
|
Reworking the interpreter in general to not stack overflow for a large* amount of recursive calls will be difficult I think. In general it requires queuing calls using a trampoline or similar. Since the interpreter would also need to preserve control-flow in the middle of a function it'd mean making it async. Since the interpreter also uses the elaborator... the entire noir frontend would need to be async. For now we can maybe rework quicksort to use loops instead of recursion. * "large" is obviously imprecise and I'd hope that ~46 recursive calls or however many were used wouldn't be considered such but the point stands that unless we're being very inefficient with stack memory in ways that are easily fixable, saving some memory here and there probably won't get us to 1000+ recursive calls. |
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
Nvalue in comptimeBug
Will throw
To Reproduce
run
nargo compilewith this library as a dependency in Nargo.tomlWorkaround
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
The text was updated successfully, but these errors were encountered: