[GitHub] [arrow-datafusion] alamb edited a comment on pull request #1437: Fix: stack overflow

[GitBox <gi...@apache.org>]

alamb edited a comment on pull request #1437:
URL: https://github.com/apache/arrow-datafusion/pull/1437#issuecomment-992770032


   > > This is an acceptable short term workaround, but I think it would be more efficient and more elegant if we rewrite these recursive procedures into iterative procedures.
   
   > Do you mean to use push-based model？
   
   
   @xudong963 , I think what @houqp  is suggesting is to rewrite code that is recursive to not be recursive.
   
   The pattern for Datafusion probably looks like taking code like
   
   ```rust
   fn visit(expr: &expr)  {
     for child in expr.children() {
       visit(child)
     }
     // do actual expr logic
   }
   ```
   
   And changing it so the state is tracked with a structure on the heap rather than a stack. I think [`VecDeque`](https://doc.rust-lang.org/stable/std/collections/struct.VecDeque.html) is a good one for rust:
   
   ```rust
   fn visit(expr: &expr)  {
     let mut worklist = VecDequeue::new();
     worklist.push_back(expr);
     while !worklist.is_empty() {
       let parent = worklist.pop_front();
       for child in parent.children() {
         worklist.push_back(child)
       }
       // do actual expr logic on parent
     }
   }
   ```
   
   (aka avoid the call back to `visit`)


-- 
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