You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/09/24 14:44:52 UTC
[GitHub] [arrow-datafusion] alamb opened a new pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
alamb opened a new pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047
# Which issue does this PR close?
Closes https://github.com/apache/arrow-datafusion/issues/419
# Rationale for this change
Prior to this PR, trying to evaluate `BinaryExprs` more than a few level deep (e.g. something like `a + a + a + a + a + a + a + a ...`) would result in a stack overflow
For example the test included fails like this with `tree_depth` of 10 (in debug builds)
```
thread 'physical_plan::expressions::binary::tests::relatively_deeply_nested' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass '-p datafusion --lib'
Caused by:
process didn't exit successfully: `/Users/alamb/Software/arrow-datafusion/target/debug/deps/datafusion-68280be86fef135e deeply` (signal: 6, SIGABRT: process abort signal)
```
# What changes are included in this PR?
1. Break the `BinaryExpr::evaluate` into a few smaller functions
2. Remove special case workaround added for #910
# Are there any user-facing changes?
Not really other than avoiding stack overflows while evaluating queries in debug builds
# Technical Backstory
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] houqp commented on pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
houqp commented on pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#issuecomment-927191961
This kind of "match to many arms with macros" pattern is very common in our code base. It seems like in the future if we want to get fancy, we could automate detection of problems like this in our code base. For example, having a linter tool automatically find out all recursive functions and check their stack size to see if it has passed a certain threshold.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
alamb commented on pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#issuecomment-927281881
> This kind of "match to many arms with macros" pattern is very common in our code base. It seems like in the future if we want to get fancy, we could automate detection of such problem in our code base. For example, having a linter tool automatically find out all recursive functions and check their stack size to see if it has passed a certain threshold.
I agree -- if we run into this problem again, investing in an automated tool like that sounds like a good idea.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] NGA-TRAN commented on a change in pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
NGA-TRAN commented on a change in pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#discussion_r715700618
##########
File path: datafusion/src/physical_plan/expressions/binary.rs
##########
@@ -1381,4 +1416,37 @@ mod tests {
))
}
}
+
+ #[test]
+ fn relatively_deeply_nested() {
+ // Reproducer for https://github.com/apache/arrow-datafusion/issues/419
+
+ // where even relatively shallow binary expressions overflowed
+ // the stack in debug builds
+
+ let input: Vec<_> = vec![1, 2, 3, 4, 5].into_iter().map(Some).collect();
+ let a: Int32Array = input.iter().collect();
+
+ let batch = RecordBatch::try_from_iter(vec![("a", Arc::new(a) as _)]).unwrap();
+ let schema = batch.schema();
+
+ // build a left deep tree ((((a + a) + a) + a ....
+ let tree_depth: i32 = 100;
Review comment:
🎉
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
alamb commented on pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#issuecomment-926826502
I'll plan to merge this tomorrow unless there are objections
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] houqp merged pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
houqp merged pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] houqp edited a comment on pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
houqp edited a comment on pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#issuecomment-927191961
This kind of "match to many arms with macros" pattern is very common in our code base. It seems like in the future if we want to get fancy, we could automate detection of such problem in our code base. For example, having a linter tool automatically find out all recursive functions and check their stack size to see if it has passed a certain threshold.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on a change in pull request #1047: Avoid stack overflow by reducing stack usage of `BinaryExpr::evaluate` in debug builds
Posted by GitBox <gi...@apache.org>.
alamb commented on a change in pull request #1047:
URL: https://github.com/apache/arrow-datafusion/pull/1047#discussion_r715677104
##########
File path: datafusion/src/physical_plan/expressions/binary.rs
##########
@@ -1381,4 +1416,37 @@ mod tests {
))
}
}
+
+ #[test]
+ fn relatively_deeply_nested() {
+ // Reproducer for https://github.com/apache/arrow-datafusion/issues/419
+
+ // where even relatively shallow binary expressions overflowed
+ // the stack in debug builds
+
+ let input: Vec<_> = vec![1, 2, 3, 4, 5].into_iter().map(Some).collect();
+ let a: Int32Array = input.iter().collect();
+
+ let batch = RecordBatch::try_from_iter(vec![("a", Arc::new(a) as _)]).unwrap();
+ let schema = batch.schema();
+
+ // build a left deep tree ((((a + a) + a) + a ....
+ let tree_depth: i32 = 100;
Review comment:
On master, this test causes a stack overflow with `tree_depth` of `10`. After the changes in this PR it passes successfully with a tree_depth of 100 (I didn't try any bigger)
##########
File path: datafusion/src/physical_plan/expressions/binary.rs
##########
@@ -543,86 +543,17 @@ impl PhysicalExpr for BinaryExpr {
)));
}
+ // Attempt to use special kernels if one input is scalar and the other is an array
Review comment:
There are no intended changes to this function's behavior, simply breaking it up into several smaller functions
##########
File path: .github/workflows/rust.yml
##########
@@ -105,8 +105,6 @@ jobs:
run: |
export ARROW_TEST_DATA=$(pwd)/testing/data
export PARQUET_TEST_DATA=$(pwd)/parquet-testing/data
- # run tests on all workspace members with default feature list + avro
Review comment:
This is the workaround added in #910
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org