I missed to send this to guile-devel, sorry! ---------- Forwarded message ---------- From: Stefan Israelsson Tampe <stefan.ita...@gmail.com> Date: Wed, Apr 4, 2012 at 5:36 PM Subject: Re: Inclusion of guile-log II To: Mark H Weaver <m...@netris.org>
Mark I must give you right, Actually contemplating it some more, consider having a large tree vith variables in defined in thread 1 that starts two subthread 2 and 3, How do one set those variables burried in the tree? You would not like to treat the datastructures uniquely. Here Kanren works really well and so well that I'm contemplating to have both an assoc list and a stack and use the assoc for just this case e.g. when going from datastructure in thread 1 to datastructure in thread 2 or 3. And not only this, one of the drawback with changing variable in thread 0 to for example set the variable to a list of ( tread.id . key) pairs is that the synchronsisation has pretty dramatic effects on performance as you know. But I would just not dwell too much into trying to optimize that synchronisation. Because what would be cool though is to use an assoc-list as in kanren and when it grows to large issue a batch synchronisation and bring out that whole assoc into modifying the thread0 datastructure in one go. The amortized cost on each synchronisation should than decrease by say a factor of 20 e.g. about 20ns per op. with about 10 interations and the transfer cost should be small compared to the overall lookup cost that needed to be done in order to create a 20 element assoc What do you think? WDYT On Wed, Apr 4, 2012 at 10:23 AM, Stefan Israelsson Tampe < stefan.ita...@gmail.com> wrote: > Hi Mark, > > Thanks for the reply! > > > > Several libraries for Guile (e.g. guile-gnome) include C code that uses > > Guile's C interface, and this does not pose any difficulties for making > > an external package. Can you please explain more clearly why > > guile-log is impractical to package separately? > > Actually I have now strong feelings more that it would be cool to have > logic programming abilities in guile from the startup and that I started > all my guile involvenment suggesting to add that to guile. I'm actually > pretty fine with maintaining a lib of it's own. > > > > FWIW, I find guile-log to be very interesting work, but I also get the > > impression that it is a somewhat experimental and unproven approach to > > logic programming in Scheme. Only time will tell whether it proves to > > be a successful approach. > > I have actually used it quite a lot in examples but that's only me, I do > find it stable enough > to do good work in it. It's that I feel that I constantly find new cool > things I would like to > add to it and feel hey it's experimental cause it's only me using it. > > > >One of my concerns is the extensive use of mutable state in guile-log. > >Recently I have been thinking about how best to support scalable > >lock-free concurrency in Guile, so this question looms large in my mind: > >How effectively will guile-log be able to make use of a potentially > >large number of processor cores. Do you have any thoughts on that? > > For multicore you would like to support both traditional lock centered > programming > and lock free programming. For lock free you will for each variable that > is seen by > m threads be matched by m variables that points to the global one, if we > assume that > the global one does not change, then binding the variable in a thread will > only relate to that > thread. So to conceptually match kanrens datastructure multicore > capability can be done. > the main current problem though is that for each core you would like to > maintain a local stack > and currently this is a fixed sized stack. So before starting implementing > multicore lock free > programming to guile-log I would like to introduce resizable stacks which > probably is a much more difficult programming task that later make the lock > free threading. > > If on the other hand we would like to connect one thread local prolog > variable with another tread local prolog variable (think a fluid that > points to another fluid) we would probably want som synchronisation ideoms > attached to them but that is also not difficult especially difficult and > could be maintained beside the lock free versions, I guess that this is not > inluded in kanren (I think that I would add these to guile-kanren though > when thinking about it) > > > > Kanren is written in a purely functional style, and this may well prove > > to a significant performance advantage in the multi-core future, even > > though it runs slower on a uniprocessor. > > Kanren is not going to be faster then prolog multicore versions or > guile-log If I implement it > correctly for most cases I've seen. But the functional way of kanren has > use cases > where it can really shine due to it's way of mainting the variable binding > datastructure. > > One thing that can lead to a dramatic improvement is in memoizing states > in backtracking > so that when we try to evaluate a goal we look if we have had this state > before and if so > reuse that expensive deduction. Another use case is when the code uses > interleaving constructs guile-log stack based approaches is inferior here > now due to the fact that we > need to unwind and restore the stack meaning that the stack need to grow > back and forth > and in the process recreate the variable bindings which is a bit clumsy. > Here guile-log lacks > the ability to do this but it's on my TODO list to have something usable > here. > > Another reason is that sometimes the kanren ideom lead to elegant > expressions of algorithms and sometimes guile-log win's, I'm trying to make > that even by bringing over fetures from kanren to guile-log and vice verse > so that in the end there would only need to be a performance question of > when one or the other is used. > > /Stefan > > > On Wed, Apr 4, 2012 at 2:05 AM, Mark H Weaver <m...@netris.org> wrote: > >> Hi Stefan, >> >> Stefan Israelsson Tampe <stefan.ita...@gmail.com> writes: >> > The guile-log code is very dependent on guile! It's based on a c-file >> > which uses >> > guile C interface in order to get speedy and featureful at the same >> > time. So basically I have no hope that this codebase could be >> > independent from guile. >> >> Several libraries for Guile (e.g. guile-gnome) include C code that uses >> Guile's C interface, and this does not pose any difficulties for making >> it an external package. Can you please explain more clearly why >> guile-log is impractical to package separately? >> >> FWIW, I find guile-log to be very interesting work, but I also get the >> impression that it is a somewhat experimental and unproven approach to >> logic programming in Scheme. Only time will tell whether it proves to >> be a successful approach. >> >> One of my concerns is the extensive use of mutable state in guile-log. >> Recently I have been thinking about how best to support scalable >> lock-free concurrency in Guile, so this question looms large in my mind: >> How effectively will guile-log be able to make use of a potentially >> large number of processor cores. Do you have any thoughts on that? >> >> It's unclear whether individual processors can be made much faster than >> they are today. Making efficient use of a large number of processors >> will likely become increasingly important in the future. In that >> context, there is a significant advantage to avoiding mutation of shared >> state, since that causes cache lines to bounce back and forth between >> processors, which kills performance. >> >> Kanren is written in a purely functional style, and this may well prove >> to a significant performance advantage in the multi-core future, even >> though it runs slower on a uniprocessor. >> >> Regards, >> Mark >> > >
