guile-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Fwd: Inclusion of guile-log II


From: Stefan Israelsson Tampe
Subject: Fwd: Inclusion of guile-log II
Date: Wed, 4 Apr 2012 18:30:35 +0200


I missed to send this to guile-devel, sorry!
---------- Forwarded message ----------
From: Stefan Israelsson Tampe <address@hidden>
Date: Wed, Apr 4, 2012 at 5:36 PM
Subject: Re: Inclusion of guile-log II
To: Mark H Weaver <address@hidden>


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 <address@hidden> 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 <address@hidden> wrote:
Hi Stefan,

Stefan Israelsson Tampe <address@hidden> 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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]