What are the arguments in favor of delay/force in eval.c?

What are the arguments in favor of delay/force in eval.c?

[Rob Browning]

Does anyone know what the arguments are, if any, for implementing
delay and force directly in eval.c rather than more generically, at
the Scheme level, perhaps in boot-9.scm via define-record, lambda,
etc.?

  (define-record promise
    ...)

  (define-syntax (delay exp) ... (make-promise ... (lambda () (exp) ...) ...))

  (define-syntax (force promise) ... ((promise-get-thunk promise)) ...)

Is the primary argument efficiency?

I ask because I was thinking about SRFI-45 (perhaps in prelude to
SRFI-40) and was trying to determine what Guile specific constraints
might apply to an implementation.

   SRFI-45: Primitives for Expressing Iterative Lazy Algorithms
   SRFI-40: A Library of Streams

If these were added to Guile, then we might want the SRFI-40 delay and
force to just replace our existing implementations.

Thanks
-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> Does anyone know what the arguments are, if any, for implementing
> delay and force directly in eval.c rather than more generically, at
> the Scheme level, perhaps in boot-9.scm via define-record, lambda,
> etc.?

I imagine some C code is less bytes for a promise object.

(Speaking of which, I'd thought before that once a promise is forced
it shouldn't need a mutex any more, which would save a bit of time and
space.)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Rob Browning]

Kevin Ryde <user42@zip.com.au> writes:

> (Speaking of which, I'd thought before that once a promise is forced
> it shouldn't need a mutex any more, which would save a bit of time and
> space.)

I suppse it might, though you'd have to be very careful with the
coding.  i.e. (offhand) you would probably have to do something like
this:

  SCM mutex = SCM_PROMISE_MUTEX(p);  // assume atomic copy
  if(scm_is_null(mutex))
    result = SCM_PROMISE_DATA(p);  // [1]
  else
  {
    scm_lock_mutex(mutex);
    if(scm_is_null(SCM_PROMISE_MUTEX(p))  // must check again after lock
    {
      // someone was already evaluating when we started
      // (and must have finished now)
      result = SCM_PROMISE_DATA(p);
    }
    else
    {
      SCM ans = scm_call_0(SCM_PROMISE_DATA (ans));
      SCM_SET_PROMISE_DATA(p, ans);
      SCM_SET_PROMISE_MUTEX(p, SCM_BOOL_F) // (do last to avoid race at [1])
      result = SCM_PROMISE_DATA(p);
    } 
    scm_unlock_mutex(mutex);
  }

Note that this wouldn't be safe if the initial mutex assignment might
copy a value that has been half filled by some other thread.

Of course, if we're interested in srfi-45, then it would require
somewhat more...

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> Note that this wouldn't be safe if the initial mutex assignment might
> copy a value that has been half filled by some other thread.

Yep, a single fetch is assumed to be ok in other places too.

An even more radical idea would be not to have a mutex at all.  If two
threads are simultaneously forcing then whichever finishes first sets
the forced value.  (The same way that recursive forcing results in the
first finisher setting the value.)

(Oh, and to bring this slightly back on-topic, I'm imagining that if
streams or lazy stuff throw off quite a few forced promises then it's
a good thing for them to be small and fast.)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Rob Browning]

Kevin Ryde <user42@zip.com.au> writes:

> An even more radical idea would be not to have a mutex at all.  If
> two threads are simultaneously forcing then whichever finishes first
> sets the forced value.  (The same way that recursive forcing results
> in the first finisher setting the value.)

This would only work if you forbid side-effects, right?  Either that,
or perhaps we'd just have to document the resulting semantics,
whatever they are.

I was also wondering about the possibilities for deadlock with the
current code, and then what they might be with a srfi-45 force, which
may do more work (it's basically a trampoline approach to the problem
described in the srfi).

I suppose one of the questions here (and one of the traditional
questions) is just how much protection/overhead Guile should try to
provide by default.

> (Oh, and to bring this slightly back on-topic, I'm imagining that if
> streams or lazy stuff throw off quite a few forced promises then it's
> a good thing for them to be small and fast.)

Quite possibly.  

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Ken Raeburn]

On Dec 7, 2005, at 17:47, Rob Browning wrote:
>     {
>       SCM ans = scm_call_0(SCM_PROMISE_DATA (ans));
>       SCM_SET_PROMISE_DATA(p, ans);
>       SCM_SET_PROMISE_MUTEX(p, SCM_BOOL_F) // (do last to avoid  
> race at [1])
>       result = SCM_PROMISE_DATA(p);
>     }

Of course, the compiler might reorder these accesses, unless you make  
everything volatile.  Even then, the CPU still might reorder them so  
another compiler might see something different.  I'd be worried about  
the reordering or caching in another processor if the code decides it  
can bypass all the mutex stuff, too.

Once every thread agrees on the new data value and no mutex needed,  
everything should be fine, but managing the transition to that state  
(without adding *another* mutex) is very tricky.

>     scm_unlock_mutex(mutex);

That (and the lock call) is probably the only barrier past which you  
can safely assume that non-volatile accesses won't be reordered.   
(And for CPU reordering, you probably shouldn't depend too much on  
simply declaring storage to be volatile.  AFAIK most compilers won't  
insert memory-barrier instructions before and after every volatile  
access.)  Actually, I think some memory models will allow some  
accesses to be moved into the region where the lock is held from  
outside it.

Ken


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Rob Browning]

Ken Raeburn <raeburn@raeburn.org> writes:

> Of course, the compiler might reorder these accesses, unless you
> make everything volatile.  Even then, the CPU still might reorder
> them so another compiler might see something different.  I'd be
> worried about the reordering or caching in another processor if the
> code decides it can bypass all the mutex stuff, too.
>
> Once every thread agrees on the new data value and no mutex needed,
> everything should be fine, but managing the transition to that state
> (without adding *another* mutex) is very tricky.

