PROGRAMMING TODAY new approach in C strict
runtime allows us to improve reccurency: call queue

Well acknowledged, astonished and reverded (random words
which meanning i dont know) professor fir from comp.lang.c
presented now aproach to strict recureency: call queue

In this article we will brifly show how it works and
slightli discuss some advantage of this new approach

Consider classic reccurency example, co called "flood fill"

recolorize_pixel_chain(int x, int y)
{ if(map[y][x]==color_to_replace)
{
map[y][x]=replacement_color);

recolorize_pixel_chain(x+1, y);
recolorize_pixel_chain(x-1, y);
recolorize_pixel_chain(x, y+1);
recolorize_pixel_chain(x, y-1);
}
}

this is kinda astonishingly simple solution hovever
there are few somewhat serios disadvantages of it making it less practically
usable..

I.
one problem is that the depth of recursion which such
code may achieve is quite high - and for example flod fill of
HD images which are 2 mega pixels big or more could need a stack
of range of few tens of megabytes (wchich for present pc having at least
4-8 GB ram are nothig shocking but still)

II.
the second problem is efficiency: passing a myriads of
ret values on call stack is most probably suboptimall
where iterative version of this code could avoid passing
retvalues only stuffing argumens in some array which maay
spare unnecessary bandwidth (details would need to be investigated
though)

III.
other problems may be found like ofr example the order in which
this algorithm choses pixels is somewhat 'unnatural'

IV.
yet other problem may be that this code could be hard to
be optimised for compiler, though theoretically it could be
optimised

the disadvantage of iterative method is hovever also present
its harder to write, less eradable and longer

Here comes the solution profesor fir proposed, it is called
"call queue" (by analogt to "call stack")

the idea is to mark some function calls to be placed on call
queueinstead of call stack, say for example you use keyword
queue tod enote that

recolorize_pixel_chain(int x, int y)
{ if(map[y][x]==color_to_replace)
{
map[y][x]=replacement_color);

queue recolorize_pixel_chain(x+1, y);
queue recolorize_pixel_chain(x-1, y);
queue recolorize_pixel_chain(x, y+1);
queue recolorize_pixel_chain(x, y-1);
}
}

the idea is then compiler met the queue keyword it
not generates call to function but stores the pointer to it and
the arguments into separate runtime 'list' (it is internal array)
and then continues execution of the parent function

here above the function will execute and during its execution it will
store 4 entries in call queue - the queue is then 'run' but
after the function ends

whebn the four functions from queue execute it will store another entries
in the queue - untill the queue will be emptied then the execution finishes

the disadvantages here are seen

I. it is almost the same simple as oryguinal simpel recursion
method

II. the depth of recursion will be more shallow as when new
entries are added old are removed and the call queue may be
set on circular ram area - it is for example queue may have 10 MB
but work on 100 MB working set (depending on case)

III. the efficiency problem are probably resolved and
probably this verion will not be slower than iterative method
- note in fact call adreses of function not need to be stored
in many cases as here above - as the same function is called
each time, only arguments need to be stored

IV. order in which the call queue choses pixels is more natural

profesor fir thinks it should be build in new c compilers
to enhance recursion abilities of c, hovver he not expect
the big compiler writers which are sometimes slow to
adapt new methods will do it soon but the solution is not
bad to quite professor

[read more articles of PROGRAMMING TODAY your new news programming
magazine]

On 20/03/2024 13:15, fir wrote:
>
> the idea is then compiler met the queue keyword it
> not generates call to function but stores the pointer to it and
> the arguments into separate runtime 'list' (it is internal array)
> and then continues execution of the parent function
>

And we need big stacks so that people can use poor programming
approaches without the system falling over, and we need small stacks
becausem whilst modern stacks are usually just in cached main memory, if
stacks are small then potentially the hardware people can manufacture
very fast and as a tradeoff therefore very low capacity, special memory
to use for the stack.

--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

Malcolm McLean wrote:
> On 20/03/2024 13:15, fir wrote:
>>
>> the idea is then compiler met the queue keyword it
>> not generates call to function but stores the pointer to it and
>> the arguments into separate runtime 'list' (it is internal array)
>> and then continues execution of the parent function
>>
>
> And we need big stacks so that people can use poor programming
> approaches without the system falling over, and we need small stacks
> becausem whilst modern stacks are usually just in cached main memory, if
> stacks are small then potentially the hardware people can manufacture
> very fast and as a tradeoff therefore very low capacity, special memory
> to use for the stack.
>

nah thet talking on low stacks is probably bulshit...there is a thing called
"hardware prefetchers" and if you use that stack liek an array (and that
what as i describe is like that its an 'list') then you got it totally
pre-cached...see my other threads i incidentally was writing as an
answer of what said somewhat "against" stacks

fir wrote:
> pre-cached...see my other threads i incidentally was writing as an
> answer of what said somewhat "against" stacks

of what YOU said somewhat "against" stacks [errata]

(my conclusion is there is probably no need to fear/avoid
setting stack to 100 MB if yur machine has 4GB+ of ram
- and if you set it just use it

and if it will slow down programs at least i would like to observe that
differences which presently i doubt (as stack is the same ram as heap
and static)

>Malcolm McLean wrote:
>> On 20/03/2024 13:15, fir wrote:
>>>
>>> the idea is then compiler met the queue keyword it
>>> not generates call to function but stores the pointer to it and
>>> the arguments into separate runtime 'list' (it is internal array)
>>> and then continues execution of the parent function
>>>
>>
>> And we need big stacks so that people can use poor programming
>> approaches without the system falling over, and we need small stacks
>> becausem whilst modern stacks are usually just in cached main memory, if
>> stacks are small then potentially the hardware people can manufacture
>> very fast and as a tradeoff therefore very low capacity, special memory
>> to use for the stack.

Speaking as someone works in processor design, I'd point out that
modern L1 caches have a three-cycle[*] latency (call it a nanosecond at
3Ghz). As the stack is just regular memory in all modern
processors, accesses to the stack are almost free so long
as they're present in the L1 cache.

Dedicated SRAM on-chip to support a "special memory stack"
would not be any faster and would cost valuable area on the
die and would result in strange software workarounds to
work with the limited stack and extra context switching overhead
to save and restore the 'special memory stack'.

Note that most modern processors have an on-chip return stack
to aid in reducing pipeline bubbles during function return.

[*] Load to use

And your characterization that big stacks are required because
of 'poor programming approaches' shows a lack of understanding
of modern programming workloads.

fir wrote:
> PROGRAMMING TODAY new approach in C strict
> runtime allows us to improve reccurency: call queue

this article is kinda prima aprilis joke becouse it is fictional article
in fictional magazine but the call queue idea seem to be okay imo

maybe there is even something more in here becouse this idea edges
somewhat with paralelisation - becouse those queued functions are
something like async calls - though here are not executed in parralel
but stored in list - but it is closed to paralelisation somewhat and
maybe something more is also here like finding some way of doing more
nice paralelism..i maybe will try to rething on it yet some later time