expr: Refactor AST evaluation to avoid stack overflow #7388
Conversation
|
GNU testsuite comparison: |
|
Windows isn't happy :) |
The algorithm is just wrong sorry, I wanted to avoid adding an id on the nodes but it doesn't work. I'll push fixes and update the PR description. |
5a1751b to
2b35b5b
Compare
|
GNU testsuite comparison: |
1 similar comment
|
GNU testsuite comparison: |
|
I did some quick benchmarking by simulating the long input here are the results: export N=10000
echo $(seq -s" + " $N)1 > tmp.txt
hyperfine -n expr "expr $(cat tmp.txt)" -n main_uu_expr "./main_uu_expr $(cat tmp.txt)" -n new_uu_expr "./new_uu_expr $(cat tmp.txt)" -N --warmup 300 -i
And with the input that the current implementation on the main branch can't handle: export N=30000
echo $(seq -s" + " $N)1 > tmp.txt
hyperfine -n expr "expr $(cat tmp.txt)" -n main_uu_expr "./main_uu_expr $(cat tmp.txt)" -n new_uu_expr "./new_uu_expr $(cat tmp.txt)" -N --warmup 300 -i
Tested on a MacBook Air M1 16Go macos 14.5 |
|
GNU testsuite comparison: |
|
What does the " (ignoring error)" mean in your second table ? |
It's relate to the The command runs but the exit code is a failure because of the stack overflow. |
|
It sounds strange to me, because when I tried, the segfault happened instantly, not after 10 seconds 🤔 |
Yes the benchmarks are in milliseconds. For the case when there is no stack overflow, it looks like my implementation is on par with the current one. I can do more benchmarks with different inputs if you want, but it's a bit hard to have a good benchmarks. When you go under the 1ms it's not reliable. |
src/uu/expr/src/syntax_tree.rs
Outdated
| @@ -5,6 +5,11 @@ | |||
|
|
|||
| // spell-checker:ignore (ToDO) ints paren prec multibytes | |||
|
|
|||
| use std::{ | |||
| collections::BTreeMap, | |||
| sync::atomic::{AtomicU16, Ordering}, | |||
There was a problem hiding this comment.
Is there a specific reason for using atomics here ?
I'm not very familiar with it, I thought it was only useful in threaded environments.
There was a problem hiding this comment.
There is no way for the compiler to assert that the function fn get_next_id() -> u16 isn't used by another thread. The simplest solution is to use an atomic value.
Another solution would be to use a thread local variable but it would be a bit more verbose. With thread locals every thread has a unique counter and it would break the code if the parser becomes multi-threaded.
There was a problem hiding this comment.
if the parser becomes multi-threaded
I don't think this is likely to happen.
After all, this is "just" a simple CLI arithmetic expression evaluator.
Making it multi-threaded seems a bit overkill to me, like if you really need that level of performance, use a dedicated tool, rather than a command from the coreutils.
In the single-threaded case, using an atomic add is just gonna make the process a tiny bit slower for no real reason.
There was a problem hiding this comment.
Yes make sense, I moved the implementation to use thread locals.
Duh, didn't see it 😭 Anyway, this Pr is about fixing a SEGFAULT, not improving the performance, so it's OK if you manage to keep the same performance without immproving it. |
There was a problem hiding this comment.
Nothing to say on the logic part.
I'd rather remove the use of atomics though, as the tool is not likely to get multi-threading support.
Apart from that, I think you could stash your commits in only 2 (changes to the code, and to the test), so we keep the main branch clean from implementation details.
Good job !
Test a stack overflow that was happening on linux for long inputs.
|
Fix a stack overflow happening on long inputs
|
GNU testsuite comparison: |
|
GNU testsuite comparison: |
1 similar comment
|
GNU testsuite comparison: |
Overview
This pull request addresses a stack overflow issue in the
exprutility when handling deeply nested expressions.Fixes #7338
Changes
Testing
The implementation includes a new test case that verifies the ability to handle large expressions that would previously cause stack overflow.
Notes
A simpler solution would be to use the decurse crate.