8 ms·

The lack of stack size is one of my continual irritations. It makes it difficult to write tree-searches in the obvious recursive way, because there is a good ch

• likeabbas 5y ago
  Could also be solved if the compiler supported Tail calls optimization
  • dnautics 5y ago
    I don't think tail call will help depth-first ("obvious recursive way") tree algos.
    • aidenn0 5y ago
      It doesn't help with breadth-first searches either. A non-degenerate tree of depth N will use O(N) space, and that space will be on the call-stack if you use a recursive algorithm to access it. As long as you use less than 1 page per activation record though, most modern libc implementations behave safely under unbounded recursion as they will allocate a guard-page around each stack. [edit] It would also be useful if the compiler could warn about activation records larger than 1 page. Absent alloca (and deprecated c99 VLAs), that should be statically knowable.
      • Dylan16807 5y ago
        What does a recursive breadth-first search look like? I think you'd have to contort yourself to write that, which is why people are specifically mentioning depth-first where recursion is easy and natural.
        • aidenn0 5y ago
          Ah you're right; the most natural BFS would be tail-recursive or iterative.
      • dnautics 5y ago
        A BFS is essentially a while loop with a queue datastructure. This is (relatively) easy to implement in TCO-recursive erlang/elixir, which is what I'm currently most proficient in. And, yeah, TCO would help.
  • cryptonector 5y ago
    TCO is an optimization. It's not always possible.
    • jhgb 5y ago
      It's a misnomer. It's not just "an optimization"; in some cases, it alters program semantics.
      • cryptonector 5y ago
        Usually the only visible side-effect of TCO is stack trace compression and failure to exhaust the stack. You can call that semantics if you like, but I think most people wouldn't. It's absurd that Java doesn't do TCO because of the stack compression "issue" (as I understand, that's why Java doesn't TCO).
        • jhgb 5y ago
          Termination instead of divergence definitely is a change in semantics.
          • cryptonector 5y ago
            No, failure to fail is not a change in semantics. EDIT: "My program used to fail with a stack size exhaustion error, but now it works -- I'm so angry about this!" -no one ever.
            • jhgb 5y ago
              But they'd complain about the opposite -- for example if the program were an external-event-driven state automaton.
              • cryptonector 5y ago
                TCO does not do the opposite. TCO helps avoid stack exhaustion without introducing new faults. TCO might cause your program to avoid one stack exhaustion fault only to reveal a different fault (possibly a different stack exhaustion fault). This is not a semantics change. And it's not a bug either.
  • Jensson 5y ago
    The main reason to use recursion is to use the stack variables, when tail call optimization is possible people usually just prefers loops.
• ploxiln 5y ago
  The initial/main thread stack size is dynamic, it grows until it runs into another allocation (and these days there are guard pages and such). You can already use 128MB on the initial/main stack, even with musl-libc / Alpine linux (it needs to be linearly probed it if it's unreasonably huge, so the OS isn't surprised by a random memory access out in the middle of nowhere, but the compiler should do that automatically these days). You can also request whatever stack size you need for additional threads when you create them, this has always been a good idea. It's only the default stack size for non-main threads, if you don't specify it, which may be considered reasonably limited.
  • masklinn 5y ago
    > The initial/main thread stack size is dynamic That seems doubtful, AFAIK all OS have a static allocation for the main thread, just one that is commonly (though not necessarily) much larger than what they give off-threads, as https://ariadne.space/2021/06/25/understanding-thread-stack-sizes-and-how-alpine-is-different/ https://ariadne.space/2021/06/25/understanding-thread-stack-... quotes Windows gives 1MB to all threads, while macOS or OpenBSD 4.6+ give 8MB to the main thread and 512k to off-threads. The former would not merit consideration if it was automatically increased. > it grows until it runs into another allocation Which it won't because vmem. > and these days there are guard pages and such That just makes the access segfault if the stack allocation is not large enough to straight jump over the guard page.
    • ploxiln 5y ago
      I'm not so familiar with other operating systems, but on Linux and presumably other unixes, the only thing holding back the initial/main "process stack" is ulimit. Try "ulimit -s unlimited". (On macOS that increases it from 8MB to 64MB, but on linux it seems to really go unlimited)
