Georg Wrede wrote:
> Somebody more resourceful than I might /prove/ some maximum for any program that doesn't use recursion (be it implicit or explicit recursion). Hello.d attempted to be an example of such a program.

There's no need for a lot of expertise, it's a trivial fact for anyone who's written even a toy compiler. The tidbit that's difficult is the interprocedural part: in order to compute the stack consumed by any function, you need to know the stack consumed by all functions it invokes.

> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.

I think my failure is seeing what the idea is. My understanding is that you use one trace of a run to estimate the (average? minimum? maximum?) stack needed by future runs of a thread. It's unclear to me how that estimate would be used, what sort of information it provides (if any - I highly doubt it tells much), and generally how you'd integrate that into a compiler.


Andrei

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> Somebody more resourceful than I might /prove/ some maximum for any program that doesn't use recursion (be it implicit or explicit recursion). Hello.d attempted to be an example of such a program.
> 
> There's no need for a lot of expertise, it's a trivial fact for anyone who's written even a toy compiler. The tidbit that's difficult is the interprocedural part: in order to compute the stack consumed by any function, you need to know the stack consumed by all functions it invokes.
> 
>> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.
> 
> I think my failure is seeing what the idea is. My understanding is that you use one trace of a run to estimate the (average? minimum? maximum?) stack needed by future runs of a thread. It's unclear to me how that estimate would be used, what sort of information it provides (if any - I highly doubt it tells much), and generally how you'd integrate that into a compiler.

I think in the first instance it was at least to get an idea of how much stack space you're typically using. I must confess to having absolutely no idea of how much stack space my D apps are using. It'd be an interesting thing to know.

> 
> 
> Andrei

Andrei Alexandrescu wrote:
> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.

No way in hell is there a reliable way for a compiler to estimate stack depth. Heck, just a virtual function call blows it.

The stack, however, is checked. The virtual memory system puts a "guard" page following the end of the stack, so running off the end produces an exception. If there is unallocated space beyond that, the operating system will allocate more pages, then resume from the exception.

Georg Wrede wrote:
> Andrei Alexandrescu wrote:
>> Georg Wrede wrote:
>>> Andrei Alexandrescu wrote:
>>>> Georg Wrede wrote:
>>>>> Andrei Alexandrescu wrote:
>>>>>> Computing the stack depth even for non-recursive functions is an interprocedural analysis so it's difficult to do modularly. The stack is also unchecked so going with a "good enough" approximation is bound to be risky.
>>>>>
>>>>> The old size estimation problem. No matter how big you decide on, somewhere is an idiot who will blow that size too.
>>>>>
>>>>>
>>>>> A runtime solution just occurred to me. The newly allocated stack for a thread is zeroed first, right? Well then, just before the thread finishes, one could scan the stack area, and find the first address that contains a non-zero value.
>>>>>
>>>>> This isn't bullet proof in theory, but hey, the aim is to help in /estimating/ the needed stack size.
>>>>
>>>> You can't be more serious than Mark Twain when giving advice on the stock market: "Buy some stock. If it goes up, sell it. If it doesn't go up, don't buy it."
>>>
>>> I'd be amazed if the stack usage of hello.d varied from run to run.
>>
>> I'd be amazed if hello.d were your prototype of a useful program :o).
> 
> Somebody more resourceful than I might /prove/ some maximum for any program that doesn't use recursion (be it implicit or explicit recursion). Hello.d attempted to be an example of such a program.
> 
>> Let's face it. Any program that uses mutual recursion of any kind (even when the user did not set out to use recursion) or that uses alloca (fewer), is bound to have the consumed stack dependent on the input. 
> 
> Of course. And there's a limit to the stack size, ultimately at the hardware level. For any increase in available stack size, the probability of an out-of-stack exception decreases, never reaching zero. I agree.
> 
>> Even without recursion, various traces of a program depend on a data and have different stack depths. That's why your estimate is utterly useless.
> 
> It'd be useless if we were attempting to give 100.000% guarantees.
> 
>> I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it).

Having looked into things, it turns out I'm the one that now suspects you of jesting.

> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.

There is prior art, by the truckload. A /very/ short slide show here: http://zope.stackless.com/StacklessEuroPy.ppt

I'd kill to get that in D.

And about your comments on stack size, seems regular Python has an in-built limit on recursion, at 1000 deep. That should be diametrically opposite your stance on stack size.

Georg Wrede wrote:
>>> I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it).
> 
> Having looked into things, it turns out I'm the one that now suspects you of jesting.

What I referred to was inferring a thread's actual stack requirements from one trace of its run. That's just untenable.

>> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.
> 
> There is prior art, by the truckload. A /very/ short slide show here: http://zope.stackless.com/StacklessEuroPy.ppt
> 
> I'd kill to get that in D.

Interesting, just you can't claim you were talking about that all along. I mean, come on! You say one thing that was untenable, and now you come up with a different one that is. And you were right all along?

