Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Limiting function recursion depth

88 views
Skip to first unread message

Mr Flibble

unread,
Mar 24, 2019, 9:52:15 AM3/24/19
to
Hi!

I've just thought of another elegant use for thread_local: limiting
recursion depth of recursive functions to avoid a stack fault if recursion
is dynamic/user input dependent:

namespace neolib
{
template <typename Tag, std::size_t MaxDepth = Tag::RecursionLimit>
class recursion_limiter
{
public:
struct too_deep : std::runtime_error { too_deep() :
std::runtime_error(std::string{ "Maximum recursion depth for '" } +
typeid(Tag).name() + "' exceeded") {} };
public:
recursion_limiter()
{
if (++current_depth() > MaxDepth)
throw too_deep();
}
~recursion_limiter()
{
--current_depth();
}
private:
static std::size_t& current_depth()
{
thread_local std::size_t tDepth;
return tDepth;
}
};
}

#define _limit_recursion_(a) neolib::recursion_limiter<a>
_##a##_recursion_limiter_

Usage:

class ed209
{
public:
static constexpr std::size_t RecursionLimit = 64u;
public:
void target_armed()
{
_limit_recursion_(ed209);
target_armed();
}
};

The need for such a device is predicated on the assumption that throwing
an exception is more desirable than raising a stack fault (which is
undefined behaviour).

/Flibble

--
“You won’t burn in hell. But be nice anyway.” – Ricky Gervais

“I see Atheists are fighting and killing each other again, over who
doesn’t believe in any God the most. Oh, no..wait.. that never happens.” –
Ricky Gervais

"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."

Bonita Montero

unread,
Mar 24, 2019, 11:32:04 AM3/24/19
to
You're dealing with problems that not exist. Stack-overflows
almost never happen. The only case which might tigger a stack
overflow realistically is a massively misuse of alloca(). But
using alloca() is untypical for C++-programs.

Scott Lurndal

unread,
Mar 24, 2019, 12:25:19 PM3/24/19
to
Mr Flibble <flibbleREM...@i42.co.uk> writes:
>Hi!
>
>I've just thought of another elegant use for thread_local: limiting
>recursion depth of recursive functions to avoid a stack fault if recursion
>is dynamic/user input dependent:
>

>The need for such a device is predicated on the assumption that throwing
>an exception is more desirable than raising a stack fault (which is
>undefined behaviour).
>

Your code is not re-entrant, however. May be a limitation for some usage
(e.g. if the recursion invokes a leaf function via a function pointer or
std::function).

Mr Flibble

unread,
Mar 24, 2019, 12:44:12 PM3/24/19
to
Nonsense.

Mr Flibble

unread,
Mar 24, 2019, 12:44:47 PM3/24/19
to
Nonsense.

Bonita Montero

unread,
Mar 24, 2019, 12:45:18 PM3/24/19
to
> Your code is not re-entrant, ...

Why? thread_local is like static but for
each thread with an individual isntance.

Bonita Montero

unread,
Mar 24, 2019, 12:48:45 PM3/24/19
to
>> You're dealing with problems that not exist. Stack-overflows
>> almost never happen. The only case which might tigger a stack
>> overflow realistically is a massively misuse of alloca(). But
>> using alloca() is untypical for C++-programs.

> Nonsense.

No, not nonsense. No one cares about stack-overflows at least in
userspace. With Windows the default stacksize is one MB and with
Linux its 2MB. No one does recursions that eat so much stack-size.

Mr Flibble

unread,
Mar 24, 2019, 12:52:24 PM3/24/19
to
More nonsense.

Bonita Montero

