Re: vhash speed thread safeness

[Stefan Israelsson Tampe <stefan.itampe@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3074 bytes --]

On Tue, Oct 29, 2013 at 1:34 PM, Ludovic Courtès <ludo@gnu.org> wrote:

> Hi, Stefan,
>
> Stefan Israelsson Tampe <stefan.itampe@gmail.com> skribis:
>
> > 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.
>
> As we discussed, I don’t really like the idea of implementing that much
> in C.
>
My neither, but it is good to see that in cache friendly cases we can
improve the situation 30x. Gives us a goal to strive for. Also the main
intention is to use vashses for guile-log. For this we can note.

1. With this I managed to make an indexer that can find any ordered set of
matches that matches a 10000 consed pattern (x,y) in about 0.5 mu s.
e.g. matches for form (x y) (_ y) (x _) (_ _). the fun part is that the
indexer indexes and y list of list of list including having some elements
beeing variable. This is cool because if you want to solve first order
logic problems you will have sometimes many hundreds of matching patterns
that represents the compiled rules and hence get a speedup for searching
for rule matches.

2.A thread safe version of vhashes could be used for kanren or guile-log.
To improve scalability. In order to use this sanely we need to be able to
truncate the vhash else the lookup complexity will not be that great for
many applications. A truncation means that one need to check if the state
has been stored or not and in case it has been stored do a no-op.

Also, I’d really like the optimization effort to be driven by actual
> profiling data, such as C-level profiles of repeated calls to the
> current ‘vhash-assoc’.  Have you tried that?


No. But a lot of things can be gain by unpacking the vectors and use pure C
vector lookup, I think that we will get that in the second or third version
of the native compiler at least its to much to ask for to get it for the
first one no? Then it's the overhead of VM jumps as usual which probably is
the main contributor.




> > Another pressing need is that vhashes are not thread safe,
>
> Section 2.8 of Bagwell’s paper proposes a simple solution.  All that is
> missing AFAICS is an atomic test-and-set VM op to implement it (which
> may also be useful in other places.)
>
> What do you think of this approach?


For vlists it's probably a good idea, I don't know if it's enough for
vhashes though. Maybe you need a mutex. But lock overhead will be
significant and I suspect that it is faster many times to start afresh in
all threads. But untill we get a well optimized native compiler, lock
overhead is not that pressing.

BTW I have a good enough solution implemented now that I will use for
parallellizing logic programs, which is what I will concentrate on getting
the iso-prolog into shape.


>


>
Thanks,
> Ludo’.
>
>
> /Stefan

[-- Attachment #2: Type: text/html, Size: 4294 bytes --]