vhash speed thread safeness

[Stefan Israelsson Tampe]

Hi all,

I did some tests witha C-based vhash implementation, it's possible to 
increse the speed by 30x compared to current vlist imlpementation in
guile. It would be possible to get this speed today if one implemented
vhash-assoc as a VM op. Anyway using the source as a standard lib will
get you about 10x speed increase.

Another pressing need is that vhashes are not thread safe, also a
downside is that if there are many versions spawned by each vhash the
good theoretical properties may not realize. Anyway here is a
suggestion of how to make it thread safe:

1. keep two numbers seq-int and thread-id on the block.
thread-id is a unique id for a thread. And
seq-id is a unique id for a state.

2. At thread-creation in thread 1 spawning thread 2. increment
thread 1's seq-id, and allocate a new id to thread 2 and set it's
seq-id to zero.

3. Att vhash-cons, if not the vhash seq-id and thread-id matches we
must create a new block pointing to the old vhash with size equal to
k.

4. this is thread safe and will not waste space, but can create
problems with lot's of small blocks linked and essentially get a sort 
of linked list the computational lookup is o(T), T is the number of
threads.

5. If we get an issue with lot's of small block linked together we
could detect this and issue a "remake" in order to speed up
access times. This is not a problem that is unique to threading but
can be seen in a naive use of vhashes for many applications that 
backtracks and use old copies of vhashes. So a solution of
autocompilation would be needed.

6. I plan to add a version of vhashes to guile-log as a replacement of
the assoc list. What I will then use is to tag vhash blocks as
referenced and when backtracking and the block is not referenced it
will simply reset the offset pointer and reuse the block-frame instead
of linking another one to it. Some kind of reference counter technique 
would
be used here. n guile-log we have good control on when we reference
for storage so this solution would probably work just great.

With all this implementing good thread safe ideoms into guile-log
would be quite possible.

Regards
Stefan