• phkahler 5y ago
  A good tree will have something like log(n) depth so normal recursion should be fine. Apart from recursive algorithms, stack size can be determined by static analysis. Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree?
  • dllthomas 5y ago
    > A good tree will have something like log(n) depth so normal recursion should be fine. But in many contexts you have to be robust against a bad tree. > Apart from recursive algorithms, stack size can be determined by static analysis. Not always, in the presence of dynamically sized arrays (or alloca and friends).
  • xfer 5y ago
    https://llvm.org/docs/Passes.html#dot-callgraph-print-call-graph-to-dot-file https://llvm.org/docs/Passes.html#dot-callgraph-print-call-g...
  • AnimalMuppet 5y ago
    Yeah. You won't be able to fit the tree in memory long before you overflow the stack while recursing down the tree.
  • stncls 5y ago
    > A good tree will have something like log(n) depth so normal recursion should be fine. Yes, this is true for comparison/search/sort/bucketing algorithms. But in other applications (e.g. graph theory, networks, sparse matrices) a depth of n, for n elements, can be perfectly legitimate. Or it can even be an edge case, but one you don't want to handle by just segfaulting. > Which reminds me: what is a good tool for analyzing / viewing a C++ programs call tree? Linux perf can collect the necessary data. Then for frontends, I am not sure. KDAB's "hotspot" ( https://www.kdab.com/tag/perf/ https://www.kdab.com/tag/perf/ ) can do flamegraphs, but this may be more performance-oriented than what you're looking for. Edit: perf can collect the data statistically. It will miss many calls, the ones that are the least time-consuming.
  • wallstprog 5y ago
• kevincox 5y ago
  > would it really cost that much (as until the memory was touched it wouldn't really be allocated). The problem here is that once it is used once it is never freed. (Other than being swapped out). So you effectively cache all of the space your program needs forever. There are some solutions like trying to mark the stack below you freeable but it is hard to do this in a way that doesn't cause huge performance concerns if you happen to be crossing whatever boundary is picked often. IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop.
  • owl57 5y ago
    > IIRC Golang used to do this but switched to copying, growable stacks because no matter how hard they tried they always ended up in scenarios where they were allocating and deallocating stacks in a hot loop. They used to do segmented stacks. The bad overhead is not in allocation, but in switching between segments when stack pointer is oscillating around the boundary — but if you want to allocate really many stacks that could grow large, you don't have much choice: either this or tracking pointers that need to be updated on reallocation. Normal contiguously mapped stack, but with dynamic growing and shrinking of actually mapped pages, is an entirely different proposition.
    • Dylan16807 5y ago
      Ah, that makes more sense, since you could easily limit stack deallocation to once a second or whatever.
    • kragen 5y ago
      In an implementation of a language that can't take the address of a local variable, you can move some stack frames to the new segment when you switch segments, 256 bytes or so. Then, to oscillate around the boundary, you need to return enough times to deallocate those 256 bytes. This will cost enough to swamp the cost of switching segments. (If you can take the address of a local variable, but you have garbage collection and can handle memory allocation failures by exiting, you can heap-allocate whatever local variables have their address taken.) Segmented stacks are a particularly efficient way to implement call/cc.
• ximeng 5y ago
  Zig appears to have a proposed solution to this similar to your option 1, move recursion to the heap. https://github.com/ziglang/zig/issues/1639 https://github.com/ziglang/zig/issues/1639 They're also looking at static analysis of the maximum stack depth which might help in some cases.
  • ziml77 5y ago
    Being able to make recursive functions use the heap would be great. I assume it would need to be opt-in since you'll change performance characteristics, but I almost always rearrange recursive algorithms to use a loop and a heap allocated stack structure instead. There's no reason the compiler couldn't help do that for me.
  • pcwalton 5y ago
    I'm highly skeptical that static analysis of maximum stack depth will work, because of higher-order functions.
    • klyrs 5y ago
      In rust, unsafe operations can be marked such to silence the compiler when you know better; one could imagine something similar for a stack depth analyzer in zig. Or, for example, zig could use a finite stack depth when it can prove that's feasible, and emit code that will spill to the heap for cases it can't.
• foobiekr 5y ago
  Honestly, there is almost no difference between a purely recursive implementation on the stack and one that uses a passed-in stack structure (whether extensible or fixed) in terms of complexity. Though I can see why it would be nice if the languages supported some sugar for this.
• LegionMammal978 5y ago
  I recall that the Rust compiler uses the stacker crate [0] to grow the stack into the heap, and it's under the rust-lang organization on GitHub, so it's probably the closest you can get to an "in-language option" without it actually being in the standard library. However, it currently isn't supported for several platforms due to the lack of a suitable OS interface. [0] https://docs.rs/stacker/0.1.14/stacker/ https://docs.rs/stacker/0.1.14/stacker/
• bjourne 5y ago
  Any recursive tree traversal function is incorrect. You need to write the function in an iterative fashion. Hoping that a recursive function won't run out of stack space is like allocating 500 characters to an input field and hoping that the user never will enter longer inputs. Consider a degenerate tree consisting of a linked list of N nodes. If N is large (100m perhaps) you will inevitably run out of stack.
  • nineteen999 5y ago
    As much as I love recursive algorithms, I couldn't agree with you more. Why do the clever and pretty thing, when it is better to do the less elegant but reliable thing.
    • omegalulw 5y ago
      +1, though in general designing an iterative solution is more effort for problems that have intuitive recursive solution so OPs argument has some merit.
  • atq2119 5y ago
    I agree where there isn't inherently a stack. Many of the introductory examples of recursion are trivially transformed to an iteration in constant space. However, there are plenty of interesting cases where if you don't use recursion, you end up having to implement your own stack as a resizable vector. The question "why should the busy work of hand-rolling your own stack be necessary?" is the kind of question that you don't want to waste too much time on as a working programmer, but unless some people think deeply about such questions, the field as a whole stops progressing. As others point out in this discussion, with a 64-bit address space one could organize the stack(s) in such a way that recursion could use all of physical memory if necessary.
    • deleted 5y ago
      [deleted]
• Const-me 5y ago
  > but feels like reimplementing for no reason In C++, std::vector::emplace_back() and pop_back() are in the standard library for a decade now.
  • TillE 5y ago
    Well that's a stack, but it's not a call stack, which is the point.
• m463 5y ago
  it's even worse in the kernel. I think it's 16kb yes, kilobytes.
• rini17 5y ago
  I did try to enlarge the default stack size on Linux and ran into problem that it caused maximum number of threads to decrease. Because each thread has its own stack so it's (virtual memory limit)/(stack size) iirc and if you set stack size to 1G you'll get very low threads limit.