unread,
Mar 24, 2019, 1:59:55 PM3/24/19
to
I've read much code and I never have seen someone dealing with
stack-overflows explicitly. Even in Java where you have a special
StackOverflowError, I've never seen code that catches such an
error (it's not an exception but an Error in Java).
The best thing here is that you can't calculate the amout of stack
that is allocated for a function in C++ in a way to estimate a maxi-
mum recursion-depth as the amount of stack for each function call
may vary depending on the compiler and the runtime-library. And
even if you could, setting the maximul recursion-depth to a
_compile-time_ tempalte-parameter would be silly.

Mr Flibble

unread,
Mar 24, 2019, 2:10:47 PM3/24/19
to
Yet more nonsense.

Bonita Montero

unread,
Mar 24, 2019, 2:12:38 PM3/24/19
to
>> I've read much code and I never have seen someone dealing with
>> stack-overflows explicitly. Even in Java where you have a special
>> StackOverflowError, I've never seen code that catches such an
>> error (it's not an exception but an Error in Java).
>> The best thing here is that you can't calculate the amout of stack
>> that is allocated for a function in C++ in a way to estimate a maxi-
>> mum recursion-depth as the amount of stack for each function call
>> may vary depending on the compiler and the runtime-library. And
>> even if you could, setting the maximul recursion-depth to a
>> _compile-time_ tempalte-parameter would be silly.

> Yet more nonsense.

Absolute no argumentation from you - impressing.

Mr Flibble

unread,
Mar 24, 2019, 2:15:41 PM3/24/19
to
And random assertions from you with no evidence to back them up.
Assertions made without evidence can be dismissed without evidence which
is what I have been doing.

David Brown

unread,
Mar 24, 2019, 5:02:16 PM3/24/19
to
I don't know if Mr Flibble was thinking of such systems, but stack
overflows are very much a real problem in small embedded systems. It is
not uncommon to have stacks of a couple of KB - sometimes they are far,
far smaller. And generally there is no hardware protection or detection
in the case of stack overflows.

I haven't looked much at the OP's code to see if it is suitable for such
systems.

Paavo Helde

unread,
Mar 24, 2019, 5:19:01 PM3/24/19
to
No one does such recursion because it does not work in C++. Stack
overflow is one of nastiest UB-s in C++. Instead, people take pains to
rewrite recursive algorithms via loops and dynamic data structures on heap.

In other news, nobody needs more than 640K of RAM.

Mr Flibble

unread,
Mar 24, 2019, 6:58:25 PM3/24/19
to
I assume you are joking based on what you write next because that is
simply bullshit.

>
> In other news, nobody needs more than 640K of RAM.

El Jo

unread,
Mar 24, 2019, 7:43:11 PM3/24/19
to
I disagree. I had experience of code that unfortunately was already in production
where a recursive bad parser of ASN.1 for a cryptokey crashed the stack since we were in embedded enviroment.


Paavo Helde

unread,
Mar 25, 2019, 3:07:57 AM3/25/19
to
On 25.03.2019 0:58, Mr Flibble wrote:
> On 24/03/2019 21:18, Paavo Helde wrote:
>> On 24.03.2019 18:48, Bonita Montero wrote:
>>>>> You're dealing with problems that not exist. Stack-overflows
>>>>> almost never happen. The only case which might tigger a stack
>>>>> overflow realistically is a massively misuse of alloca(). But
>>>>> using alloca() is untypical for C++-programs.
>>>
>>>> Nonsense.
>>>
>>> No, not nonsense. No one cares about stack-overflows at least in
>>> userspace. With Windows the default stacksize is one MB and with
>>> Linux its 2MB. No one does recursions that eat so much stack-size.
>>
>> No one does such recursion because it does not work in C++. Stack
>> overflow is one of nastiest UB-s in C++. Instead, people take pains to
>> rewrite recursive algorithms via loops and dynamic data structures on
>> heap.
>
> I assume you are joking based on what you write next because that is
> simply bullshit.

Probably you misunderstood me somehow. What I wanted to say is that
certainly there are some people who would like to use deep recursive
algorithms in C++. A million iteration loop is perfectly fine, so why
should a million deep recursion not be? Alas, currently they can't
because the stack size is pretty limited and there are no safeguards.
Even if the recursion depth can be artificially bounded like in your
solution, it would not be safe to go anywhere near the max stack size as
there are too many uncontrollable factors affecting the stack memory usage.

As you said yourself, sometimes aborting too deep recursion with an
exception is acceptable, sometimes it is not. If it is not, then I
cannot use a recursive solution at all, period. It just does not work. I
have to rewrite my solution as non-recursive, and there would be no
point to keep the recursive variant around. So that's why Bonita is not
seeing deep recursive functions using up all the stack.

If an exception is acceptable, then I could come closer to utilizing the
whole stack, but nowhere near 100% as this would be way too dangerous,
especially with a rigid compile-time constant like in your solution. To
play it safe in a library used in unknown environments I would not dare
to use over half of the default stack space. So again Bonita is not
seeing a recursive function using up all the stack.


Juha Nieminen

unread,
Mar 25, 2019, 4:30:18 AM3/25/19
to
Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> On 24/03/2019 15:31, Bonita Montero wrote:
>> You're dealing with problems that not exist. Stack-overflows
>> almost never happen. The only case which might tigger a stack
>> overflow realistically is a massively misuse of alloca(). But
>> using alloca() is untypical for C++-programs.
>
> Nonsense.

Do you have anything constructive to say?

How about you explain your objection and present some arguments?

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

leigh.v....@googlemail.com

unread,
Mar 25, 2019, 4:34:04 AM3/25/19
to
On Monday, March 25, 2019 at 8:30:18 AM UTC, Juha Nieminen wrote:
> Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> > On 24/03/2019 15:31, Bonita Montero wrote:
> >> You're dealing with problems that not exist. Stack-overflows
> >> almost never happen. The only case which might tigger a stack
> >> overflow realistically is a massively misuse of alloca(). But
> >> using alloca() is untypical for C++-programs.
> >
> > Nonsense.
>
> Do you have anything constructive to say?

As far as this reply is concerned whether or not I have anything constructive to say is irrelevant.

>
> How about you explain your objection and present some arguments?

How about I continue to dismiss without evidence assertions made without evidence?

/Leigh

fir

unread,
Mar 25, 2019, 4:38:59 AM3/25/19
to
the word nonesnse is not much proper here but its sorta untrue imo

if some is lazy he can for example use a quicksort in stack version - stack deepnes of quicksort on most pessimistic case is about N (where N are numbers of items to sort) (and each that item has at least 4 bytes i think usually probebly more)

it means that for example if someone uses this for sorting cells on a grid or something like that it would work in most cases (where this stac deepnes is lower) but will 'crash' on some rare of prepared cases

the way would be not to be so lazy and revrite if on non stck version..besides (for lazy ones) if someone wants to track a recursion depth he may use one ststic integer which he would ++ and --

fir

unread,
Mar 25, 2019, 4:55:49 AM3/25/19
to
what you say is sane but i thionk its not exactly logicaly 'strict' (tight? rigorous? - sorry or my weak english)

some points are,->
1) i think you may read the stack pointer in main at program enter and then compare to this value to gave sorta absolute stack usage counted (it may seen be as hack but sorta can be used)
2) in windows at least yu may set stack
size at compile time (you may probebly stet 50 MB if you want) (it probably can be set even after compiling by hackin the exe, as it is a fireld in exe header which says what stack this exe want to hae)
3) in windows i think they coud do far more save "resizable" stack, this is becouse after stack there is unmapped
page of ram and when you hit such page
afair system has some exception which he utylises yo map this ram (this 'exception' could be potentially used just to reallock up whole stack, it may be even copied in another place)