> And about your comments on stack size, seems regular Python has an in-built limit on recursion, at 1000 deep. That should be diametrically opposite your stance on stack size.

Python has apparently set a maximum to have a guarantee it won't crash when given a certain minimum stack size. That's nice, but I'm not quite seeing how that's opposite to what I said in this discussion.


Andrei

Georg Wrede:
> And about your comments on stack size, seems regular Python has an in-built limit on recursion, at 1000 deep. That should be diametrically opposite your stance on stack size.

See also sys.setrecursionlimit() to lift that limit where useful. You can also define how much deep to show the when an error occurs (to avoid flooding the shell, for example).

Python is a high-level language, so naturally people expect it to be fit for recursive algorithms, because they are sometimes shorter and more natural (when they work on nested data structures). But the low stack limit (and the very low performance of function calls) forces people to often manually translate recursive algorithms into iterative ones. I hate this.

Bye,
bearophile

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>>>> I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it).
>>
>> Having looked into things, it turns out I'm the one that now suspects you of jesting.

Could it be that you're looking at this too much through the eyes of a compiler developer? With souce code that can include templates, it should be no surprise that a programmer can write a file which results in preposterous stack needs. This is certainly the case with C++, for example.

> What I referred to was inferring a thread's actual stack requirements from one trace of its run. 

Of course you'd give different input data, a little like you give different input data to your unit tests.

> That's just untenable.

Agreed, IF there's a possibility of recursion happening, the variation in input data is not guaranteed, etc. But for practical purposes (read: most of my programs, and presumably those of the other programmers'), the situation is different.

For a particular application, we expect some explicit or implicit constarints on the input data. We also know (er, expect) whether (and to what extent) there will be recursion. Additionally (as with any real-life application), we accept that if the input data goes wild, the application /doesn't/ have to cope with it. (Making nuke proof apps where reasonably good is sufficient, is just gratuituous work.)

For example, a robust application, instead of accepting and coping with *anything*, instead has *documented limitations*. IMHO, that is the right way to "fix infinity problems". Not demanding limitless stack for all kinds of programs.

>>> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.
>>
>> There is prior art, by the truckload. A /very/ short slide show here: http://zope.stackless.com/StacklessEuroPy.ppt
>>
>> I'd kill to get that in D.
> 
> Interesting, just you can't claim you were talking about that all along. I mean, come on! You say one thing that was untenable, and now you come up with a different one that is. And you were right all along?

I was actually talking about *two* things. If you remember, I was talking about measuring actually used stack depth. Then I got the idea of having separate stacks for threads. Two separate things in a post.

(Now that I think more about it, I must have heard about stackless Python somewhere. But as I've seen others do, this time I, too, believed I invented something that I've actually seen somewhere.)

>> And about your comments on stack size, seems regular Python has an in-built limit on recursion, at 1000 deep. That should be diametrically opposite your stance on stack size.
> 
> Python has apparently set a maximum to have a guarantee it won't crash when given a certain minimum stack size. That's nice, but I'm not quite seeing how that's opposite to what I said in this discussion.

Nope. It's because

 - They don't want the entire computer thrashing each time some idiot has a typo in his recursive algorithm.

 - They genuinely don't think you usually need preposterous levels of recursion. And if you do, then just change the limit.

Python is for Real Computers (as opposed to Windows). There it's polite to make your apps (here, the Python interpreter) have some decency as to how much resources they take. The idea is that there are hundreds of other users, and dozens of daemons running critical apps, round the clock.

If developers didn't know (by measurement or analysis) the reasonable stack size needed, there would be no mobile phones, no set-top boxes with hard disks, no GPS receivers, no digital PBX appliances, no solid state firewalls, no ADSL boxes, no programmable calculators......

Dammit, any pocket calculator that has parenthesis buttons needs a stack. And that stack space is predermined by the manufacturer.

I'm still maintaining that the stack space needs of regular applications are much less than people tend to think. Last time I checked, you ran out of stack on a name brand calculator with just ten levels of parentheses. That's not much. On the other hand, in real life, not too many people in the world have ever seen a calculator run out of stack space.

bearophile wrote:
> Georg Wrede:
>> And about your comments on stack size, seems regular Python has an
>>  in-built limit on recursion, at 1000 deep. That should be
>> diametrically opposite your stance on stack size.
> 
> See also sys.setrecursionlimit() to lift that limit where useful. You
> can also define how much deep to show the when an error occurs (to
> avoid flooding the shell, for example).
> 
> Python is a high-level language, so naturally people expect it to be
> fit for recursive algorithms, because they are sometimes shorter and
> more natural (when they work on nested data structures). But the low
> stack limit (and the very low performance of function calls) forces
> people to often manually translate recursive algorithms into
> iterative ones. I hate this.

