Yet another strike against the current AA implementation

[Georg Wrede]

Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> downs wrote:
>>> Joel C. Salomon wrote:
>>>> grauzone wrote:
>>>>> downs wrote:
>>>>>> Daniel Keep wrote:
>>>>>>> Here's an excellent reason to use ranges over opApply: you
>>>>>>> can't define zip with opApply.  Because opApply uses inversion of
>>>>>>> control, you can't use more than one without bringing threads 
>>>>>>> into the
>>>>>>> equation.
>>>>>> Your point stands, of course, but I just wanted to mention that
>>>>>> stackthreads/fibers work too and have far less overhead.
>>>>> First, don't they have LOTS of memory overhead, because each fiber 
>>>>> needs
>>>>> a new/separate stack?
>>>> A fiber-specific stack needn’t be very large. A few KB is often enough
>>>> even for long-running threads; if the call stack is only going to be a
>>>> few levels deep you might get away with a few hundred bytes each.
>>
>> The Commodore-64 had a stack of 0.25kB shared between your Basic 
>> program, subroutine calls, and the operating system. While not unheard 
>> of, it still was unusual to have to make amendments to program design 
>> because of stack limitations, even in large programs.
>>
>> *If* we had a convenient way to record the high-water mark of stack 
>> usage for functions (and maybe also threads), then people could have 
>> new insights on how little stack space is needed.
>>
>> This would be /very/ convenient once we start using thread specific 
>> stacks, because the stack space has to be allocated in advance, 
>> hopefully not wasting huge amounts of space "just in case".
>>
>> Andrei, Walter???
> 
> Since C64 programs have gotten a lot bigger, programming style favors 
> deeper call stacks, and (mutually) recursive functions are not a rarity.
> 
> 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.

If this shows the maximum stack usage as 160 bytes, then today's 
youngsters could allocate, say, 0.25k, (or even 1k) instead of the 50k 
they'd otherwise allocate.

Incidentally, this raises another thought: what if the stack was 
extendable? Like D arrays? A stack overflow would trigger a relocation 
of the stack, and then continue. Being able to have hundreds of small 
stacks would be useful in other things than threads, too.