im not even sure if they dont do that
(last checked they didnt but i guess they do or should do at least something)

4) obviously sad that c dont gives stack information at will (at leas some gcc extensions should define some functions/intrinsics like

extern void* stack_top;
extern void* stack_bottom;
extern void* current_stack_pointer;







fir

unread,
Mar 25, 2019, 5:02:49 AM3/25/19
to
W dniu poniedziałek, 25 marca 2019 09:38:59 UTC+1 użytkownik fir napisał:
> W dniu niedziela, 24 marca 2019 19:12:38 UTC+1 użytkownik Bonita Montero napisał:
> > >> I've read much code and I never have seen someone dealing with
> > >> stack-overflows explicitly. Even in Java where you have a special
> > >> StackOverflowError, I've never seen code that catches such an
> > >> error (it's not an exception but an Error in Java).
> > >> The best thing here is that you can't calculate the amout of stack
> > >> that is allocated for a function in C++ in a way to estimate a maxi-
> > >> mum recursion-depth as the amount of stack for each function call
> > >> may vary depending on the compiler and the runtime-library. And
> > >> even if you could, setting the maximul recursion-depth to a
> > >> _compile-time_ tempalte-parameter would be silly.
> >
> > > Yet more nonsense.
> >
> > Absolute no argumentation from you - impressing.
>
> the word nonesnse is not much proper here but its sorta untrue imo
>
> if some is lazy he can for example use a quicksort in stack version - stack deepnes of quicksort on most pessimistic case is about N (where N are numbers of items to sort) (and each that item has at least 4 bytes i think usually probebly more)
>

in most optymistyic this deepnes is probably lg2(N) so for 1 milion it would be like only 20... in real cases it is somewhere between, this 20 and that prepared milion, (closer to 20 as to get that pessimistic case every entry should be prepared and chances probably drop fast...but afair there is a risk, and you may sort bigger sets of data and then risk will rise)

David Brown

unread,
Mar 25, 2019, 5:59:15 AM3/25/19
to
How about you give some brief examples or explanation about why you
think he is talking nonsense, and where you see your code being useful.
Then the discussion can progress above the pantomime level.

If you think your class is useful and stack overflow is a real problem,
you haven't given any evidence of that either.

(If you are just giving the class as an example of thread local data,
RAII, or CRTP, without claiming it is useful in itself, that's fine.)

Scott Lurndal

unread,
Mar 25, 2019, 9:48:45 AM3/25/19
to
I've been using thread-local data for almost three decades; Hell, I've
implemented thread-local data in operating systems. I'm pretty sure
I understand it quite well.

The function that Flibble posted won't work as documented if it is re-entered
from the same thread further down the call stack.

Öö Tiib

unread,
Mar 25, 2019, 10:58:53 AM3/25/19
to
What function you mean? To re-enter function from same thread down
the call stack the function has to be calling some other function(s).

Bonita Montero

unread,
Mar 25, 2019, 12:00:18 PM3/25/19
to
> The function that Flibble posted won't work as documented if it
> is re-entered from the same thread further down the call stack.

No, the idea is correct. The TLS-specific counter is incremented
with each call-level for each instantiation of a new recursion
_limiter and decremented on destruction / retuen.
The thing is simply, that almost no one cares for stack-overflows;
so his code is almost useless.

Rick C. Hodgin

unread,
Mar 25, 2019, 12:21:03 PM3/25/19
to
Bonita, don't forget: Leigh's writing a new master neo-lang right?

So, apparently he's running into this issue in his own neo-generated
code often enough that he saw the need to create a new neo-disaster
class to handle these kinds of infinite recursion issues. We'll
likely see extensions added as time goes by and more neo-disasters
are found.

J/k, Leigh. Where's your sense of humor?

--
Rick C. Hodgin

Bonita Montero

unread,
Mar 25, 2019, 12:49:51 PM3/25/19
to
> Bonita, don't forget: Leigh's writing a new master neo-lang right?

People even don't like having a lot of #defines and depending or
even nested #ifdefs in a single module. But in this case you can
see a necessity to do that. But there's no necessity to mix several
even interleaving code-pieces of different languages in a single
source-file. The idea is totally ridiculous.
And I hardly doubt that Mr.Fibble is able to write a parser for
this set of languages. Parsing C++ should be the hardest; that's
three heads to high for him. And he is simply not smart enough
to write a performant VM.

Rick C. Hodgin

unread,
Mar 25, 2019, 12:51:42 PM3/25/19
to
I disagree. I think he's got the skillz. I think we'll soon see
a brand of neo ravioli coming out (with special sauce).

--
Rick C. Hodgin

Bonita Montero

unread,
Mar 25, 2019, 12:53:05 PM3/25/19
to
> I disagree. I think he's got the skillz. I think we'll soon
> see a brand of neo ravioli coming out (with special sauce).

Yes, with an interleaving mix of strawberrys and mussels.

Rick C. Hodgin

unread,
Mar 25, 2019, 1:31:56 PM3/25/19
to
LOL! Quote possibly.

"Mussels. Mussels. .... Mussels."

--
Rick C. Hodgin

Mr Flibble

unread,
Mar 25, 2019, 2:05:41 PM3/25/19
to
Nonsense; the function is re-entrant; obviously those three decades have
paid off eh?

Mr Flibble

unread,
Mar 25, 2019, 2:06:31 PM3/25/19
to
Yet more baseless assertions summarily dismissed.

Mr Flibble

unread,
Mar 25, 2019, 2:06:47 PM3/25/19
to

Bonita Montero

unread,
Mar 25, 2019, 2:24:54 PM3/25/19
to
>> People even don't like having a lot of #defines and depending or
>> even nested #ifdefs in a single module. But in this case you can
>> see a necessity to do that. But there's no necessity to mix several
>> even interleaving code-pieces of different languages in a single
>> source-file. The idea is totally ridiculous.
>> And I hardly doubt that Mr.Fibble is able to write a parser for
>> this set of languages. Parsing C++ should be the hardest; that's
>> three heads to high for him. And he is simply not smart enough
>> to write a performant VM.

> Yet more baseless assertions summarily dismissed.

Yor work is as serious as your name.

Mr Flibble

unread,
Mar 25, 2019, 2:29:31 PM3/25/19
to
Learn to spell dear.

james...@alumni.caltech.edu

unread,
Mar 25, 2019, 3:20:24 PM3/25/19
to
On Monday, March 25, 2019 at 9:48:45 AM UTC-4, Scott Lurndal wrote:
...
> The function that Flibble posted won't work as documented if it is re-entered
> from the same thread further down the call stack.

That description sounds to me like it should be relatively easy to
create a simple example demonstrating the problem you're talking about.
Since there seems to be considerable confusion about this issue, perhaps
you could provide such an example?

David Brown

unread,
Mar 25, 2019, 3:26:24 PM3/25/19
to
On 25/03/2019 19:29, Mr Flibble wrote:
> On 25/03/2019 18:24, Bonita Montero wrote:
>>>> People even don't like having a lot of #defines and depending or
>>>> even nested #ifdefs in a single module. But in this case you can
>>>> see a necessity to do that. But there's no necessity to mix several
>>>> even interleaving code-pieces of different languages in a single
>>>> source-file. The idea is totally ridiculous.
>>>> And I hardly doubt that Mr.Fibble is able to write a parser for
>>>> this set of languages. Parsing C++ should be the hardest; that's
>>>> three heads to high for him. And he is simply not smart enough
>>>> to write a performant VM.
>>
>>> Yet more baseless assertions summarily dismissed.
>>
>> Yor work is as serious as your name.
>
> Learn to spell dear.
>
> /Flibble
>

<https://en.wikipedia.org/wiki/Muphry%27s_law>

(At the risk of invoking it myself, I note that you missed out the comma.)

Scott Lurndal

unread,
Mar 25, 2019, 3:51:08 PM3/25/19
to
Ah, not having used the C++11 threading facilities, I wrongly concluded
that thread_local, like static, would use the same storage for multiple
objects defined with the same name. I see that is incorrect.

Mea culpa; I generally use POSIX interfaces (pthread_key_create/pthread_setspecific).

Mr Flibble

unread,
Mar 25, 2019, 4:24:02 PM3/25/19
to
"three decades" of experience!.

Bonita Montero

unread,
Mar 25, 2019, 4:30:29 PM3/25/19
to
>>>> The function that Flibble posted won't work as documented if it is
>>>> re-entered
>>>> from the same thread further down the call stack.

>>> That description sounds to me like it should be relatively easy to
>>> create a simple example demonstrating the problem you're talking about.
>>> Since there seems to be considerable confusion about this issue, perhaps
>>> you could provide such an example?

>> Ah, not having used the C++11 threading facilities, I wrongly concluded
>> that thread_local, like static, would use the same storage for multiple
>> objects defined with the same name.   I see that is incorrect.
>> Mea culpa; I generally use POSIX interfaces
>> (pthread_key_create/pthread_setspecific).

> "three decades" of experience!.

Keep calm!
You have a massive overestimation of your capabilities yourself.

Alf P. Steinbach

unread,
Mar 25, 2019, 8:12:39 PM3/25/19
to
<shelrock hat>Lols. As far as I can see the "guitly" party is located in
Melbourne, Australia, so it isn't you unless you used a proxy, e.g. Tor
network. However, I don't see how you could become aware of that in such
a short time frame unless you were somehow involved or with knowledge of
the edit.</shelrock hat>

In Norwegian:

Watson, stikk ut og se hva det er hunden fra Basker vil.


Cheers!,

- Alf

David Brown

unread,
Mar 26, 2019, 4:17:34 AM3/26/19
to
On 25/03/2019 21:23, Mr Flibble wrote:
> On 25/03/2019 19:50, Scott Lurndal wrote:
>> james...@alumni.caltech.edu writes:
>>> On Monday, March 25, 2019 at 9:48:45 AM UTC-4, Scott Lurndal wrote:
>>> ...
>>>> The function that Flibble posted won't work as documented if it is
>>>> re-entered
>>>> from the same thread further down the call stack.
>>>
>>> That description sounds to me like it should be relatively easy to
>>> create a simple example demonstrating the problem you're talking about.
>>> Since there seems to be considerable confusion about this issue, perhaps
>>> you could provide such an example?
>>
>> Ah, not having used the C++11 threading facilities, I wrongly concluded
>> that thread_local, like static, would use the same storage for multiple
>> objects defined with the same name.   I see that is incorrect.
>>
>> Mea culpa; I generally use POSIX interfaces
>> (pthread_key_create/pthread_setspecific).
>
> "three decades" of experience!.
>
> /Flibble
>

He made a little mistake - as we all do from time to time. He realised
it, admitted it, learned from it, and moves on. That shows the maturity
of someone with three decades of experience. I'm not sure what /your/
response is showing, but "maturity" is not the word that springs to mind.

0 new messages