art with code

2008-09-10 range iterators

Ported the parallel is_prime example from Keep your multi-core CPU busy with F# to OCaml, which gave me an excuse to write a Range module for iterating over number ranges. Here the current version of Also retired ($) and ($.) in favour of (|>) and (|>.) to make them more consistent with (@@) and (@.).

Here's the is_prime:

open Prelude

let is_prime n =
let max = int (sqrt (float n)) in
not ( (2 --> max) |> Range.find (fun d -> n mod d = 0) )

let primes = (1000000 --> 1100000) |> Range.pfilter is_prime

let () = puts (showInt (sum primes))

0.39s using Range.filter, 0.24s using Range.pfilter.

Oh right, added the following parallel functions too: pfilter, pfoldl1, pfoldr and pfoldr1. Most of the parallel combinators could be abstracted into splitInto process_count input |> par_map f |> combine, which is what I'll probably do next.

[edit] Did the refactoring, eliminating 70+ lines, here is the new version:

let par_mapReduce ?process_count ~rf ~mf l =
let process_count = process_count |? !global_process_count in
splitInto process_count l |> par_map ~process_count mf |> rf

let pmapReduce rf mf = par_mapReduce ~rf ~mf

let pfoldl r f init = pmapReduce (foldl1 r) (foldl f init)
let pfoldl1 f = pmapReduce (foldl1 f) (foldl1 f)
let pfoldr r f init = pmapReduce (foldr1 r) (foldr f init)
let pfoldr1 f = pmapReduce (foldr1 f) (foldr1 f)

let piter f = pmapReduce ignore (iter f)
let pmap f = pmapReduce concat (map f)
let pfilter f = pmapReduce concat (filter f)

If you have a collection module with splitInto and some of the other functions, you can basically paste this right in. With Range it wasn't quite that easy because par_map returns a list, so the foldls have to use List.foldl for the reduce fold. And I haven't made foldrs for Range, so couldn't add the pfoldrs.

It feels like a promising start towards generalizing the parallel iterators though.
Post a Comment

Blog Archive

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes