Re: vhash speed thread safeness

[Stefan Israelsson Tampe]

On Tue, Oct 29, 2013 at 1:34 PM, Ludovic Courtès <address@hidden> wrote:

Hi, Stefan,

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