3 ms·

Recursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able

by mannyv 3y ago

Recursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion. Recursion is a nice toy, but in real life it's a ticking time bomb.

josephg 3y ago
If you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree. If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8. This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.
munificent 3y ago
This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine.
- Joel_Mckay 3y ago
  "Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)
  - munificent 3y ago
    If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous. There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine. We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't. Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
    - Joel_Mckay 3y ago
      For many reasons, people often add nesting limits in recursive structures to at least constrain how bad they behave when something eventually does go wrong. Parsers are far from immune to these issues. I think we will have to "agree to disagree" here... =)
  - jcgrillo 3y ago
    For a fun time, make a nested json blob about 1000 layers deep[1] and in python: with open('lulz.json') as ayy_lmao: oops = json.load(ayy_lmao) If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill. EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it. EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting. [1] EDIT3: on my machine in ipython right now it's 1485: import json def nest(d): return '{"k":' + str(d) + '}' def make_mess(n): v = 1 for _ in range(n): v = nest(v) return v json.loads(make_mess(1485)) # boom
    - Joel_Mckay 3y ago
      In general, most json/bson parsers like libbson have a rather shallow depth restriction (xerces also constrains this if I recall.) And yeah, recursion is avoided in some shops for good reasons.
    - munificent 3y ago
      Parsing untrusted input on a machine where failure could affect someone other than the person who provided the input is definitely a known case to be mindful of. You'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory. If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)
      - Joel_Mckay 3y ago
        You mean like the reply depth limit in forums like YC. Shouldn't you stick to a depth-first branch reply limit until moving to the next fork. I want to respect your beliefs. =)
  - jameshart 3y ago
    There’s an easy way to figure out if recursion is fine for your usecase def isRecursionOk(problem) for (subProblem in (breakDownIntoSubProblems(problem)) if ! isRecursionOk(subProblem) return false return true
    - Joel_Mckay 3y ago
      "kernel: Out of memory: Kill process 9163 (Insulin-pump-task) score 511 or sacrifice child" There are safer hobbies available like snake juggling =)
    - hughdbrown 3y ago
      This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recursion is good for a use case unless the problem decomposes into infinite subproblems, but in that case this test function never returns false. Makes more sense to do it as breadth-first with only one return value: from collections import deque def isRecursionOk(problem): q = deque(problem) while q: problem = q.popleft() q.append(list(breakDownIntoSubProblems(problem))) return true
naasking 3y ago
> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.
- Joel_Mckay 3y ago
  From my perspective, the main issue it causes (besides flood risks) is an overlapping state dependency that can process-bind large areas of fragmented memory. So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context. Best of luck, =)
- jcgrillo 3y ago
  > This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken. - space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others. - time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker. > Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter. I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution. EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.

by mannyv 3y ago

josephg 3y ago

If you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree. If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8. This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.

munificent 3y ago

This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine.

Joel_Mckay 3y ago
"Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)
- munificent 3y ago
  If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous. There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine. We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't. Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
  - Joel_Mckay 3y ago
    For many reasons, people often add nesting limits in recursive structures to at least constrain how bad they behave when something eventually does go wrong. Parsers are far from immune to these issues. I think we will have to "agree to disagree" here... =)
- jcgrillo 3y ago
  For a fun time, make a nested json blob about 1000 layers deep[1] and in python: with open('lulz.json') as ayy_lmao: oops = json.load(ayy_lmao) If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill. EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it. EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting. [1] EDIT3: on my machine in ipython right now it's 1485: import json def nest(d): return '{"k":' + str(d) + '}' def make_mess(n): v = 1 for _ in range(n): v = nest(v) return v json.loads(make_mess(1485)) # boom
  - Joel_Mckay 3y ago
    In general, most json/bson parsers like libbson have a rather shallow depth restriction (xerces also constrains this if I recall.) And yeah, recursion is avoided in some shops for good reasons.
  - munificent 3y ago
    Parsing untrusted input on a machine where failure could affect someone other than the person who provided the input is definitely a known case to be mindful of. You'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory. If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)
    - Joel_Mckay 3y ago
      You mean like the reply depth limit in forums like YC. Shouldn't you stick to a depth-first branch reply limit until moving to the next fork. I want to respect your beliefs. =)
- jameshart 3y ago
  There’s an easy way to figure out if recursion is fine for your usecase def isRecursionOk(problem) for (subProblem in (breakDownIntoSubProblems(problem)) if ! isRecursionOk(subProblem) return false return true
  - Joel_Mckay 3y ago
    "kernel: Out of memory: Kill process 9163 (Insulin-pump-task) score 511 or sacrifice child" There are safer hobbies available like snake juggling =)
  - hughdbrown 3y ago
    This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recursion is good for a use case unless the problem decomposes into infinite subproblems, but in that case this test function never returns false. Makes more sense to do it as breadth-first with only one return value: from collections import deque def isRecursionOk(problem): q = deque(problem) while q: problem = q.popleft() q.append(list(breakDownIntoSubProblems(problem))) return true

naasking 3y ago

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to, just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.

Joel_Mckay 3y ago
From my perspective, the main issue it causes (besides flood risks) is an overlapping state dependency that can process-bind large areas of fragmented memory. So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context. Best of luck, =)
jcgrillo 3y ago
> This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken. - space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others. - time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker. > Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter. I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution. EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.