Python seems a nice language. It's a shame that it's a bit slow. Heh, that's good for D.

Georg Wrede wrote:
> Andrei Alexandrescu wrote:
>> Georg Wrede wrote:
>>>>> I can't believe you brought it up as anything else but jesting (maybe you are and I'm not getting it).
>>>
>>> Having looked into things, it turns out I'm the one that now suspects you of jesting.
> 
> Could it be that you're looking at this too much through the eyes of a compiler developer? With souce code that can include templates, it should be no surprise that a programmer can write a file which results in preposterous stack needs. This is certainly the case with C++, for example.

I am sorry, I need to fix a few mistakes in this post and then I'll have to leave this conversation as it becomes ungainful for us both.

The above is wrong, or at least contains a claim that you'd need to support better. Stack size requirements grow with the prevalence of short functions. Those are a style of programming not particularly correlated with templates. I don't have lots of small functions that call one another in templated code, any more than in regular code.

>> What I referred to was inferring a thread's actual stack requirements from one trace of its run. 
> 
> Of course you'd give different input data, a little like you give different input data to your unit tests.
> 
>> That's just untenable.
> 
> Agreed, IF there's a possibility of recursion happening, the variation in input data is not guaranteed, etc. But for practical purposes (read: most of my programs, and presumably those of the other programmers'), the situation is different.

This is utter nonsense. Practical vs. theoretical has absolutely nothing to do with this all. Forget recursion. I'm talking about straight "if"s that create different program traces that in turn require different stack sizes. Collecting one and saying it's fine "for practical purposes" is just nonsense. What's so complicated about this?

> For a particular application, we expect some explicit or implicit constarints on the input data. We also know (er, expect) whether (and to what extent) there will be recursion. Additionally (as with any real-life application), we accept that if the input data goes wild, the application /doesn't/ have to cope with it. (Making nuke proof apps where reasonably good is sufficient, is just gratuituous work.)

Again, just to drive the point home - recursion has nothing to do with. Your inferences are starting from a faulty premise.

> For example, a robust application, instead of accepting and coping with *anything*, instead has *documented limitations*. IMHO, that is the right way to "fix infinity problems". Not demanding limitless stack for all kinds of programs.
> 
>>>> Maybe I'll have to dig up prior art, or something. Clearly I'm not qualified to properly defend the validity of this idea.
>>>
>>> There is prior art, by the truckload. A /very/ short slide show here: http://zope.stackless.com/StacklessEuroPy.ppt
>>>
>>> I'd kill to get that in D.
>>
>> Interesting, just you can't claim you were talking about that all along. I mean, come on! You say one thing that was untenable, and now you come up with a different one that is. And you were right all along?
> 
> I was actually talking about *two* things. If you remember, I was talking about measuring actually used stack depth. Then I got the idea of having separate stacks for threads. Two separate things in a post.

Threads already have separate stacks. (You might have said more.)

> (Now that I think more about it, I must have heard about stackless Python somewhere. But as I've seen others do, this time I, too, believed I invented something that I've actually seen somewhere.)

Fortran was stackless for... for a long time :o). An activation record in Fotran is in static memory. To call a Fortran function, you deposit arguments in that static storage, issue the CALL, and wait.

>>> And about your comments on stack size, seems regular Python has an in-built limit on recursion, at 1000 deep. That should be diametrically opposite your stance on stack size.
>>
>> Python has apparently set a maximum to have a guarantee it won't crash when given a certain minimum stack size. That's nice, but I'm not quite seeing how that's opposite to what I said in this discussion.
> 
> Nope. It's because
> 
>  - They don't want the entire computer thrashing each time some idiot has a typo in his recursive algorithm.
> 
>  - They genuinely don't think you usually need preposterous levels of recursion. And if you do, then just change the limit.
> 
> Python is for Real Computers (as opposed to Windows). There it's polite to make your apps (here, the Python interpreter) have some decency as to how much resources they take. The idea is that there are hundreds of other users, and dozens of daemons running critical apps, round the clock.
> 
> If developers didn't know (by measurement or analysis) the reasonable stack size needed, there would be no mobile phones, no set-top boxes with hard disks, no GPS receivers, no digital PBX appliances, no solid state firewalls, no ADSL boxes, no programmable calculators......
> 
> Dammit, any pocket calculator that has parenthesis buttons needs a stack. And that stack space is predermined by the manufacturer.
> 
> I'm still maintaining that the stack space needs of regular applications are much less than people tend to think. Last time I checked, you ran out of stack on a name brand calculator with just ten levels of parentheses. That's not much. On the other hand, in real life, not too many people in the world have ever seen a calculator run out of stack space.

Sure, I'm not contending that. But that's a rather different claim than some others you made.


Andrei

Andrei Alexandrescu wrote:
> I am sorry, I need to fix a few mistakes in this post and then I'll have to leave this conversation as it becomes ungainful for us both.

Sigh.