search

mdbartos / pysheds

:earth_americas: Simple and fast watershed delineation in python.
GNU General Public License v3.0
706 stars 191 forks source link

Convert recursion into iteration, eliminating runtime errors in d8_catchment_search #144

Closed fnino closed 2 years ago

fnino commented 3 years ago

For big zones, recursion imposes an unnecessary burden on memory. The algorithm uses tail recursion, which on other languages is optimized automatically, converting it into a simple iteration. This is what I did here, because Guido von Rossum doesn't want to optimize tail recursion.

With the change, our big catchment executes with no error, faster and with less memory requirements.

mdbartos commented 3 years ago

Greetings,

Thanks for the contribution. I believe this issue has come up before, and I'm glad to see a fix proposed. I will review this is as soon as possible.

For future reference: I am currently in the process of reimplementing major DEM processing functions in numba (#143). This should take care of the recursion issue, and currently appears to be resulting in 10-100x speedups across the board.