I've been playing around with a simple AVL tree that uses the split/join operations that Adams originally applied to weight-balanced binary trees[1] and then Blelloch, Ferizovic, and Sun later applied to other kinds of balanced binary trees.[2] The latter paper concentrates on how certain operations (union, intersection, difference) are easily parallelized with an implementation that uses this approach. In their tests, they saw performance increase linearly up to around 32 cores.
I tried the same thing with futures on racket-cs (since I understand that it has fewer blocking/synchronized operations than racket-c). On my 8 core machine, performance is slightly better for a parallel version of `union` (which is implemented exactly as Blelloch et al. have it on the second page of their paper) but it's nowhere near a linear speed-up. The parallel version completes a test in about 80% of the time that the sequential version does. The future-visualizer doesn't show any synchronizing or blocking events (aside from the touches), though I also don't entirely understand what it does show. What, for example, is indicated by a thread that has only a very short green horizontal line? Is it just idle for most of the time? I'm using futures pretty much the same way that Dominik Pantůček is using them in his `futures-sort` package, with a parallelism depth computed from the number of cores available.[3] (Thank you for the excellent example, by the way, Dominik.) [1] http://groups.csail.mit.edu/mac/users/adams/BB/ [2] https://www.cs.cmu.edu/~guyb/papers/BFS16.pdf [3] https://github.com/dzoep/futures-sort/blob/master/main.rkt#L338 My own code has: (define (parallel-union t1 t2 cmp) (let loop ([t1 t1] [t2 t2] [depth (inexact->exact (ceiling (log (processor-count) 2)))]) (match* (t1 t2) [(#f _) t2] [(_ #f) t1] [(_ (node _ l2 (and (cons k2 _) kv2) r2)) (define-values (l1 _ r1) (split t1 k2 cmp)) (cond [(fx<= depth 0) (define tl (loop l1 l2 (fx- depth 1))) (define tr (loop r1 r2 (fx- depth 1))) (join tl kv2 tr)] [else (define tl (future (λ () (loop l1 l2 (fx- depth 1))))) (define tr (loop r1 r2 (fx- depth 1))) (join (touch tl) kv2 tr)])]))) -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAKfDxxyUaPFf6Kdum-FuKYunGrPCLsQxMZd3%3D4NR5k5MLqj6yg%40mail.gmail.com.
