* What are the arguments in favor of delay/force in eval.c? @ 2005-12-06 21:14 Rob Browning 2005-12-07 21:31 ` Kevin Ryde 0 siblings, 1 reply; 10+ messages in thread From: Rob Browning @ 2005-12-06 21:14 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-06 21:14 What are the arguments in favor of delay/force in eval.c? Rob Browning @ 2005-12-07 21:31 ` Kevin Ryde 2005-12-07 22:47 ` Rob Browning 0 siblings, 1 reply; 10+ messages in thread From: Kevin Ryde @ 2005-12-07 21:31 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-07 21:31 ` Kevin Ryde @ 2005-12-07 22:47 ` Rob Browning 2005-12-08 0:29 ` Kevin Ryde 2005-12-08 0:57 ` Ken Raeburn 0 siblings, 2 replies; 10+ messages in thread From: Rob Browning @ 2005-12-07 22:47 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-07 22:47 ` Rob Browning @ 2005-12-08 0:29 ` Kevin Ryde 2005-12-08 0:52 ` Rob Browning 2005-12-08 0:57 ` Ken Raeburn 1 sibling, 1 reply; 10+ messages in thread From: Kevin Ryde @ 2005-12-08 0:29 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-08 0:29 ` Kevin Ryde @ 2005-12-08 0:52 ` Rob Browning 2005-12-10 0:11 ` Kevin Ryde 0 siblings, 1 reply; 10+ messages in thread From: Rob Browning @ 2005-12-08 0:52 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-08 0:52 ` Rob Browning @ 2005-12-10 0:11 ` Kevin Ryde 2005-12-10 4:23 ` Rob Browning 0 siblings, 1 reply; 10+ messages in thread From: Kevin Ryde @ 2005-12-10 0:11 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-10 0:11 ` Kevin Ryde @ 2005-12-10 4:23 ` Rob Browning 2005-12-14 21:10 ` Kevin Ryde 0 siblings, 1 reply; 10+ messages in thread From: Rob Browning @ 2005-12-10 4:23 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-10 4:23 ` Rob Browning @ 2005-12-14 21:10 ` Kevin Ryde 0 siblings, 0 replies; 10+ messages in thread From: Kevin Ryde @ 2005-12-14 21:10 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-07 22:47 ` Rob Browning 2005-12-08 0:29 ` Kevin Ryde @ 2005-12-08 0:57 ` Ken Raeburn 2005-12-08 1:28 ` Rob Browning 1 sibling, 1 reply; 10+ messages in thread From: Ken Raeburn @ 2005-12-08 0:57 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: What are the arguments in favor of delay/force in eval.c? 2005-12-08 0:57 ` Ken Raeburn @ 2005-12-08 1:28 ` Rob Browning 0 siblings, 0 replies; 10+ messages in thread From: Rob Browning @ 2005-12-08 1:28 UTC (permalink / raw) Cc: guile-devel 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2005-12-14 21:10 UTC | newest] Thread overview: 10+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2005-12-06 21:14 What are the arguments in favor of delay/force in eval.c? Rob Browning 2005-12-07 21:31 ` Kevin Ryde 2005-12-07 22:47 ` Rob Browning 2005-12-08 0:29 ` Kevin Ryde 2005-12-08 0:52 ` Rob Browning 2005-12-10 0:11 ` Kevin Ryde 2005-12-10 4:23 ` Rob Browning 2005-12-14 21:10 ` Kevin Ryde 2005-12-08 0:57 ` Ken Raeburn 2005-12-08 1:28 ` Rob Browning
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).