7 ms·

There is no useful way to employ these functions. It's equivalent to asking if a mutex is locked. That piece of information is worthless.

by vasama 5y ago

notact 5y ago
If writing a recursive algorithm on arbitrary input, check remaining stack size upon recursive function entry. If space is depleted, allocate a new fiber (aka a brand new clean stack), switch to it, and resume. Switch back to calling fiber on stack unwind.
- 10000truths 5y ago
  If you’re writing a recursive algorithm on arbitrary input, you should be using a stack container to store your state, not the call stack.
  - sydthrowaway 5y ago
    you mean std::stack?
  - notact 5y ago
    Why do you think so? A stack container ordinarily contains a single data type. You can jump through some hoops to let it store completely arbitrary types, but when you consider a function's stack frame as a distinct type, the call stack naturally does that for you.
    - kragen 5y ago
      Most commonly you handle this with a stack of records.
    - 10000truths 5y ago
      1. A stack frame usually takes up far more memory than the state that actually needs to be persisted, due to local variables and padding from alignment requirements. With a stack container, you can specify exactly what gets stored, and save on your memory footprint. 2. There are very few knobs you can tweak to control how your call stack space is allocated or represented in memory. With a stack container, you have much finer control over that - you can do reallocations or define custom error handling when you overflow the container, you can deallocate/shrink the container when you no longer need the space, you can serialize the container to disk to make your processing resumable, etc. 3. A call stack has a very limited set of operations. You can only access data from the current stack frame, and you can only push/pop (call/return) stack frames. But with your own stack-like data structure, you could extend it to do far more, e.g. accessing data from the first or last n traversals, or insert/remove multiple elements at once.
Y_Y 5y ago
Could you explain this please?
- vasama 5y ago
  Just like with the mutex, this piece of information is out of date as soon as it reaches you. Preparations for whatever action you perform after, or the very act of retrieving this information may invalidate it.
adrianN 5y ago
"I can't complete this recursive algorithm because I ran out of stack at this particular step" is a much nicer error message than "segmentation fault". For that it would be useful if you could check remaining stack space before recursing.
- vasama 5y ago
  Whatever values these functions returned, there would be no way for you to make a determination on whether another step can be performed.
sumtechguy 5y ago
I could see that sort of thing being very useful for a debugger.
- kragen 5y ago
  Debuggers don't need to restrict themselves to what the C standard provides, and never do.
OskarS 5y ago
What are you talking about? For lots of functions, it is perfectly possible to statically determine a maximum stack size (not all functions obviously, that would be the halting problem). An trivial example would be a function that calls no other functions, but you can imagine others: functions with static call trees (i.e. no function pointers), don’t use VLAs or alloca, and that are not recursive (mutually, indirectly, or otherwise) will have a static limit on possible stack usage. If you’ve formally verified that function X uses at most Y pages of stack, and the remaining stack is smaller than that, you could return an OUT_OF_STACK error instead of calling it. Most libraries/functions wouldn’t need this, but there are C libraries which place an extraordinary importance on reliability, and it seems like it would be a useful feature for them. There might be other reasons why these functions shouldn’t be in the standard (or are impossible on some platforms), but ”the information is worthless” is not one of them. Of course this information can be useful.
- vasama 5y ago
  The information is indeed worthless unless the standard were to also define such things as the stack layout and a closed set of operations which are allowed to consume more stack, such as defining a VLA, or calling a function.
kragen 5y ago
https://news.ycombinator.com/item?id=28683773 https://news.ycombinator.com/item?id=28683773 gives a useful way to employ them; Chicken Scheme has to run a minor garbage collection and longjmp to its trampoline before the stack runs out, but because there's no way to find out what the stack size limit is at runtime, you have to configure a stack size limit when you compile it. The CPython interpreter could also use them usefully; in order to ensure that recursive loops in Python programs raise a Python exception instead of segfaulting, it defaults to a limit of only 1000 levels of Python recursion, because some platforms it ran on were segfaulting at 2000. If it could query the stack size limit, it could instead raise an exception when it's getting close to the real limit instead of guessing. They wouldn't be like access(). There are more hacks in Heaven and Earth, Horatio, than are dreamed of in your philosophy.
- vasama 5y ago
  I believe we were discussing a potential addition to the C standard. It would however be useless unless the standard also defined such things as stack layout and a closed set of operations which may consume more stack space, such as calling a function.
  - kragen 5y ago
    It's true that this potential addition to the C standard would not permit things like CPython or Chicken to depend only on the C standard, it's true, but then every C program already depends on things other than the C standard—such as the example given in TFA, that any C implementation is entitled to abort any C program because it ran out of stack. Moreover, every nontrivial C program in practice contains UB. Nevertheless, it does matter what is and isn't standardized; standardizing such functions would greatly improve the situation for programs like those I mention, because they would be able to rely on the C standard to find out when they're about to run out of stack, an event they already have code for handling. It's true that a pathological C library implementation could still totally break their stack-exhaustion-handling code, and in fact that's already true, but fortunately there are lots of C library implementations that behave well enough in practice.

There is no useful way to employ these functions. It's equivalent to asking if a mutex is locked. That piece of information is worthless.

by vasama 5y ago

There is no useful way to employ these functions. It's equivalent to asking if a mutex is locked. That piece of information is worthless.

notact 5y ago

If writing a recursive algorithm on arbitrary input, check remaining stack size upon recursive function entry. If space is depleted, allocate a new fiber (aka a brand new clean stack), switch to it, and resume. Switch back to calling fiber on stack unwind.

10000truths 5y ago
If you’re writing a recursive algorithm on arbitrary input, you should be using a stack container to store your state, not the call stack.
- sydthrowaway 5y ago
  you mean std::stack?
- notact 5y ago
  Why do you think so? A stack container ordinarily contains a single data type. You can jump through some hoops to let it store completely arbitrary types, but when you consider a function's stack frame as a distinct type, the call stack naturally does that for you.
  - kragen 5y ago
    Most commonly you handle this with a stack of records.
  - 10000truths 5y ago
    1. A stack frame usually takes up far more memory than the state that actually needs to be persisted, due to local variables and padding from alignment requirements. With a stack container, you can specify exactly what gets stored, and save on your memory footprint. 2. There are very few knobs you can tweak to control how your call stack space is allocated or represented in memory. With a stack container, you have much finer control over that - you can do reallocations or define custom error handling when you overflow the container, you can deallocate/shrink the container when you no longer need the space, you can serialize the container to disk to make your processing resumable, etc. 3. A call stack has a very limited set of operations. You can only access data from the current stack frame, and you can only push/pop (call/return) stack frames. But with your own stack-like data structure, you could extend it to do far more, e.g. accessing data from the first or last n traversals, or insert/remove multiple elements at once.

Y_Y 5y ago

Could you explain this please?

vasama 5y ago
Just like with the mutex, this piece of information is out of date as soon as it reaches you. Preparations for whatever action you perform after, or the very act of retrieving this information may invalidate it.

adrianN 5y ago

"I can't complete this recursive algorithm because I ran out of stack at this particular step" is a much nicer error message than "segmentation fault". For that it would be useful if you could check remaining stack space before recursing.

vasama 5y ago
Whatever values these functions returned, there would be no way for you to make a determination on whether another step can be performed.

sumtechguy 5y ago

I could see that sort of thing being very useful for a debugger.

kragen 5y ago
Debuggers don't need to restrict themselves to what the C standard provides, and never do.

OskarS 5y ago

What are you talking about? For lots of functions, it is perfectly possible to statically determine a maximum stack size (not all functions obviously, that would be the halting problem). An trivial example would be a function that calls no other functions, but you can imagine others: functions with static call trees (i.e. no function pointers), don’t use VLAs or alloca, and that are not recursive (mutually, indirectly, or otherwise) will have a static limit on possible stack usage. If you’ve formally verified that function X uses at most Y pages of stack, and the remaining stack is smaller than that, you could return an OUT_OF_STACK error instead of calling it. Most libraries/functions wouldn’t need this, but there are C libraries which place an extraordinary importance on reliability, and it seems like it would be a useful feature for them. There might be other reasons why these functions shouldn’t be in the standard (or are impossible on some platforms), but ”the information is worthless” is not one of them. Of course this information can be useful.

vasama 5y ago
The information is indeed worthless unless the standard were to also define such things as the stack layout and a closed set of operations which are allowed to consume more stack, such as defining a VLA, or calling a function.

kragen 5y ago

https://news.ycombinator.com/item?id=28683773 https://news.ycombinator.com/item?id=28683773 gives a useful way to employ them; Chicken Scheme has to run a minor garbage collection and longjmp to its trampoline before the stack runs out, but because there's no way to find out what the stack size limit is at runtime, you have to configure a stack size limit when you compile it. The CPython interpreter could also use them usefully; in order to ensure that recursive loops in Python programs raise a Python exception instead of segfaulting, it defaults to a limit of only 1000 levels of Python recursion, because some platforms it ran on were segfaulting at 2000. If it could query the stack size limit, it could instead raise an exception when it's getting close to the real limit instead of guessing. They wouldn't be like access(). There are more hacks in Heaven and Earth, Horatio, than are dreamed of in your philosophy.

vasama 5y ago
I believe we were discussing a potential addition to the C standard. It would however be useless unless the standard also defined such things as stack layout and a closed set of operations which may consume more stack space, such as calling a function.
- kragen 5y ago
  It's true that this potential addition to the C standard would not permit things like CPython or Chicken to depend only on the C standard, it's true, but then every C program already depends on things other than the C standard—such as the example given in TFA, that any C implementation is entitled to abort any C program because it ran out of stack. Moreover, every nontrivial C program in practice contains UB. Nevertheless, it does matter what is and isn't standardized; standardizing such functions would greatly improve the situation for programs like those I mention, because they would be able to rely on the C standard to find out when they're about to run out of stack, an event they already have code for handling. It's true that a pathological C library implementation could still totally break their stack-exhaustion-handling code, and in fact that's already true, but fortunately there are lots of C library implementations that behave well enough in practice.