Ticket #225 (closed defect: fixed)

Opened 4 years ago

Last modified 4 years ago

[with patch, needs review] recursion stack overflow in control flow analysis

Reported by: scoder Owned by: scoder
Priority: major Milestone: 0.12
Component: Optimization Keywords:
Cc:

Description

Here is an example for a program that Cython currently cannot compile as the control flow analysis reaches the maximum recursion limit. The problem appears to be the long sequence of simple "if" statements.

Attachments

Sieves.py Download (85.9 KB) - added by scoder 4 years ago.
iterative-controlflow-traversal.patch Download (6.0 KB) - added by scoder 4 years ago.
use a loop instead of recursion
Sieves.2.py Download (97.2 KB) - added by scoder 4 years ago.
Cythonized version of Sieves.py (uses C ints and basically runs in no-time)

Change History

Changed 4 years ago by scoder

Changed 4 years ago by scoder

As a 'quick' fix, it might work to materialise the control flow state at branching/merge points. That would speed up the lookups and prevent deep recursion.

Changed 4 years ago by scoder

  • owner changed from somebody to robertwb
  • summary changed from recursion stack overflow in control flow analysis to [with patch, needs review] recursion stack overflow in control flow analysis
  • milestone changed from wishlist to 0.12

Here is a patch that reimplements the control flow traversal with a loop instead of recursion. I can't easily check if I broke anything (which I likely did), so I don't push it directly. Robert, do you have a way to check if this still works as expected?

Changed 4 years ago by scoder

use a loop instead of recursion

Changed 4 years ago by scoder

Cythonized version of Sieves.py (uses C ints and basically runs in no-time)

Changed 4 years ago by robertwb

  • status changed from new to closed
  • resolution set to fixed

Looks fine to me, though I can't think of how to add a good automated test. I see you've pushed.

Changed 4 years ago by scoder

  • status changed from closed to reopened
  • resolution fixed deleted

Changed 4 years ago by scoder

  • owner changed from robertwb to scoder
  • status changed from reopened to new

Changed 4 years ago by scoder

  • status changed from new to closed
  • resolution set to fixed
Note: See TracTickets for help on using tickets.