Yeah.  I definitely wondered if there was a way to do it completely
safely without full protection.  I'm always hesitant about code that
relies on so many assumptions, though I (obviously) wasn't thinking
about the reordering issues.  (Of course, I pretty much always fully
protect things in real code, so it's not an issue...)

> Actually, I think some memory models will allow some accesses to be
> moved into the region where the lock is held from outside it.

Interesting.

Thanks
-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> This would only work if you forbid side-effects, right?

Well, leave it up to the application to keep itself out of trouble if
the code is not reentrant.  That'd be consistent a general policy of
not stopping stupid multi-thread code, only code that might crash the
interpreter.

> I was also wondering about the possibilities for deadlock with the
> current code, and then what they might be with a srfi-45 force,

Whenever arbitrary code executes in a mutex I guess there's scope for
that.  srfi-45 shouldn't be inherently worse.


Some code below (untested) for what I think "force" could look like
without per-promise mutexes.

Having a magic "uncomputed" value means no locking at all once
computed (same as your code).  The thunk to be called is in a separate
field, zapped once no longer needed.

Second block of code is with two magic "uncomputed" values, one for
normal and one for srfi-45 style lazy promises.  If I understand how
they're supposed to work :-).



#define SCM_PROMISE_DATA   SCM_SMOB_OBJECT
#define SCM_PROMISE_EXPR   SCM_SMOB_OBJECT_2

{
  SCM data, expr, ans;

  SCM_VALIDATE_SMOB (1, promise, promise);

  data = SCM_PROMISE_DATA (promise);
  if (data != SCM_PROMISE_MAGIC_UNCOMPUTED_INDICATOR)
    return data;

  SCM_CRITICAL_SECTION_START;
  data = SCM_PROMISE_DATA (promise);
  expr = SCM_PROMISE_EXPR (promise);
  SCM_CRITICAL_SECTION_END;

  if (data != SCM_PROMISE_MAGIC_UNCOMPUTED_INDICATOR)
    return data;

  ans = scm_call_0 (expr);

  SCM_CRITICAL_SECTION_START;
  data = SCM_PROMISE_DATA (promise);
  if (data == SCM_PROMISE_MAGIC_UNCOMPUTED_INDICATOR)
    {
      SCM_SET_PROMISE_DATA (promise, ans);         /* we set the value */
      SCM_SET_PROMISE_EXPR (promise, SCM_BOOL_F);  /* gc the expression */
    }
  else
    {
      /* recursive force or other thread set the value, return that */
      ans = data;
    }
  SCM_CRITICAL_SECTION_END;

  return ans;
}



{
  SCM data, expr, ans;

  SCM_VALIDATE_SMOB (1, promise, promise);

again:
  data = SCM_PROMISE_DATA (promise);
  if ((data & ~1) != SCM_PROMISE_MAGIC_UNCOMPUTED)
    return data;

  SCM_CRITICAL_SECTION_START;
  data = SCM_PROMISE_DATA (promise);
  expr = SCM_PROMISE_EXPR (promise);
  SCM_CRITICAL_SECTION_END;

  if ((data & ~1) != SCM_PROMISE_MAGIC_UNCOMPUTED)
    return data;

  ans = scm_call_0 (expr);

  SCM_CRITICAL_SECTION_START;
  data = SCM_PROMISE_DATA (promise);
  if (data == SCM_PROMISE_MAGIC_UNCOMPUTED_LAZY && SCM_PROMISE_P (ans))
    {
      /* SRFI-45 lazy promise, mutate ourselves to ANS and go again */
      SCM_SET_PROMISE_DATA (promise, SCM_PROMISE_DATA (ans));
      SCM_SET_PROMISE_EXPR (promise, SCM_PROMISE_EXPR (ans));
      SCM_CRITICAL_SECTION_END;
      goto again;
    }
  else if (data == SCM_PROMISE_MAGIC_UNCOMPUTED_NORMAL)
    {
      SCM_SET_PROMISE_DATA (promise, ans);         /* we set the value */
      SCM_SET_PROMISE_EXPR (promise, SCM_BOOL_F);  /* gc the expression */
    }
  else
    {
      /* recursive force or other thread set the value, return that */
      ans = data;
    }
  SCM_CRITICAL_SECTION_END;

  return ans;
}


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Rob Browning]

Kevin Ryde <user42@zip.com.au> writes:

>> I was also wondering about the possibilities for deadlock with the
>> current code, and then what they might be with a srfi-45 force,
>
> Whenever arbitrary code executes in a mutex I guess there's scope for
> that.  srfi-45 shouldn't be inherently worse.

I'm not sure either way yet.  There are subtleties of srfi-45 that I
still don't fully understand.  If you haven't already, check out the
reference implementation of force, and then the test cases.

I'll probably have to wait until I feel like I understand the detailed
semantics better before I can comment much.

> Second block of code is with two magic "uncomputed" values, one for
> normal and one for srfi-45 style lazy promises.  If I understand how
> they're supposed to work :-).

You may have already noticed this, but I think the semantics of
SRFI-45 force/delay are supposed to be a strict superset of R5RS
force/delay, so in theory we might be able to have just one type of
promise.

-- 
Rob Browning
rlb @defaultvalue.org and @debian.org; previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: What are the arguments in favor of delay/force in eval.c?

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> You may have already noticed this, but I think the semantics of
> SRFI-45 force/delay are supposed to be a strict superset of R5RS
> force/delay, so in theory we might be able to have just one type of
> promise.

As far as I can tell there's two types of promises, one generated by
`delay' the other by `lazy', so if you only use delay+force you get
r5rs, if you use lazy+force you get the new style.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel