How to map a function over a list in parallel in racket?

Question

The question title says it all, really: What is the best way map a function over a list in parallel in racket? Thanks.

Indurate

Answer 1

If you mean over multiple processor cores, then the most general approach is to use Places.

Places enable the development of parallel programs that take advantage of machines with multiple processors, cores, or hardware threads.

A place is a parallel task that is effectively a separate instance of the Racket virtual machine. Places communicate through place channels, which are endpoints for a two-way buffered communication.

You might be able to use the other parallelization technique, Futures, but the conditions for it to work are relatively limited, for example floating point operations, as described here.

---

EDIT: In response to the comment:

Is there an implementation of parallel-map using places somewhere?

First, I should back up. You might not need Places. You can get concurrency using Racket threads. For example, here's a map/thread:

#lang racket

(define (map/thread f xs)
  ;; Make one channel for each element of xs.
  (define cs (for/list ([x xs])
               (make-channel)))
  ;; Make one thread for each elemnet of xs.
  ;; Each thread calls (f x) and puts the result to its channel.
  (for ([x xs]
        [c cs])
    (thread (thunk (channel-put c (f x)))))
  ;; Get the result from each channel.
  ;; Note: This will block on each channel if not yet ready.
  (for/list ([c cs])
    (channel-get c)))

;; Use:
(define xs '(1 2 3 4 5))
(map add1 xs)
(map/thread add1 xs)

If the work being done involves blocking, e.g. I/O requests, this will give you "parallelism" in the sense of not being stuck on I/O. However Racket threads are "green" threads so only one at a time will be using the CPU.

If you truly need parallel use of multiple CPU cores, then you would need Futures or Places.

Due to the way Places are implemented --- effectively as multiple instances of Racket --- I don't immediately see how to write a generic map/place. For examples of using places in a "bespoke" way, see:

• Places in the Guide
• Places in the Reference

Travis

Thanks Greg. I did try a quick attempt mapping the factorial function over a list of large integers using futures but the computation seemed bound to one core. However, I was obviously using bignums — I hadn't picked up on the fact that futures are restricted to floats. – Indurate

BTW I was a little casual in my description. It's not so much "floating point". Both fixed point and floating could work; the key is whether they're fixnum or flonum and don't need to be boxed/allocated. It's a bit tricky. That's why I suggested Places as the more general thing to try. Only if you're doing numeric stuff and are willing to review the code carefully are you likely to find Futures helpful (as far as I understand it; someone else who know more might jump in and correct me). – Travis

Is there an implementation of parallel-map using places somewhere? I'd love to just be able to call (parallel-map f xs ys zs) parameterized by the number of available cores and be done with it. – Apposition

@Apposition Seems it is not so easy to get it working in a generic way, because places are liftet to the modules top level (a bit confusing at first, but reading the paragraphs in the documentation multiple times helps). I tried putting multiple places inside a list, but then was unable use them later in my program. This lifting has some weird effects. In general the places concept seems great though, like almost all concepts in Racket. – Protraction

Answer 2

I don't know in Racket, but I implemented a version in SISC Scheme.

(define (map-parallel fn lst)
  (call-with-values (lambda ()
                      (apply parallel 
                             (map (lambda (e)
                                    (delay (fn e)))
                                  lst)))
    list))

Only parallel is not R5RS.

Example of use:

Using a regular map:

(time (map (lambda (a)
        (begin
          (sleep 1000)
          (+ 1 a)))
     '(1 2 3 4 5)))
=> ((2 3 4 5 6) (5000 ms))

Using the map-parallel:

(time (map-parallel (lambda (a)
        (begin
          (sleep 1000)
          (+ 1 a)))
     '(1 2 3 4 5)))
=> ((2 3 4 5 6) (1000 ms))

Inapposite