* scm_i_fraction_reduce thread safety @ 2003-12-11 11:43 Bill Schottstaedt 2003-12-11 19:19 ` Carl Witty 0 siblings, 1 reply; 22+ messages in thread From: Bill Schottstaedt @ 2003-12-11 11:43 UTC (permalink / raw) Actually I was thinking about garbage collection when I wrote that note (more of a reminder to myself to check it, which I of course forgot to do). I'd vote for a lock, if it's really an issue. On the need for reduction, I wonder how much of that notoriety is due to Knuth -- his discussion of this was in a slightly artificial context, and I've been intending for a long time to check some "real-world" situation. (I think it's less of a problem than calling gcd all the time). Perhaps Han-Wen has some info on this? _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2003-12-11 11:43 scm_i_fraction_reduce thread safety Bill Schottstaedt @ 2003-12-11 19:19 ` Carl Witty 2003-12-12 12:11 ` Bill Schottstaedt ` (2 more replies) 0 siblings, 3 replies; 22+ messages in thread From: Carl Witty @ 2003-12-11 19:19 UTC (permalink / raw) Cc: guile-devel On Thu, 2003-12-11 at 03:43, Bill Schottstaedt wrote: > On the need for reduction, I wonder how much of that > notoriety is due to Knuth -- his discussion of this > was in a slightly artificial context, and I've been > intending for a long time to check some "real-world" > situation. (I think it's less of a problem than > calling gcd all the time). I don't have any data on this (merely uninformed opinions), but I'd be nervous about not reducing fractions. If you always reduce, I think that multiplies the cost of operations by about log(n) (where n is the number of bits in the numerator or denominator) (assuming you use Euclid's gcd algorithm, instead of something asymptotically faster). On the other hand, if somebody has an algorithm that builds up fractions which are almost always reducible, then not reducing can make the algorithm slower by an arbitrary amount. For instance, I recently had a problem of coming up with a simple formula (to find the volume of an n-dimensional simplex, if you're curious), where part of the problem was to compute (1/2)*(2/3)*(3/4)*(4/5)*...*(n/(n+1)). When you're working out the formula, it's easy to recognize that this is 1/(n+1). But if I had just wanted a few answers, rather than a general formula, I might have written a little program and ended up with fractions of the form n!/(n+1)!, which would be highly inefficient to work with for large n. I think that one way to avoid arbitrarily-bad behavior is to reduce only if the numerator or denominator is "sufficiently large" (I think this is at most a constant factor worse than always reducing). For instance, we could reduce fractions only if the numerator or denominator is a bignum, in hopes that we will get back to fixnum-sized numbers. Carl Witty _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2003-12-11 19:19 ` Carl Witty @ 2003-12-12 12:11 ` Bill Schottstaedt 2003-12-12 15:04 ` Paul Jarc 2003-12-12 23:23 ` Kevin Ryde 2 siblings, 0 replies; 22+ messages in thread From: Bill Schottstaedt @ 2003-12-12 12:11 UTC (permalink / raw) Cc: guile-devel > I think that one way to avoid arbitrarily-bad behavior is to reduce only > if the numerator or denominator is "sufficiently large" (I think this is > at most a constant factor worse than always reducing). For instance, we > could reduce fractions only if the numerator or denominator is a bignum, > in hopes that we will get back to fixnum-sized numbers. That strikes me as a good idea -- I think it would also fit into the current code pretty easily. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2003-12-11 19:19 ` Carl Witty 2003-12-12 12:11 ` Bill Schottstaedt @ 2003-12-12 15:04 ` Paul Jarc 2003-12-12 23:23 ` Kevin Ryde 2 siblings, 0 replies; 22+ messages in thread From: Paul Jarc @ 2003-12-12 15:04 UTC (permalink / raw) Cc: Bill Schottstaedt, guile-devel Carl Witty <cwitty@newtonlabs.com> wrote: > For instance, we could reduce fractions only if the numerator or > denominator is a bignum, in hopes that we will get back to > fixnum-sized numbers. Or reduce when the numerator or denominator is nearly a bignum, in the hopes that we will prevent the need for allocating bignums. paul _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2003-12-11 19:19 ` Carl Witty 2003-12-12 12:11 ` Bill Schottstaedt 2003-12-12 15:04 ` Paul Jarc @ 2003-12-12 23:23 ` Kevin Ryde 2004-01-10 22:38 ` Marius Vollmer 2 siblings, 1 reply; 22+ messages in thread From: Kevin Ryde @ 2003-12-12 23:23 UTC (permalink / raw) Cc: Bill Schottstaedt, guile-devel Bill Schottstaedt <bil@ccrma.Stanford.EDU> writes: > > I'd vote for a lock, I guess everywhere inspecting the parts of a fraction would need to acquire and release such a lock. Perhaps a macro that did that and delivered out the parts could stop it being too awful when coding. > if it's really an issue. Unfortunately I believe it is, in the new-style free-running concurrent posix threads. It'll be one of those threading things that might almost never actually cause a problem, but alas is not right. > On the need for reduction, I wonder how much of that > notoriety is due to Knuth -- his discussion of this > was in a slightly artificial context, and I've been > intending for a long time to check some "real-world" > situation. I guess +, -, *, / will keep increasing num and/or den (though perhaps with some cancellation in the num for + and -), unless steps are taken at some point. > (I think it's less of a problem than calling gcd all the time). The claim in gmp (without anything actual to cite :-), is that because gcd is O(N^2) it's better to do a couple of smaller one's sooner than to allow a product to accumulate and do a big one later. Of course if one knows or suspects not much cancellation will be possible in a given algorithm, then all theories about automated reductions go out the window. A general purpose fraction type is probably not the tool for the job in that case. Carl Witty <cwitty@newtonlabs.com> writes: > > I think that one way to avoid arbitrarily-bad behavior is to reduce only > if the numerator or denominator is "sufficiently large" (I think this is > at most a constant factor worse than always reducing). mpz_t allocated memory could be counted towards the mtrigger, to provoke a gc when big numbers are using up memory. That's probably a good idea anyway. The gc could nose around and attempt to reduce likely looking big fractions. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2003-12-12 23:23 ` Kevin Ryde @ 2004-01-10 22:38 ` Marius Vollmer 2004-01-10 23:29 ` Kevin Ryde 0 siblings, 1 reply; 22+ messages in thread From: Marius Vollmer @ 2004-01-10 22:38 UTC (permalink / raw) Cc: Bill Schottstaedt, guile-devel Kevin Ryde <user42@zip.com.au> writes: > Bill Schottstaedt <bil@ccrma.Stanford.EDU> writes: >> >> I'd vote for a lock, > > I guess everywhere inspecting the parts of a fraction would need to > acquire and release such a lock. Perhaps a macro that did that and > delivered out the parts could stop it being too awful when coding. This is a general problem with the data structures in libguile and we need to solve it generally. I haven't made my mind up about this yet... there is the drastic and easy way: restrict guile threads to be cooperative (then we don't need object-level locks). Or we could allow full concurrency and be pedantic about object-level locks. Allowing full concurrency is very attractive if we can pull it off. It looks like we can, but it will be hard to be convinced that absolutely no race conditions exist in libguile, and that users of libguile wont introduce new ones. > Unfortunately I believe it is, in the new-style free-running > concurrent posix threads. It'll be one of those threading things > that might almost never actually cause a problem, but alas is not > right. Right. I don't have the courage or arguments right now to remove the fully concurrent threads, but I know I would feel happier if we didn't had them... -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-10 22:38 ` Marius Vollmer @ 2004-01-10 23:29 ` Kevin Ryde 2004-01-11 1:31 ` Marius Vollmer 0 siblings, 1 reply; 22+ messages in thread From: Kevin Ryde @ 2004-01-10 23:29 UTC (permalink / raw) Cc: Bill Schottstaedt, Carl Witty, guile-devel Marius Vollmer <mvo@zagadka.de> writes: > > This is a general problem with the data structures in libguile and we > need to solve it generally. I'd think nobody can mind if strange things happen when one thread is reading something another is writing. (Well, perhaps as long as it doesn't actually crash the interpreter.) But the problem at the moment with reducing fractions is that it's happening when merely reading the value out. Or what one would hope was merely reading the value, ie. printing or equality testing. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-10 23:29 ` Kevin Ryde @ 2004-01-11 1:31 ` Marius Vollmer 2004-01-12 0:51 ` Kevin Ryde 0 siblings, 1 reply; 22+ messages in thread From: Marius Vollmer @ 2004-01-11 1:31 UTC (permalink / raw) Cc: Carl Witty, guile-devel Kevin Ryde <user42@zip.com.au> writes: > But the problem at the moment with reducing fractions is that it's > happening when merely reading the value out. Or what one would hope > was merely reading the value, ie. printing or equality testing. Yes, I agree that we should do somehting about this, even when the general problem still remains unaddressed. User code should only use scm_numerator and scm_denominator to access parts of the fraction object and those functions will first reduce the fraction (in a thread safe way). Wouldn't that be enough? -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-11 1:31 ` Marius Vollmer @ 2004-01-12 0:51 ` Kevin Ryde 2004-01-12 5:22 ` Richard Todd 2004-01-21 0:00 ` Marius Vollmer 0 siblings, 2 replies; 22+ messages in thread From: Kevin Ryde @ 2004-01-12 0:51 UTC (permalink / raw) Cc: Bill Schottstaedt, Carl Witty, guile-devel Marius Vollmer <mvo@zagadka.de> writes: > > User code should only use scm_numerator and scm_denominator to access > parts of the fraction object and those functions will first reduce the > fraction (in a thread safe way). Wouldn't that be enough? Yep, though it seems a shame the accessors have to be slowed down just so printing and equality can write back. It's probably worth thinking about reduction policy. Certainly printing and equality need a reduced form, but if one never actually does those then it might be nice to have some other way, either automatic like under gc or explicit. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-12 0:51 ` Kevin Ryde @ 2004-01-12 5:22 ` Richard Todd 2004-01-14 21:09 ` Kevin Ryde 2004-01-21 0:03 ` Marius Vollmer 2004-01-21 0:00 ` Marius Vollmer 1 sibling, 2 replies; 22+ messages in thread From: Richard Todd @ 2004-01-12 5:22 UTC (permalink / raw) Cc: Bill Schottstaedt, guile-devel, Carl Witty, Marius Vollmer Kevin Ryde wrote: > Marius Vollmer <mvo@zagadka.de> writes: > >>User code should only use scm_numerator and scm_denominator to access >>parts of the fraction object and those functions will first reduce the >>fraction (in a thread safe way). Wouldn't that be enough? > > > Yep, though it seems a shame the accessors have to be slowed down just > so printing and equality can write back. I may not fully understand this, but after reading through the messages on the list, and having been awake for 36 hours, I can't help but think at least two things: 1) If you are worried about thread safety, the most fool-proof C interface probably does not allow separate access to numerator and denominator, since they need to be read in one atomic operation to ensure consistent results in the face of other mutating code. 2) Aren't (numerator frac) and (denominator frac) themselves other examples of would-be readers that might have to 'write back' in this setup? According to r5rs they return the reduced value. For the speed issue in general, doesn't it come down to whether the extra gcd()s of eager reduction would be cheaper than the mutex_lock()s of lazy reduction? If I'm thinking straight, the mutex only seems necessary if SCM_FRACTION_REDUCED(n) == #f, so as long as you don't mutate/reduce/mutate/reduce in a tight loop, there may not be much mutexing at all. Seems like it could be tried both ways. Richard _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-12 5:22 ` Richard Todd @ 2004-01-14 21:09 ` Kevin Ryde 2004-01-21 0:03 ` Marius Vollmer 1 sibling, 0 replies; 22+ messages in thread From: Kevin Ryde @ 2004-01-14 21:09 UTC (permalink / raw) Richard Todd <richardt@vzavenue.net> writes: > > 1) If you are worried about thread safety, the most fool-proof C > interface probably does not allow separate access to numerator and > denominator, since they need to be read in one atomic operation to > ensure consistent results in the face of other mutating code. Or don't mutate, except possibly under gc. > 2) Aren't (numerator frac) and (denominator frac) themselves other > examples of would-be readers that might have to 'write back' in this > setup? Yep. > For the speed issue in general, doesn't it come down to whether the > extra gcd()s of eager reduction would be cheaper than the > mutex_lock()s of lazy reduction? Well, locks will slow down accesses, but the question of when to do gcds really depends on num+den at risk of growing more or less unboundedly and on the way gcd is O(N^2) so much better to do on smaller operands where possible (assuming a reduction will in fact be wanted at some point, which would not be the case say if rounding to an int or float at the end). _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-12 5:22 ` Richard Todd 2004-01-14 21:09 ` Kevin Ryde @ 2004-01-21 0:03 ` Marius Vollmer 1 sibling, 0 replies; 22+ messages in thread From: Marius Vollmer @ 2004-01-21 0:03 UTC (permalink / raw) Cc: Bill Schottstaedt, Carl Witty, guile-devel Richard Todd <richardt@vzavenue.net> writes: > 1) If you are worried about thread safety, the most fool-proof C > interface probably does not allow separate access to numerator and > denominator, since they need to be read in one atomic operation to > ensure consistent results in the face of other mutating code. Guile fractions can not mutated in general: they always represent one value. The mutation that might take place is a reduction, but that might only happen once. After a fraction is reduced, it stays that way. So when you have a reduced fraction you can safely return the nominator, say, without having to worry that a later access to the denominator will return something bogus. -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-12 0:51 ` Kevin Ryde 2004-01-12 5:22 ` Richard Todd @ 2004-01-21 0:00 ` Marius Vollmer 2004-01-21 3:11 ` Carl Witty 1 sibling, 1 reply; 22+ messages in thread From: Marius Vollmer @ 2004-01-21 0:00 UTC (permalink / raw) Kevin Ryde <user42@zip.com.au> writes: > Marius Vollmer <mvo@zagadka.de> writes: >> >> User code should only use scm_numerator and scm_denominator to access >> parts of the fraction object and those functions will first reduce the >> fraction (in a thread safe way). Wouldn't that be enough? > > Yep, though it seems a shame the accessors have to be slowed down just > so printing and equality can write back. Is that slow down significant? The logic could be like if fraction is not reduced: lock if fraction is not reduced: reduce it unlock read it So in the common case of a reduced fraction, no locks would be necessary. (This works since a fraction can never go from reduced to unreduced.) -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-21 0:00 ` Marius Vollmer @ 2004-01-21 3:11 ` Carl Witty 2004-01-21 21:06 ` Marius Vollmer 2004-01-27 22:15 ` Dirk Herrmann 0 siblings, 2 replies; 22+ messages in thread From: Carl Witty @ 2004-01-21 3:11 UTC (permalink / raw) Cc: guile-devel On Tue, 2004-01-20 at 16:00, Marius Vollmer wrote: > Kevin Ryde <user42@zip.com.au> writes: > > Yep, though it seems a shame the accessors have to be slowed down just > > so printing and equality can write back. > > Is that slow down significant? The logic could be like > > if fraction is not reduced: > lock > if fraction is not reduced: > reduce it > unlock > read it > > So in the common case of a reduced fraction, no locks would be > necessary. (This works since a fraction can never go from reduced to > unreduced.) I'm afraid this doesn't work. The idiom is known as "double-checked locking"; see http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html for an explanation of why it doesn't work. (Briefly: the "reduce it" code will do something like the following: write numerator, write denominator, write "fraction is reduced" marker. The compiler is allowed to re-order these writes, so the "fraction is reduced" marker is written before the numerator and denominator. Even if it does not, on a multi-processor machine, the memory system may reorder these writes between processors, unless you put (expensive and non-portable) "memory barrier" instructions in the appropriate places.) Read the web page linked above before you suggest ways to fix this. Carl Witty _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-21 3:11 ` Carl Witty @ 2004-01-21 21:06 ` Marius Vollmer 2004-01-27 22:15 ` Dirk Herrmann 1 sibling, 0 replies; 22+ messages in thread From: Marius Vollmer @ 2004-01-21 21:06 UTC (permalink / raw) Cc: guile-devel Carl Witty <cwitty@newtonlabs.com> writes: > I'm afraid this doesn't work. The idiom is known as "double-checked > locking"; Right! Thanks. -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-21 3:11 ` Carl Witty 2004-01-21 21:06 ` Marius Vollmer @ 2004-01-27 22:15 ` Dirk Herrmann 2004-01-27 23:24 ` Rob Browning 1 sibling, 1 reply; 22+ messages in thread From: Dirk Herrmann @ 2004-01-27 22:15 UTC (permalink / raw) Cc: Marius Vollmer, guile-devel Carl Witty wrote: >On Tue, 2004-01-20 at 16:00, Marius Vollmer wrote: > > >> if fraction is not reduced: >> lock >> if fraction is not reduced: >> reduce it >> unlock >> read it >> >> >I'm afraid this doesn't work. The idiom is known as "double-checked >locking"; see >http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html >for an explanation of why it doesn't work. (Briefly: the "reduce it" >code will do something like the following: write numerator, write >denominator, write "fraction is reduced" marker. The compiler is >allowed to re-order these writes, so the "fraction is reduced" marker is >written before the numerator and denominator. Even if it does not, on a >multi-processor machine, the memory system may reorder these writes >between processors, unless you put (expensive and non-portable) "memory >barrier" instructions in the appropriate places.) > > Interesting - and makes me nervous. If one thread uses the code (set-cdr! pair (cons #t #t)) then this will translate into the writing of three memory locations, namely the car and cdr of the new cell plus the cdr of the old cell. If these write can get arbitrarily re-ordered, then a second thread may access (cdr pair) and find the reference to the new cell, which is not yet initialized. Accessing the uninitalized new cell might lead to a crash of the second thread (I have not thoroughly checked this) . Certainly, this way of accessing memory is wrong, since the user should have done some locking between the two threads. But, (if my assumption is right) the bad thing is, that we are dealing with pure scheme code here, and only the fact that we run the code in a multithreaded environment instead of within a single thread can cause pure scheme code to crash. One might say this is also true for all other kinds of programs when thrown into a multi-threaded environment. But, for guile we had up to now the goal of keeping pure scheme code crash free. The underlying problem here is, that guile's space of cells is actually shared memory between all threads. To make things transparently safe for scheme code would either forbid thread switches to happen at certain points in time (which makes concurrent threads impossible), or to add a lot more locking when accessing the cell space. Am I missing something here? Best regards, Dirk Herrmann _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-27 22:15 ` Dirk Herrmann @ 2004-01-27 23:24 ` Rob Browning 2004-01-29 19:35 ` Marius Vollmer 0 siblings, 1 reply; 22+ messages in thread From: Rob Browning @ 2004-01-27 23:24 UTC (permalink / raw) Cc: Marius Vollmer, Carl Witty, guile-devel Dirk Herrmann <dirk@dirk-herrmanns-seiten.de> writes: > The underlying problem here is, that guile's space of cells is > actually shared memory between all threads. To make things > transparently safe for scheme code would either forbid thread > switches to happen at certain points in time (which makes concurrent > threads impossible), or to add a lot more locking when accessing the > cell space. This raises something I've been thinking about off and on for quite a while. My guess is that we may have some fairly substantial performance and design tradeoffs the more concurrency and "transparent safety" we try to support in a fully preemtive environment. As a trivial example, if you just want "all user C calls to be safe", then you probably have to put guards around the bodies of essentially every function (and or in the code generated by every macro). One exception I can think of is a compiler which knew enough to be able to omit the locks for sections of code that it could either tell were otherwise protected, or that it had otherwise protected on a higher level. In any case, do we have a "current plan" with respect to threading, and on a related note, do we have any plans to consider anything other than our current one interpreter per-process arrangement? -- 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://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-27 23:24 ` Rob Browning @ 2004-01-29 19:35 ` Marius Vollmer 2004-01-29 20:32 ` Rob Browning 2004-01-30 14:45 ` Mikael Djurfeldt 0 siblings, 2 replies; 22+ messages in thread From: Marius Vollmer @ 2004-01-29 19:35 UTC (permalink / raw) Cc: Carl Witty, guile-devel, Marius Vollmer Rob Browning <rlb@defaultvalue.org> writes: > In any case, do we have a "current plan" with respect to threading, I don't have one ready, but I do very much want to have one before 1.8. I need to decide for myself whether I would want to go for full concurrency or for restricting us to a one-thread-at-a-time model. Full concurrency is not a nice-model to program for, one-thread-at-a-time wont be able to take advantage of multiple processors. > and on a related note, do we have any plans to consider anything other > than our current one interpreter per-process arrangement? In my view, it doesn't make much sense to talk about 'the interpreter' in the context of Guile. Our 'interpreter' is just the function eval. What would separate interpreters mean? Separate heaps? -- GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3 331E FAF8 226A D5D4 E405 _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-29 19:35 ` Marius Vollmer @ 2004-01-29 20:32 ` Rob Browning 2004-01-30 14:45 ` Mikael Djurfeldt 1 sibling, 0 replies; 22+ messages in thread From: Rob Browning @ 2004-01-29 20:32 UTC (permalink / raw) Cc: Carl Witty, guile-devel, Marius Vollmer Marius Vollmer <mvo@zagadka.de> writes: > I don't have one ready, but I do very much want to have one before > 1.8. I need to decide for myself whether I would want to go for > full concurrency or for restricting us to a one-thread-at-a-time > model. > > Full concurrency is not a nice-model to program for, > one-thread-at-a-time wont be able to take advantage of multiple > processors. Though I can't actually say *how* we'd do it, another conceptual arrangement might be to allow an interpreter per-posix-thread. It's certainly not as transparent as full concurrency, and unless there were some reasonable way to have all the interpreters share a heap/GC without heading right back into the problems related to full-concurrency, then people would have to structure their solutions to explicitly pass data between interpreters. Again, though, I haven't thought about this enough to have any real idea if this is even remotely feasible. -- 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://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-29 19:35 ` Marius Vollmer 2004-01-29 20:32 ` Rob Browning @ 2004-01-30 14:45 ` Mikael Djurfeldt 2004-02-01 18:49 ` Andy Wingo 1 sibling, 1 reply; 22+ messages in thread From: Mikael Djurfeldt @ 2004-01-30 14:45 UTC (permalink / raw) Cc: Marius Vollmer, guile-devel, djurfeldt, Carl Witty, Rob Browning Marius Vollmer <mvo@zagadka.de> writes: > Rob Browning <rlb@defaultvalue.org> writes: > >> In any case, do we have a "current plan" with respect to threading, There is a document threads/thread-interface.text in workbook which is not a plan, but which brings up things which should be considered when making decisions on the organization of threading in Guile. > I don't have one ready, but I do very much want to have one before > 1.8. I need to decide for myself whether I would want to go for full > concurrency or for restricting us to a one-thread-at-a-time model. > > Full concurrency is not a nice-model to program for, > one-thread-at-a-time wont be able to take advantage of multiple > processors. My view is that the current organization of threading in HEAD has a lot of promise. It does give full concurrency, at the same time as it is usually quite easy to program for. For the application writer or Guile user who doesn't want to concern himself with threading there is nothing special to think about. For those who do write threaded programs, there *could* be a distinction between thread-safe and thread unsafe resources. They would need to use mutecis etc explicitly in the latter case. However, usually, there is not much to think about even at the C level. Since the garbage collector, in the current scheme, only can be invoked at special well-defined places in the code, there is nowadays not even a need for the SCM_DEFER/ALLOW_INTS critical sections. Many of those in the current code can simply be removed. I know what I'm talking about here since I have written threaded applications using HEAD. Two have been using gtk-1.2, with an event handler thread, and multiple threads accessing the graphics. I think the highest demands is put on the Guile developers, because there are probably quite a few parts of Guile which we probably would like to have the ambition to make thread-safe (although we wouldn't need to in all cases). But even in this case, we shouldn't exaggerate the problem. Basically, the main thing to look out for is when we have code which changes the state of something which is available for other threads. That doesn't happen too often. There could of course turn up tricky problems with regard to threaded semantics in areas such as signals and exceptions. On the other hand, I think the benefits of allowing full pthreads support are great. Among other roles, Guile is an application extension language. I think it is up to the application writer to decide which thread library he wants to use, so I'd like to see Guile being able to support various thread libraries, the choice being made at Guile initialization time. (These things are discussed in the thread-interface.text document mentioned above.) If the application writer have chosen pthreads, I wouldn't say the downside of removing full concurrency is only with regards to multi-CPU support. What is almost more important is the constraints that will cause on the design of the application. The application writer will then be limited with respect to the designs he can choose between. For example, if we don't support full concurrency, the application writer can't easily write Scheme extensions (Scheme primitives) which run concurrently. (This statement may or may not be true depending on the exact form of the restriction you are thinking about.) Also, supporting pthreads without full concurrency on the Scheme side will likely introduce more overhead than we have now in HEAD because of all arbitration using mutecis and condition variables that would entail. Finally, while multi-CPU support may look exotic now, it's not unlikely that it will become a common thing in within just a few years once the hardware makers eventually run into the long-predicted barriers for making things faster along the current route. I think it would be sad to build ourselves into a corner in this respect... M _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: scm_i_fraction_reduce thread safety 2004-01-30 14:45 ` Mikael Djurfeldt @ 2004-02-01 18:49 ` Andy Wingo 0 siblings, 0 replies; 22+ messages in thread From: Andy Wingo @ 2004-02-01 18:49 UTC (permalink / raw) On Fri, 2004-01-30 at 16:45, Mikael Djurfeldt wrote: > My view is that the current organization of threading in HEAD has a > lot of promise. It does give full concurrency, at the same time as it > is usually quite easy to program for. I don't have anything really constructive to add, but I do want to say that concurrent threads would be wonderful. If you ever check the docs for the python gstreamer bindings[1], you'll see the mess they get into because the python interpreter is single-threaded (due to their refcounting gc strategy). So really you can't write a quality DVD player in python, because the callbacks and signals coming in from many threads have to compete over one mutex. So. Just a note of support for your efforts, they would be much appreciated in media-land. -- Andy Wingo <wingo@pobox.com> _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
* scm_i_fraction_reduce thread safety @ 2003-12-09 20:39 Kevin Ryde 0 siblings, 0 replies; 22+ messages in thread From: Kevin Ryde @ 2003-12-09 20:39 UTC (permalink / raw) There's a comment in scm_i_fraction_reduce questioning the safety of modifying the given fraction. I think it probably isn't safe, if other threads are looking at the fraction concurrently, and also I suspect two threads running that reduce function itself would not be safe. Not sure what to do about it. I guess the choices would be between some sort of lock, not storing back reduced values, or keeping fractions reduced always. Reducing every so often might be a good idea, since rational arithmetic is a bit notorious for intermediate expression swell. Maybe gc could do something. _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2004-02-01 18:49 UTC | newest] Thread overview: 22+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2003-12-11 11:43 scm_i_fraction_reduce thread safety Bill Schottstaedt 2003-12-11 19:19 ` Carl Witty 2003-12-12 12:11 ` Bill Schottstaedt 2003-12-12 15:04 ` Paul Jarc 2003-12-12 23:23 ` Kevin Ryde 2004-01-10 22:38 ` Marius Vollmer 2004-01-10 23:29 ` Kevin Ryde 2004-01-11 1:31 ` Marius Vollmer 2004-01-12 0:51 ` Kevin Ryde 2004-01-12 5:22 ` Richard Todd 2004-01-14 21:09 ` Kevin Ryde 2004-01-21 0:03 ` Marius Vollmer 2004-01-21 0:00 ` Marius Vollmer 2004-01-21 3:11 ` Carl Witty 2004-01-21 21:06 ` Marius Vollmer 2004-01-27 22:15 ` Dirk Herrmann 2004-01-27 23:24 ` Rob Browning 2004-01-29 19:35 ` Marius Vollmer 2004-01-29 20:32 ` Rob Browning 2004-01-30 14:45 ` Mikael Djurfeldt 2004-02-01 18:49 ` Andy Wingo -- strict thread matches above, loose matches on Subject: below -- 2003-12-09 20:39 Kevin Ryde
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).