Re: escaping from a recursive call

[Olivier Dion]

On Thu, 10 Nov 2022, Damien Mattei <damien.mattei@gmail.com> wrote:
> will it work well in // code with future or thread ,i'm having already
> problem with // code that,compute well but show no speed up, is it because
> of continuation? not being compatible with //,does macro generates
> functions that causes unknown problem to // code, i try to get rid of
> macros and continuation in // code but i always fall back using
> them...

There's many problem that arise when you play with continuation in
multi-threads environment.  See the scheduler of my library
guile-parallel <https://sr.ht/~old/guile-parallel/> for example.

> but since i have problem with // speed up i try other procedure:
> below you see the need of having to sort of escape ,'return from the
> current level in case of end of lists,and 'return-rec from the full stack
> of recursions in cas of #f result.

>
> (define (unify-two-minterms-rec mt1 mt2)
>
>   {err <+ #f}
>
>   (def (unify-two-lists-tolerant-one-mismatch mt1 mt2)
>
>        (if {(null? mt1) and (null? mt2)}
>          (return '()))
>
>        (if {{(null? mt1) and (not (null? mt2))} or {(not (null? mt1))
> and (null? mt2)}}
>          (return-rec #f))
>       
>
>        {fst-mt1 <+ (first mt1)}
>        {fst-mt2 <+ (first mt2)}
>
>        (if (equal? fst-mt1 fst-mt2) (return (cons fst-mt1
>                                                 
> (unify-two-lists-tolerant-one-mismatch (rest mt1) (rest mt2)))))
>        (if err (return-rec #f))
>
>        {err <- #t}
>        (cons 'x
>            (unify-two-lists-tolerant-one-mismatch (rest mt1) (rest mt2))))
>
>   (unify-two-lists-tolerant-one-mismatch mt1 mt2))

If you make your algorithm tail recursive, you should be able to espace
from any level of recursion without penalty. From what I've read here,
your algorithm is not tail recursive and so a frame is made a each level
of recursion, requiring an unwinding of it after.  Keep in mind that
delimited continuation are not free.  It's kind of like a userspace
context switching.  It involves memory load/store and stack unwinding,
probably also other implementation dependant details in the runtime.  I
would not advice to use them in critical performant scenario nor in
parallelized algorithm.

> i have tested but still no speed up with 'futures, i have test it with
> Guile but the same problem is with Racket. Seems 'furure makes no speed up
> , it is hard to share the benchmarks now that i have updated the 'def of
> Scheme+ but i  then i have to release a new version and update all the
> github and documentation online.Soon i hope...

I haven't tackle your minterm problem directly here, but from a glimpse
of it, I don't see which part can be parallelize?  Furthermore, you have
a global state `err` that will impose penalty for sure.  Maybe doing a
divide and conquer approach?  In that case I would highly recommend
using vector instead of list, but you would still have problem with the
global state that should be an atomic box.

-- 
Olivier Dion
oldiob.dev