guile-log directions

guile-log directions

[Stefan Israelsson Tampe]

Hi all,

I'm just about to introduce a new feature for guile-log. A fast
threadsafe version that scales well + suitable ideoms to do logic
programming in parallell.

Now what do we do today.
There is two possibilities to produce a normal logical variable in
guile-log, 
1. A super fast version that is not thread safe that scales
badly for interleaving constructs and delimeted continuaitons.

2. A really slow version that scales badly but is thread safe.

Those following the guile-log devel list will note that I've been
working on improving on guile's vlist/vhash
implementation. vlists/vhashes scales
(normally) well when it comes to lookups of available keys, but
vhashes are not thread safe and also vlists scales badly in 
backtracking usage. So what I've been doing is to make vhashes 
threadsafe and introduced,

  (vlist-truncate! vlist)
  (vhash-truncate! vhash)
  (vlist-refcount++ vlist/vhash)
  (vlist-refcount-- vlist/vhash)

All these constructs beeing thread safe. What truncate does is that it
will try to truncate a list to the position it references to (the
underlying vector might be shared with another ref and hence
one would need to link in a new frame to it and loose scalability) The
reason that truncate! is a good ideom is that at backtracking normally
all later refs is void and one can safely truncate. But not always and
that is what vlist-refcount++ and vlist-refcount-- is targetting. if
refcount is > 0 then the truncate operation is void e.g. it signals
that the vlist is used higher up. Because we have such a good control
on when we store a ref or not in guile-log the API proposed is well 
designed and will enable fast versions of vlist to be used as an assoc
for variable values. So the not super-fast, but fast version of
variables will be objects,val pairs stored in a vhash

Thread safeness and high speed at the same time might cause a red
alert when getting the description of the truncate operation. But
we do not loos to much on employing this scheme fot the single
threaded case. (Mainly a set of fast bit operations, but no extra
memory lookup) Also the code is optimized for 64 bits, it will
probably be slower on 32bit platforms. Anyhow how is thread safeness 
reached? the answer is that each vector containing data is guarded by a
thread id and a thread seq. At each thread creation the current
threads seq number will be incremented and the new thread will get a
new different id with a seq number of zero. So when we create a bin we
associate the current thread id and and the seq id to the bin. And
then when we try to mutate, the id's have to match else we will just
produce a link to the datastructure. This means that thread safeness is
reached (almost). If one have to transport vhashes between threads at a 
later
stage then thread creation, one can enter a command

   (vlist-freeze vhash/vlist)

before moving the hash to the other thread and all would be thread
safe. What this operation does is to decrement the seq in all live
bins that the current thread owns. The problem with this is that for 
some thread applications, we might end up with long chaines of bins and
loose the good propoerties vhashes have. One solution woulod be for
the user to use a binary functional tree instead. Or that we produce a
new ideom e.g.
new-vhash,key.val <- (vhash-assoc key vhash)

where essentially a new vhash is constructed combining many small ones
in order to improve lookup performance according to some
heuristic. This is not done, but is an interesrting idea.

So my message is that we can fix the problem with vhashes and use it
in even more projects, and I'm willing to supply a patch for vlist.scm
is people on the list agree that the ideas above is sound. Else I will
 add vhashes to guile-log, because I belive that they in their right
 incarnation will shine there.

Anyhow there might be improvements that you see on this scheme of
getting it all to work, please feel free to suggest these improvements.

Highly Happy Hacking to you all,
Stefan